TY - JOUR
T1 - Forbidden Pairs for Connected Even Factors in Supereulerian Graphs
AU - Wang, Panpan
AU - Xiong, Liming
N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer Nature Japan KK, part of Springer Nature.
PY - 2023/8
Y1 - 2023/8
N2 - 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 Ws,t be the graph obtained from vertex-disjoint sK2 and (t+ 1 ) K1 by adding all possible edges between exactly one K1 and the remaining graphs sK2 and tK1 . When s= t= 1 , W1 , 1 is Z1 . 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≼{{K1,2k+2,Z1},{K1,k+i,Wk+3-i,0},{K1,k+i,Wk+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≼ { { K1,2k+2, Z1} , { K1,k+i, Wk+3-i,} } , 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).
AB - 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 Ws,t be the graph obtained from vertex-disjoint sK2 and (t+ 1 ) K1 by adding all possible edges between exactly one K1 and the remaining graphs sK2 and tK1 . When s= t= 1 , W1 , 1 is Z1 . 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≼{{K1,2k+2,Z1},{K1,k+i,Wk+3-i,0},{K1,k+i,Wk+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≼ { { K1,2k+2, Z1} , { K1,k+i, Wk+3-i,} } , 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).
KW - Connected even factor
KW - Hamiltonian
KW - K-free graph
KW - Supereulerian
UR - http://www.scopus.com/inward/record.url?scp=85160908023&partnerID=8YFLogxK
U2 - 10.1007/s00373-023-02658-4
DO - 10.1007/s00373-023-02658-4
M3 - Article
AN - SCOPUS:85160908023
SN - 0911-0119
VL - 39
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
IS - 4
M1 - 64
ER -