1. Pairs of forbidden induced subgraphs for homogeneously traceable graphs
- Author
-
Li, Binlong, Broersma, Hajo, and Zhang, Shenggui
- Subjects
- *
GRAPHIC methods , *GRAPH theory , *HAMILTONIAN graph theory , *PATHS & cycles in graph theory , *COMPLETE graphs , *COMBINATORICS - Abstract
Abstract: A graph is called homogeneously traceable if for every vertex of , contains a Hamilton path starting from . For a graph , we say that is -free if contains no induced subgraph isomorphic to . For a family of graphs, is called -free if is -free for every . Determining families of graphs such that every -free graph has some graph property has been a popular research topic for several decades, especially for Hamiltonian properties, and more recently for properties related to the existence of graph factors. In this paper we give a complete characterization of all pairs of connected graphs such that every 2-connected -free graph is homogeneously traceable. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF