Search

Let a and b be two positive integers such that a ≤ b and a ≡ b ( mod 2 ) . A graph F is an ( a , b ) -parity factor of a graph G if F is a spanning subgraph of G and for all vertices v ∈ V ( F ) , d F ( v ) ≡ b ( mod 2 ) and a ≤ d F ( v ) ≤ b . In this paper we prove that every connected graph G with n ≥ b ( a + b ) ( a + b + 2 ) ∕ ( 2 a ) vertices has an ( a , b ) -parity factor if n a is even, δ ( G ) ≥ ( b − a ) ∕ a + a , and for any two nonadjacent vertices u , v ∈ V ( G ) , max { d G ( u ) , d G ( v ) } ≥ a n a + b . This extends an earlier result of Nishimura (1992) and strengthens a result of Cai and Li (1998). [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V and let g , f : V → Z + be two functions such that g ≤ f. We say that G has all (g , f) -factors if G has an h -factor for every h : V → Z + such that g (v) ≤ h (v) ≤ f (v) for every v ∈ V and ∑ v ∈ V h (v) ≡ 0 (mod 2). Two decades ago, Niessen derived from Tutte's f -factor theorem a similar characterization for the property of graphs having all (g , f) -factors and asked whether there is a polynomial time algorithm for testing whether a graph G has all (g , f) -factors. (A characterization of graphs having all (g , f) -Factors, (Niessen, 1998).) In this paper, we show that it is NP-hard to determine whether a graph G has all (g , f) -factors, which gives a negative answer to the question of Niessen. [ABSTRACT FROM AUTHOR]

Let k ≥ 1 be an integer and G be a graph. Let k G denote the graph obtained from G by replacing each edge of G with k parallel edges. We say that G has all [ 1 , k ] -factors or all fractional [ 1 , k ] -factors if G has an h -factor or a fractional h -factor for every function h : V (G) → { 1 , 2 , ... , k } with h (V (G)) even. In this note, we come up with simple characterizations of a graph G such that k G has all [ 1 , k ] -factors or all fractional [ 1 , k ] -factors. These characterizations are extensions of Tutte's 1-Factor Theorem and Tutte's Fractional 1-Factor Theorem. [ABSTRACT FROM AUTHOR]