Research ArticleOpen AccessGoogle Scholar indexed
Forbidden Subgraphs for the Existence of an Even Factor with Exactly Two Components in 2-Edge-Connected Graphs
Department of Mathematics and Statistics, Qinghai Minzu University, Xining, China
Department of Mathematics and Statistics, Qinghai Minzu University, Xining, China
- 1 Department of Mathematics and Statistics, Qinghai Minzu University, Xining, China
- 2 Department of Mathematics and Statistics, Qinghai Minzu University, Xining, China
Applied Mathematics·Volume 17 (2026)·Pages 39–53·Published 20 January 2026·DOI10.4236/am.2026.171004
Copy link · social · email
Abstract
In this paper, we mainly consider characterize all the pairs { R , S } of 2-edge-connected graphs G such that every { R , S } -free graph G has an even factor with exactly two components if and only if δ ( G ) ≥ 2 and every odd branch-bond of G has an edge branch.
KeywordsEven FactorOdd Branch-BondForbidden PairEdge-Branch
- Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan, Elsevier.
- Karp, R.M. (1972) Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. and Bohlinger, J.D., Eds., Complexity of Computer Computations , Springer, 85-103. https://doi.org/10.1007/978-1-4684-2001-2_9
- Pulleyblank, W.R. (1979) A Note on Graphs Spanned by Eulerian Graphs. Journal of Graph Theory , 3, 309-310. https://doi.org/10.1002/jgt.3190030316
- Bedrossian, P. (1991) Forbidden Subgraph and Minimum Degree Conditions for Hamiltonicity. Ph.D. Thesis, Memphis State University.
- Faudree, R.J. and Gould, R.J. (1997) Characterizing Forbidden Pairs for Hamiltonian Properties. Discrete Mathematics , 173, 45-60. https://doi.org/10.1016/s0012-365x(96)00147-1
- Lai, H. (1995) Supereulerian Graphs and Excluded Induced Minors. Discrete Mathematics , 146, 133-143. https://doi.org/10.1016/0012-365x(94)00159-7
- Tutte, W.T. (1947) The Factorization of Linear Graphs. Journal of the London Mathematical Society , 1, 107-111. https://doi.org/10.1112/jlms/s1-22.2.107
- Gallai, T. (1950) On Factorisation of Graphs. Acta Mathematica Academiae Scientiarum Hungaricae , 1, 133-153. https://doi.org/10.1007/bf02022560
- Plummer, M.D. (2007) Graph Factors and Factorization: 1985-2003: A Survey. Discrete Mathematics , 307, 791-821. https://doi.org/10.1016/j.disc.2005.11.059
- Xiong, L. (2008) The Existence of Even Factors in Iterated Line Graphs. Discrete Mathematics , 308, 5891-5894. https://doi.org/10.1016/j.disc.2007.10.043
- Xiong, L. (2017) Characterization of Forbidden Subgraphs for the Existence of Even Factors in a Graph. Discrete Applied Mathematics , 223, 135-139. https://doi.org/10.1016/j.dam.2017.02.015
- Lv, S. and Xiong, L. (2017) Forbidden Pairs for Spanning (Closed) Trails. Discrete Mathematics , 340, 1012-1018. https://doi.org/10.1016/j.disc.2017.01.009
- Yang, X., Du, J. and Xiong, L. (2021) Forbidden Subgraphs for Supereulerian and Hamiltonian Graphs. Discrete Applied Mathematics , 288, 192-200. https://doi.org/10.1016/j.dam.2020.08.034