TY - JOUR
T1 - Forbidden set of induced subgraphs for 2-connected supereulerian graphs
AU - Wang, Shipeng
AU - Xiong, Liming
N1 - Publisher Copyright:
© 2017 Elsevier B.V.
PY - 2017/12
Y1 - 2017/12
N2 - Let H={H1,…,Hk} be a set of connected graphs. A graph is said to be H-free if it does not contain any member of H as an induced subgraph. We show that if the following statements hold, • |H|≥2,• K1,3∈H,• for any integer n0, every 2-connected H-free graph G of order at least n0 is supereulerian, i.e.,G has a spanning closed trailthen H∖{K1,3} contains an Ni,j,k or a path where Ni,j,k denotes the graph obtained by attaching three vertex-disjoint paths of lengths i,j,k≥0 to a triangle. As an application, we characterize all the forbidden triples H with K1,3∈H such that every 2-connected H-free graph is supereulerian. As a byproduct, we also characterize minimal 2-connected non-supereulerian claw-free graphs.
AB - Let H={H1,…,Hk} be a set of connected graphs. A graph is said to be H-free if it does not contain any member of H as an induced subgraph. We show that if the following statements hold, • |H|≥2,• K1,3∈H,• for any integer n0, every 2-connected H-free graph G of order at least n0 is supereulerian, i.e.,G has a spanning closed trailthen H∖{K1,3} contains an Ni,j,k or a path where Ni,j,k denotes the graph obtained by attaching three vertex-disjoint paths of lengths i,j,k≥0 to a triangle. As an application, we characterize all the forbidden triples H with K1,3∈H such that every 2-connected H-free graph is supereulerian. As a byproduct, we also characterize minimal 2-connected non-supereulerian claw-free graphs.
KW - Claw-free
KW - Forbidden set
KW - Induced subgraph
KW - Supereulerian
UR - http://www.scopus.com/inward/record.url?scp=85028764176&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2017.08.006
DO - 10.1016/j.disc.2017.08.006
M3 - Article
AN - SCOPUS:85028764176
SN - 0012-365X
VL - 340
SP - 2792
EP - 2797
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 12
ER -