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

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.