1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Forbidden Subgraphs for Existences of (Connected) 2-Factors of a Graph

Published Online: 24 Nov 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 14 Feb 2020
Accepted: 01 Sep 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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

MSC 2010

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

[2] A.A. Bertossi, The edge Hamiltonian path problem is NP-complete, Inform. Process. Lett. 13 (1981) 157–159. doi:10.1016/0020-0190(81)90048-X10.1016/0020-0190(81)90048-XSearch in Google Scholar

[3] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).10.1007/978-1-84628-970-5Search in Google Scholar

[4] Y. Egawa, Proof techniques for factor theorems, in: Horizons of Combinatorics, Bolyai Soc. Math. Stud. 17 (Springer, Berlin, 2008) 67–78.10.1007/978-3-540-77200-2_3Search in Google Scholar

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

[6] R. Faudree and R.J. Gould, Characterizating forbidden pairs for Hamiltonian properties, Discrete Math 173 (1997) 45–60. doi:10.1016/S0012-365X(96)00147-110.1016/S0012-365X(96)00147-1Search in Google Scholar

[7] F. Fujisawa and A. Saito, A pair of forbidden subgraphs and 2-factors, Combin. Probab. Comput. 21 (2012) 149–158. doi:10.1017/S096354831100051410.1017/S0963548311000514Search in Google Scholar

[8] R. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, Plenum Press, New York, (1972) 85–103.Search in Google Scholar

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

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo