Article in volume
Authors:
Title:
Forbidden subgraphs for existences of (connected) 2-factors of a graph
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 211-224
Received: 2020-02-14 , Revised: 2020-09-01 , Accepted: 2020-09-01 , Available online: 2020-10-16 , https://doi.org/10.7151/dmgt.2366
Abstract:
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
References:
- 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 - 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 - J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).
- 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 - 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 - 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 - 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 - 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 - R. Karp, On the computational complexity of combinatorial problems, Networks 5 (1975) 45–68.
https://doi.org/10.1002/net.1975.5.1.45 - 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
Close