Forbidden Subgraphs for Collapsible Graphs and Supereulerian Graphs

Discussiones Mathematicae Graph Theory

Liu Xia¹  Xiong Liming¹ 

[1] School of Mathematics and Statistics, Beijing Key Laboratory on MCAACI, Beijing Institute of Technology, Beijing100081, P.R. ofChina;

关键词: forbidden subgraph;    supereulerian;    collapsible;    05c38;    05c45;   

DOI  :  10.7151/dmgt.2270

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown