Forbidden Pairs for Connected Even Factors in Supereulerian Graphs

Panpan Wang, Liming Xiong*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 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).

Original languageEnglish
Article number64
JournalGraphs and Combinatorics
Volume39
Issue number4
DOIs
Publication statusPublished - Aug 2023

Keywords

  • Connected even factor
  • Hamiltonian
  • K-free graph
  • Supereulerian

Fingerprint

Dive into the research topics of 'Forbidden Pairs for Connected Even Factors in Supereulerian Graphs'. Together they form a unique fingerprint.

Cite this