Geodesic
Forbidden Subgraphs for Collapsible Graphs and Supereulerian Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 417-442.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: forbidden subgraph, supereulerian, collapsible 
@article{DMGT_2022_42_2_a6,
     author = {Liu, Xia and Xiong, Liming},
     title = {Forbidden {Subgraphs} for {Collapsible} {Graphs} and {Supereulerian} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {417--442},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a6/}
}
TY  - JOUR
AU  - Liu, Xia
AU  - Xiong, Liming
TI  - Forbidden Subgraphs for Collapsible Graphs and Supereulerian Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 417
EP  - 442
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a6/
LA  - en
ID  - DMGT_2022_42_2_a6
ER  - 
%0 Journal Article
%A Liu, Xia
%A Xiong, Liming
%T Forbidden Subgraphs for Collapsible Graphs and Supereulerian Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 417-442
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a6/
%G en
%F DMGT_2022_42_2_a6
Liu, Xia; Xiong, Liming. Forbidden Subgraphs for Collapsible Graphs and Supereulerian Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 417-442. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a6/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory in: Grad. Texts in Math. 244 (Springer-Verlag, London, 2008).

[2] J. Brousek, Z. Ryjáček and O. Favaron, Forbidden subgraphs, hamiltonicity and closure in claw-free graphs, Discrete Math. 196 (1999) 29–50. https://doi.org/10.1016/S0012-365X(98)00334-3

[3] R. Čada, K. Ozeki, L. Xiong and K. Yoshimoto, Pairs of forbidden subgraphs and 2 -connected supereulerian graphs, Discrete Math. 341 (2018) 1696–1707. https://doi.org/10.1016/j.disc.2018.03.009

[4] P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44. https://doi.org/10.1002/jgt.3190120105

[5] P.A. Catlin, Supereulerian graphs, collapsible graphs, and four-cycles, Congr. Numer. 58 (1987) 233–246.

[6] H.-J. Lai, Graph whose edges are in small cycles, Discrete Math. 94 (1991) 11–22. https://doi.org/10.1016/0012-365X(91)90302-I

[7] H.-J. Lai, Supereulerian graphs and excluded induced minors, Discrete Math. 146 (1995) 133–143. https://doi.org/10.1016/0012-365X(94)00159-7

[8] X. Liu, H. Lin and L. Xiong, Forbidden subgraphs and weak locally connected graphs, Graphs Combin. 34 (2018) 1671–1690. https://doi.org/10.1007/s00373-018-1952-2

[9] S. Lv and L. Xiong, Forbidden pairs for spanning ( closed ) trails, Discrete Math. 340 (2017) 1012–1018. https://doi.org/10.1016/j.disc.2017.01.009

[10] S. Lv and L. Xiong, Erratum to “Forbidden pairs for spanning ( closed ) trails” [ Discrete Math. 340 ( 2017 ) 1012–1018 ], Discrete Math. 341 (2018) 1192–1193. https://doi.org/10.1016/j.disc.2017.11.020

[11] Z. Ryjáček, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217–224. https://doi.org/10.1006/jctb.1996.1732

[12] S. Wang and L. Xiong, Forbidden set of induced subgraphs for 2 -connected supereulerian graphs, Discrete Math. 340 (2017) 2792–2797. https://doi.org/10.1016/j.disc.2017.08.006