1. Forbidden Pairs for Connected Even Factors in Supereulerian Graphs.
- Author
-
Wang, Panpan and Xiong, Liming
- Abstract
A graph is called supereulerian if it has a spanning eulerian subgraph. A connected even [2, 2s]-factor of a graph G is a connected factor with all vertices of even degree i (i ∈ { 2 , 4 , … , 2 s }) , where s ≥ 1 is an integer. Let W s , t be the graph obtained from vertex-disjoint s K 2 and (t + 1) K 1 by adding all possible edges between exactly one K 1 and the remaining graphs s K 2 and t K 1 . When s = t = 1 , W 1 , 1 is Z 1 . In this paper, we show that for any positive integer k ≤ 4 and 2 ≤ i ≤ k + 1 , every connected supereulerian H -free graph of order at least 6 contains a connected even [2, 2k]-factor if and only if H satisfies the following condition. H ≼ { { K 1 , 2 k + 2 , Z 1 } , { K 1 , k + i , W k + 3 - i , 0 } , { K 1 , k + i , W k + 2 - i , i - 1 } }.
And when k = 5 , 6 , we give some relevant results. We also show that for positive integers k, 2 ≤ i ≤ k + 1 and H ≼ { { K 1 , 2 k + 2 , Z 1 } , { K 1 , k + i , W k + 3 - i , 0 } } , if G is supereulerian H -free graph of order at least 6, then G contains a connected even [2, 2k]-factor. Our results extend the result of Yang et al. (Discrete Appl Math 288:192–200, 2021) and Duan et al. (Ars Comb 115:385–389, 2014). [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF