An Extension of Cui–Kano's Characterization on Graph Factors1. Issue 1 (4th February 2015)

• Record Type: Journal Article
• Authors: Lu, Hongliang
• Is Part Of: Journal of graph theory. Volume 81:Issue 1(2016)
• Page Start: 5
• Page End: 15
• Publication Date: 2015-02-04
• Subjects: gap -- H‐factor -- odd factor; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21856
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: Let G be a graph with vertex set V ( G ) and let H : V ( G ) → 2 N be a set function associated with G . An H ‐factor of graph G is a spanning subgraphs F such that d 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 let H 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, where H 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.