On Cui-Kano's Characterization Problem on Graph Factors

H. L. Lu; David G. L. Wang

paper

On Cui-Kano's Characterization Problem on Graph Factors

arXiv:1109.4863

Abstract

An $H_{n}$ -factor of a graph $G$ is defined to be a spanning subgraph $F$ of $G$ such that each vertex has degree belonging to the set ${1, 3, 5, ..., 2 n - 1, 2 n}$ in $F$ . In this paper, we investigate $H_{n}$ -factors of graphs by using Lovász's structural descriptions to the degree prescribed subgraph problem. We find some sufficient conditions for the existence of an $H_{n}$ -factor of a graph. In particular, we make progress on the characterization problem for a special family of graphs proposed by Cui and Kano in 1988.

11 pages