Dominating sets and Hamiltonicity in \(K_{1,3}\)-free graphs.

*(English. Russian original)*Zbl 0852.05062
Sib. Math. J. 35, No. 3, 421-425 (1994); translation from Sib. Mat. Zh. 35, No. 3, 475-479 (1994).

An undirected graph is called \(K_{1, 3}\)-free, if it contains no induced subgraph isomorphic to the complete bipartite graph \(K_{1, 3}\). The class of \(K_{1, 3}\)-free graphs includes all the line graphs and is well studied in many aspects. For instance, it is known that, for \(K_{1, 3}\)-free graphs, the strong Berge conjecture holds, and certain problems that are NP-complete in the general setting are polynomially solvable for them. Since the middle of the 70s articles have begun to appear that are devoted to the study of conditions sufficient for Hamiltonicity of a \(K_{1,3}\)-free graph. It is the following conjecture extending Thomassen’s conjecture for line graphs that became widely known: Every 4-connected \(K_{1, 3}\)-free graph is Hamiltonian.

It is known that the Hamiltonian cycle problem is NP-complete for 3-connected cubic planar graphs. Plummer and Pulleyblank showed that there exist infinitely many non-Hamiltonian 3-connected cubic graphs that, moreover, possess no dominating cycles. It is easy to observe that the replacement of vertices with triangles transforms a 3-connected cubic graph into a 3-connected \(K_{1,3}\)-free graph; moreover, the former is Hamiltonian if and only if such is the latter. Consequently, the above-cited assertions for 3-connected cubic graphs are also valid for the 3-connected \(K_{1,3}\)-free graphs.

Every Hamiltonian graph is, obviously, 2-connected. In the theorem below, we list some conditions each of which guarantees the existence of a Hamiltonian cycle in a 2-connected \(K_{1,3}\)-free graph. Theorem 1.1. Let \(G\) be a 2-connected \(K_{1,3}\)-free graph with \(n\) vertices. The graph \(G\) is Hamiltonian if at least one of the following conditions holds: (c 1) the subgraph induced by \(N(x)\) is connected for every vertex \(x\in V(G)\); (c 2) \(\delta(G)\geq (n- 2)/3\); (c 3) the diameter of \(G\) does not exceed 2; (c 4) for every triple of pairwise nonadjacent vertices \(\{x, y, z\}\subseteq V(G)\), \(\deg(x)+ \deg(y)+ \deg(z)\geq n- 2\); (c 5) \(|N(x)\cup N(y)|\geq (n+ 1)/3\) for every pair of vertices \(x, y\in V(G)\).

It is easy to see that each of the conditions (c 1)–(c 5) of Theorem 1.1 can be expressed as \(\forall x R(x)\), where \(x\) is a vertex, or a pair, or a triple of vertices and \(R(x)\) is some property. In the present article, we establish a condition of the form \(\exists x R(x)\), where \(x\) is a pair of vertices and \(R(x)\) is the property of domination.

It is known that the Hamiltonian cycle problem is NP-complete for 3-connected cubic planar graphs. Plummer and Pulleyblank showed that there exist infinitely many non-Hamiltonian 3-connected cubic graphs that, moreover, possess no dominating cycles. It is easy to observe that the replacement of vertices with triangles transforms a 3-connected cubic graph into a 3-connected \(K_{1,3}\)-free graph; moreover, the former is Hamiltonian if and only if such is the latter. Consequently, the above-cited assertions for 3-connected cubic graphs are also valid for the 3-connected \(K_{1,3}\)-free graphs.

Every Hamiltonian graph is, obviously, 2-connected. In the theorem below, we list some conditions each of which guarantees the existence of a Hamiltonian cycle in a 2-connected \(K_{1,3}\)-free graph. Theorem 1.1. Let \(G\) be a 2-connected \(K_{1,3}\)-free graph with \(n\) vertices. The graph \(G\) is Hamiltonian if at least one of the following conditions holds: (c 1) the subgraph induced by \(N(x)\) is connected for every vertex \(x\in V(G)\); (c 2) \(\delta(G)\geq (n- 2)/3\); (c 3) the diameter of \(G\) does not exceed 2; (c 4) for every triple of pairwise nonadjacent vertices \(\{x, y, z\}\subseteq V(G)\), \(\deg(x)+ \deg(y)+ \deg(z)\geq n- 2\); (c 5) \(|N(x)\cup N(y)|\geq (n+ 1)/3\) for every pair of vertices \(x, y\in V(G)\).

It is easy to see that each of the conditions (c 1)–(c 5) of Theorem 1.1 can be expressed as \(\forall x R(x)\), where \(x\) is a vertex, or a pair, or a triple of vertices and \(R(x)\) is some property. In the present article, we establish a condition of the form \(\exists x R(x)\), where \(x\) is a pair of vertices and \(R(x)\) is the property of domination.

##### Keywords:

Hamiltonicity; Thomassen’s conjecture; Hamiltonian cycle problem; dominating cycles; cubic graphs
PDF
BibTeX
XML
Cite

\textit{A. A. Ageev}, Sib. Math. J. 35, No. 3, 421--425 (1994; Zbl 0852.05062); translation from Sib. Mat. Zh. 35, No. 3, 475--479 (1994)

Full Text:
DOI

##### References:

[1] | K. R. Parthasarathy and G. Ravindra, ”The strong perfect graph conjecture is true forK 1,3-free graphs,” J. Combin. Theory Ser. B,21, No. 3, 212–223 (1976). · Zbl 0332.05106 · doi:10.1016/S0095-8956(76)80005-6 |

[2] | G. J. Minty, ”On maximal independent sets of vertices in claw-free graphs,” J. Combin. Theory Ser. B,28, No. 3, 284–304 (1980). · Zbl 0434.05043 · doi:10.1016/0095-8956(80)90074-X |

[3] | N. Sbihi, ”Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile,” Discrete Math.,29, No. 1, 53–76 (1980). · Zbl 0444.05049 · doi:10.1016/0012-365X(90)90287-R |

[4] | R. J. Gould, ”Updating the Hamiltonian problem–a survey,” J. Graph Theory,15, No. 2, 121–157 (1991). · Zbl 0746.05039 · doi:10.1002/jgt.3190150204 |

[5] | J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North-Holland, Amsterdam (1976). · Zbl 1226.05083 |

[6] | M. M. Matthews and D. P. Sumner, ”Hamiltonian results inK 1,3-free graphs,” J. Graph Theory,8, No. 1, 139–146 (1984). · Zbl 0536.05047 · doi:10.1002/jgt.3190080116 |

[7] | M. R. Garey, D. S. Johnson, and R. E. Tarjan, ”The planar Hamiltonian circuit problem is NP-complete,” SIAM J. Comput.,5, No. 4, 704–714 (1976). · Zbl 0346.05110 · doi:10.1137/0205049 |

[8] | M. D. Plummer and W. R. Pulleyblank, ”On proximity to paths and cycles in 3-connected graphs,” Ars Combin.,14, 169–185 (1982). · Zbl 0502.05035 |

[9] | D. J. Oberly and D. P. Sumner, ”Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian,” J. Graph Theory,3, No. 4, 351–356 (1979). · Zbl 0424.05036 · doi:10.1002/jgt.3190030405 |

[10] | M. M. Matthews and D. P. Sumner, ”Longest paths and cycles inK 1,3-free graphs,” J. Graph Theory,9, No. 2, 269–277 (1985). · Zbl 0591.05041 · doi:10.1002/jgt.3190090208 |

[11] | R. J. Gould, Traceability in Graphs, Ph. D. Thesis, Western Michigan Univ. (1979). |

[12] | C. Q. Zhang, ”Hamilton cycles in claw-free graphs,” J. Graph Theory,12, No. 2, 209–216 (1988). · Zbl 0642.05037 · doi:10.1002/jgt.3190120211 |

[13] | H. J. Brersma, Sufficient Conditions for Hamiltonicity and Traceability ofK1,3-Free Graphs [Preprint] (1986). |

[14] | R. J. Faudree, R. J. Gould, M. S. Jacobson, L. M. Lesniak, and T. E. Lindquester, ”A generalization of Dirac’s theorem forK 1,3-free graphs,” Period. Math. Hungar.,24, No. 1, 37–54 (1992). · Zbl 0784.05042 · doi:10.1007/BF02651085 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.