Recognition and Optimization Algorithms in {P6,C6}-Free Graphs

  • FLORIN MOIZE “Dunarea de Jos“ University of Galati
  • MIHAI TALMACIU ”Vasile Alecsandri” University of Bacau
Keywords: {P6,C6}-free graphs, weak decomposition, recognition algorithms, combinatorial optimization algorithms


Secure dominating sets can be applied as protection strategies by minimizing the number of guards to secure a system so as to be cost effective as possible.
Dominating sets that induce a complete subgraph have a great diversity of applications. In setting up the communications links in a network one might want a strong core group that can communicate with each other member of the core group and so that everyone from outside the group could communicate with someone within the core group. For arbitrary graphs, the problem of finding the size of a minimum dominating set in the graph is an NP-complete problem. The dominating set problem remains NP-complete even for some specific classes of graphs, including chordal graphs, split graphs and bipartite graphs. The class of Pk-free graphs has received a fair amount of attention in the theory of graph algorithms. Given an NP-hard optimization problem, it is often fruitful to study its complexity when the instances are restricted to Pk-free graphs. An algorithm that finds such a dominating subgraph of a connected P6-free graph in
polynomial time enables us to solve the hypergraph 2-colorability problem in polynomial time for the class of hypergraphs with P6-free incidence graphs. We characterize the triangle-free and {P6, C6} -free graphs using weakly decomposition and a dominating complete bipartite subgraph, we give a recognition algorithm, and combinatorial optimization algorithms for this class of graphs, comparable from the point of view of execution in time with existing ones.


Download data is not yet available.

Author Biography

FLORIN MOIZE, “Dunarea de Jos“ University of Galati

PhD student at The University "Dunărea de Jos" of Galați, Romȃnia

How to Cite
MOIZE F, TALMACIU M. Recognition and Optimization Algorithms in {P6,C6}-Free Graphs. The Annals of “Dunarea de Jos“ University of Galati. Fascicle III, Electrotechnics, Electronics, Automatic Control, Informatics [Internet]. 18Dec.2019 [cited 27Oct.2020];42(2):5-. Available from: