TY - JOUR AU - Florin Moize AU - Mihai Talmaciu PY - 2019/12/18 Y2 - 2024/03/29 TI - Recognition and Optimization Algorithms in {P6,C6}-Free Graphs JF - The Annals of “Dunarea de Jos“ University of Galati. Fascicle III, Electrotechnics, Electronics, Automatic Control, Informatics JA - EEAI VL - 42 IS - 2 SE - Articles DO - https://doi.org/10.35219/eeaci.2019.2.01 UR - https://www.gup.ugal.ro/ugaljournals/index.php/eeaci/article/view/2819 AB - 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 inpolynomial 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. ER -