Article in volume
Authors:
Title:
Forbidden subgraphs for collapsible graphs and supereulerian graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(2) (2022) 417-442
Received: 2019-04-13 , Revised: 2019-11-17 , Accepted: 2019-11-17 , Available online: 2021-12-16 , 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
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory in: Grad. Texts in Math. 244 (Springer-Verlag, London, 2008).
- 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 - 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 - 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 - P.A. Catlin, Supereulerian graphs, collapsible graphs, and four-cycles, Congr. Numer. 58 (1987) 233–246.
- 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 - 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 - 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 - 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 - 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 - 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 - 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
Close