Characterizing forbidden pairs for hamiltonian properties (Q1367026): Difference between revisions

Given a family \(\mathcal F\) of graphs, a graph \(G\) is said to be \(\mathcal F\)-free if \(G\) contains no induced subgraph isomorphic to a member of \(\mathcal F\). Let \(P\) stand for any of the following graph-theoretic properties: traceable, hamiltonian, pancyclic, panconnected, cyclic extendable. The authors present a variety of theorems of the following general form: Let \(R\) and \(S\) be connected graphs other than the path of length 2, and let the graph \(G\) have at least minimal connectivity necessary for property \(P\). Then, if \(|V(G)|\) is not too small (generally \(\geq 10\)), we have [\(G\) is \(\{R,S\}\)-free implies \(G\) has property \(P\)] if and only if [\(R=K_{1,3}\) and \(S\) is one of a short list of forbidden subgraphs].