zbMATH — the first resource for mathematics

Characterizing forbidden pairs for hamiltonian properties. (English) Zbl 0879.05050
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].

MSC:
 05C45 Eulerian and Hamiltonian graphs 05C75 Structural characterization of families of graphs 05C38 Paths and cycles 05C40 Connectivity
Full Text:
References:
 [1] Bedrossian, P., Forbidden subgraph and minimum degree conditions for Hamiltonicity, () [2] Broersma, H.J.; Veldman, H.J., Restrictions on induced subgraphs ensuring Hamiltonicity or pancyclicity of K1,3-free graphs, (), 181-194 [3] Duffus, D.; Gould, R.J.; Jacobson, M.S., Forbidden subgraphs and the Hamiltonian theme, (), 297-316 · Zbl 0466.05049 [4] Faudree, R.J.; Gould, R.J.; Ryjacek, Z.; Schiermeyer, I., Forbidden subgraphs and pancyclicity, (), 13-32 · Zbl 0904.05055 [5] R.J. Faudree, Z. Ryjacek and I. Schiermeyer, Forbidden subgraphs and cycle extendability, J. Combin. Math. Combin. Comput., to appear. [6] Gould, R.J., Graph theory, (1988), Benjamin/Cummings Menlo Park, CA · Zbl 0682.05003 [7] Gould, R.J.; Jacobson, M.S., Forbidden subgraphs and Hamiltonian properties of graphs, Discrete math., 42, 189-196, (1982) · Zbl 0495.05039 [8] Hendry, G.R.T., Extending cycles in graphs, Discrete math., 85, 59-72, (1990) · Zbl 0714.05038 [9] Shepherd, F.B., Hamiltonicity in claw-free graphs, J. combin. theory ser. B, 53, 173-194, (1991) · Zbl 0766.05055
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.