Closure and forbidden pairs for Hamiltonicity (Q1403925): Difference between revisions

It was shown in [\textit{Z. Ryjáček}, Discrete Math. 164, 257-263 (1997; Zbl 0872.05044)] that the forbidden pairs \(R\) and \(S\) of connected graphs that imply a sufficiently large \(2\)-connected graph \(G\) is Hamiltonian are \(R = C\), the claw, and \(S\) a subgraph of \(P_6, Z_3, W\), the wounded, or \(N\), the net. In the present paper it is shown that the claw-free closure of all of these \(RS\)-free graphs form a subclass of the class of \(CN\)-free graphs. Thus, the determination of forbidden pairs of connected graphs that imply a graph is Hamiltonian can be reduced to the consideration of \(CN\)-free graphs. Also, the structure of the closure of \(CN\)-free graphs is completely determined.