Forbidden subgraphs, hamiltonicity and closure in claw-free graphs (Q1297424): Difference between revisions

The stability of classes of graphs defined by forbidden subgraph conditions under the closure defined by \textit{Z. Ryjáček} [J. Comb. Theory, Ser. B 70, No. 2, 217-224 (1997; Zbl 0872.05032)] is studied. In particular, it is shown that the following classes of graphs are stable for all positive integers \(i, j, k\): \(\text{CP}_i\)-free graphs, \(\text{CZ}_i\)-free graphs, and \(\text{CN}_{i,j,k}\)-free graphs. The class of \(\text{CB}_{i,j}\)-free graphs are shown to not be stable. Using the stability results, some classes of graphs defined by forbidden subgraph conditions are shown to either be hamiltonian or belong to a special class of exceptional graphs. For example, it is proved that any \(2\)-connected \(\text{CP}_7\)-free graph is either hamiltonian or belongs to one exceptional class of \(2\)-connected graphs constructed from edge disjoint complete graphs. These results extend some of the classical results on forbidden graphs that imply hamiltonian.