Geodesic
Forbidden subgraphs for existences of (connected) 2-factors of a graph
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 211-224 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Clearly, having a 2-factor in a graph is a necessary condition for a graph to be hamiltonian, while having an even factor in graph is a necessary condition for a graph to have a 2-factor. In this paper, we completely characterize the forbidden subgraph and pairs of forbidden subgraphs that force a 2-connected graph admitting a 2-factor (a necessary condition) to be hamiltonian and a connected graph with an even factor (a necessary condition) to have a 2-factor, respectively. Our results show that these pairs of forbidden subgraphs become wider than those in Faudree, Gould and in Fujisawa, Saito, respectively, if we impose the two necessary conditions, respectively.
Keywords: forbidden subgraph, even factor, 2-factor, hamiltonian 
@article{DMGT_2023_43_1_a13,
     author = {Yang, Xiaojing and Xiong, Liming},
     title = {Forbidden subgraphs for existences of (connected) 2-factors of a graph},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {211--224},
     year = {2023},
     volume = {43},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a13/}
}
TY  - JOUR
AU  - Yang, Xiaojing
AU  - Xiong, Liming
TI  - Forbidden subgraphs for existences of (connected) 2-factors of a graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 211
EP  - 224
VL  - 43
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a13/
LA  - en
ID  - DMGT_2023_43_1_a13
ER  - 
%0 Journal Article
%A Yang, Xiaojing
%A Xiong, Liming
%T Forbidden subgraphs for existences of (connected) 2-factors of a graph
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 211-224
%V 43
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a13/
%G en
%F DMGT_2023_43_1_a13
Yang, Xiaojing; Xiong, Liming. Forbidden subgraphs for existences of (connected) 2-factors of a graph. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 211-224. http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a13/

[1] R.P. Anstee, An algorithmic proof of Tutte's f-factor theorem, J. Algorithms 6 (1985) 112–131. https://doi.org/10.1016/0196-6774(85)90022-7

[2] A.A. Bertossi, The edge Hamiltonian path problem is NP-complete, Inform. Process. Lett. 13 (1981) 157–159. https://doi.org/10.1016/0020-0190(81)90048-X

[3] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).

[4] Y. Egawa, Proof techniques for factor theorems, in: Horizons of Combinatorics, in: Bolyai Soc. Math. Stud. 17, (Springer, Berlin 2008) 67–78. https://doi.org/10.1007/978-3-540-77200-2_3

[5] J.R. Faudree, R.J. Faudree and Z. Ryjáček, Forbidden subgraphs that imply 2-factors, Discrete Math. 308 (2008) 1571–1582. https://doi.org/10.1016/j.disc.2007.04.014

[6] R. Faudree and R.J. Gould, Characterizing forbidden pairs for Hamiltonian properties, Discrete Math. 173 (1997) 45–60. https://doi.org/10.1016/S0012-365X(96)00147-1

[7] F. Fujisawa and A. Saito, A pair of forbidden subgraphs and 2-factors, Combin. Probab. Comput. 21 (2012) 149–158. https://doi.org/10.1017/S0963548311000514

[8] R. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, (Plenum Press, New York 1972) 85–103. https://doi.org/10.1007/978-1-4684-2001-2_9

[9] R. Karp, On the computational complexity of combinatorial problems, Networks 5 (1975) 45–68. https://doi.org/10.1002/net.1975.5.1.45

[10] X. Yang, J. Du and L. Xiong, Forbidden subgraphs for supereulerian and Hamiltonian graphs, Discrete Appl. Math 288 (2021) 192–200. https://doi.org/10.1016/j.dam.2020.08.034