2012/10/21 by Hongliang Lu, David G. L. Wang, Lu, Hongliang +3
Computer Science · Mathematics · #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C75
paper · pdf · doi:10.48550/arxiv.1210.5683
10 pages
arxiv created 2012/10/21 · openalex publication_date 2012/10/21 · arxiv updated 2012/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph, and H\colon V(G)→ 2^ℕ a set function associated with G. A spanning subgraph F of G is called an H-factor if the degree of any vertex v in F belongs to the set H(v). This paper contains two results on the existence of H-factors in regular graphs. First, we construct an r-regular graph without some given H^*-factor. In particular, this gives a negative answer to a problem recently posed by Akbari and Kano. Second, by using Lovász's characterization theorem on the existence of (g, f)-factors, we find a sharp condition for the existence of general H-factors in \r, r+1\-graphs, in terms of the maximum and minimum of H. The result reduces to Thomassen's theorem for the case that H(v) consists of the same two consecutive integers for all vertices v, and to Tutte's theorem if the graph is regular in addition.