A Degree Condition for Graphs Having All (a,b)-Parity Factors

2020/09/07 by Haodong Liu, Hongliang Lu, Liu, Haodong +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.2009.03032

openalex publication_date 2020/09/07 · arxiv created 2020/09/08 · arxiv updated 2020/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let a and b be positive integers such that a≤ b and a≡ b\pmod 2. We say that G has all (a, b)-parity factors if G has an h-factor for every function h: V(G) → \a,a+2,…,b-2,b\ with b|V(G)| even and h(v)≡ b\pmod 2 for all v∈ V(G). In this paper, we prove that every graph G with n≥ 3(b+1)(a+b) vertices has all (a,b)-parity factors if δ(G)≥ (b²-b)/a, and for any two nonadjacent vertices u,v ∈ V(G), max\d_G(u),d_G(v)\≥ (bn)/(a+b). Moreover, we show that this result is best possible in some sense.

Related

• A Degree Condition for a Graph to have (a,b)-Parity Factors
• A characterization for graphs having strong parity factors
• Eigenvalues and parity factors in graphs
• A spectral radius condition for a graph to have (a,b)-parity factors
• A Note On Edge Connectivity and Parity Factor