TY - JOUR
T1 - Pairs of forbidden subgraphs and 2-connected supereulerian graphs
AU - Čada, Roman
AU - Ozeki, Kenta
AU - Xiong, Liming
AU - Yoshimoto, Kiyoshi
N1 - Publisher Copyright:
© 2018 Elsevier B.V.
PY - 2018/6
Y1 - 2018/6
N2 - Let G be a 2-connected claw-free graph. We show that • if G is N1,1,4-free or N1,2,2-free or Z5-free or P8-free, respectively, then G has a spanning Eulerian subgraph (i.e. a spanning connected even subgraph) or its closure is the line graph of a graph in a family of well-defined graphs,• if the minimum degree δ(G)≥3 and G is N2,2,5-free or Z9-free, respectively, then G has a spanning Eulerian subgraph or its closure is the line graph of a graph in a family of well-defined graphs. Here Zi (Ni,j,k) denotes the graph obtained by attaching a path of length i≥1 (three vertex-disjoint paths of lengths i,j,k≥1, respectively) to a triangle. Combining our results with a result in [Xiong (2014)], we prove that all 2-connected hourglass-free claw-free graphs G with one of the same forbidden subgraphs above (or additionally δ(G)≥3) are hamiltonian with the same excluded families of graphs. In particular, we prove that every 3-edge-connected claw-free hourglass-free graph that is N2,2,5-free or Z9-free is hamiltonian.
AB - Let G be a 2-connected claw-free graph. We show that • if G is N1,1,4-free or N1,2,2-free or Z5-free or P8-free, respectively, then G has a spanning Eulerian subgraph (i.e. a spanning connected even subgraph) or its closure is the line graph of a graph in a family of well-defined graphs,• if the minimum degree δ(G)≥3 and G is N2,2,5-free or Z9-free, respectively, then G has a spanning Eulerian subgraph or its closure is the line graph of a graph in a family of well-defined graphs. Here Zi (Ni,j,k) denotes the graph obtained by attaching a path of length i≥1 (three vertex-disjoint paths of lengths i,j,k≥1, respectively) to a triangle. Combining our results with a result in [Xiong (2014)], we prove that all 2-connected hourglass-free claw-free graphs G with one of the same forbidden subgraphs above (or additionally δ(G)≥3) are hamiltonian with the same excluded families of graphs. In particular, we prove that every 3-edge-connected claw-free hourglass-free graph that is N2,2,5-free or Z9-free is hamiltonian.
KW - Claw-free
KW - Forbidden subgraph
KW - Hamiltonian cycle
KW - Supereulerian
UR - http://www.scopus.com/inward/record.url?scp=85044600118&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2018.03.009
DO - 10.1016/j.disc.2018.03.009
M3 - Article
AN - SCOPUS:85044600118
SN - 0012-365X
VL - 341
SP - 1696
EP - 1707
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 6
ER -