Abstract
A graph G is called homogeneously traceable if for every vertex v of G, G contains a Hamilton path starting from v. For a graph H, we say that G is H-free if G contains no induced subgraph isomorphic to H. For a family H of graphs, G is called H-free if G is H-free for every H∈H. Determining families of graphs H such that every H-free graph G 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 R,S such that every 2-connected {R,S}-free graph is homogeneously traceable.
Original language | English |
---|---|
Pages (from-to) | 2800-2818 |
Number of pages | 19 |
Journal | Discrete mathematics |
Volume | 312 |
Issue number | 18 |
DOIs | |
Publication status | Published - Sept 2012 |
Keywords
- MSC-05C
- Induced subgraph
- Forbidden subgraph
- Homogeneously traceable graph
- Hamiltonian graph