Geodesic
Forbidden Subgraphs for Collapsible Graphs and Supereulerian Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 417-442 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2022},
     volume = {42},
     number = {2},
     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
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
%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