Forbidden set of induced subgraphs for 2-connected supereulerian graphs

Shipeng Wang, Liming Xiong*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)2792-2797
Number of pages6
JournalDiscrete Mathematics
Volume340
Issue number12
DOIs
Publication statusPublished - Dec 2017

Keywords

  • Claw-free
  • Forbidden set
  • Induced subgraph
  • Supereulerian

Fingerprint

Dive into the research topics of 'Forbidden set of induced subgraphs for 2-connected supereulerian graphs'. Together they form a unique fingerprint.

Cite this