DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

X. Liu , L. Xiong

Title:

Forbidden subgraphs for collapsible graphs and supereulerian graphs

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-04-13, Revised: 2019-11-13, Accepted: 2019-11-17, https://doi.org/10.7151/dmgt.2270

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 $Z_3$-free if and only if it is $K_3$-free, where $Z_{i}$ is a graph obtained by identifying a vertex of a $K_{3}$ with an end-vertex of a $P_{i+1}$.

Keywords:

forbidden subgraph, supereulerian, collapsible

PDF
Close