Pairs of forbidden subgraphs and 2-connected supereulerian graphs

Roman Čada, Kenta Ozeki, Liming Xiong*, Kiyoshi Yoshimoto

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)1696-1707
Number of pages12
JournalDiscrete Mathematics
Volume341
Issue number6
DOIs
Publication statusPublished - Jun 2018

Keywords

  • Claw-free
  • Forbidden subgraph
  • Hamiltonian cycle
  • Supereulerian

Fingerprint

Dive into the research topics of 'Pairs of forbidden subgraphs and 2-connected supereulerian graphs'. Together they form a unique fingerprint.

Cite this