An Extension of Cui–Kano's Characterization on Graph Factors

Let G be a graph with vertex set V ( G ) and let H : V ( G ) → 2 Nbe a set function associated with G . An H ‐factor of graph G is a spanning subgraphs  F such thatd F ( v ) ∈ H ( v )for every v ∈ V ( G ) . Let f : V ( G ) → N be an even integer‐valued function such that f ≥ 4 and letH f ( v ) = { 1 , 3 , ... , f ( v ) − 1 , f ( v ) }for v ∈ V ( G ) . In this article, we investigate H f ‐factors of graphs by using Lovász's structural descriptions. Let o ( G ) denote the number of odd components of G . We show that if one of the following conditions holds, then G contains an H f ‐factor. (i) | V ( G ) | is even and o ( G − S ) ≤ f ( S ) for all S ⊆ V ( G ) ; (ii) | V ( G ) | is odd,d G ( v ) ≥ f ( v ) − 1 for all v ∈ V ( G ) and o ( G − S ) ≤ f ( S ) for all ∅ ≠ S ⊆ V ( G ) . As a corollary, we show that if a graph G of odd order with minimum degree at least 2 n − 1 satisfies o ( G − S ) ≤ 2 n | S |for all ∅ ≠ S ⊆ V ( G ) , then G contains an H n ‐factor, whereH n = { 1 , 3 , ... , 2 n − 1 , 2 n } . In particular, we make progress on the characterization problem for a special family of graphs proposed by Akiyama and Kano.