Forbidden Subgraphs for Collapsible Graphs and Supereulerian Graphs

Xia Liu, Liming Xiong

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

In this paper, we completely characterize the connected forbidden subgraphs and pairs of connected forbidden subgraphs that force a 2-edge-connected (2-connected) graph to be collapsible. In addition, the characterization of pairs of connected forbidden subgraphs that imply a 2-edge-connected graph of minimum degree at least three is supereulerian will be considered. We have given all possible forbidden pairs. In particular, we prove that every 2-edge-connected noncollapsible (or nonsupereulerian) graph of minimum degree at least three is Z3-free if and only if it is K3-free, where Zi is a graph obtained by identifying a vertex of a K3 with an end-vertex of a Pi+1.

Original languageEnglish
Pages (from-to)417-442
Number of pages26
JournalDiscussiones Mathematicae - Graph Theory
Volume42
Issue number2
DOIs
Publication statusPublished - 1 May 2022

Keywords

  • collapsible
  • forbidden subgraph
  • supereulerian

Fingerprint

Dive into the research topics of 'Forbidden Subgraphs for Collapsible Graphs and Supereulerian Graphs'. Together they form a unique fingerprint.

Cite this

Liu, X., & Xiong, L. (2022). Forbidden Subgraphs for Collapsible Graphs and Supereulerian Graphs. Discussiones Mathematicae - Graph Theory, 42(2), 417-442. https://doi.org/10.7151/dmgt.2270