TY - JOUR
T1 - Pairs of forbidden induced subgraphs for homogeneously traceable graphs
AU - Li, Binlong
AU - Broersma, Hajo
AU - Zhang, Shenggui
PY - 2012/9/28
Y1 - 2012/9/28
N2 - 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.
AB - 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.
KW - Forbidden subgraph
KW - Hamiltonian graph
KW - Homogeneously traceable graph
KW - Induced subgraph
UR - http://www.scopus.com/inward/record.url?scp=84862240370&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2012.05.018
DO - 10.1016/j.disc.2012.05.018
M3 - 文章
AN - SCOPUS:84862240370
SN - 0012-365X
VL - 312
SP - 2800
EP - 2818
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 18
ER -