An Extension of Cui-Kano's Characterization Problem on Graph Factors

Abstract

Let $G$ be a graph with vertex set $V(G)$ and let $H:V(G)\to 2^N$ be a set function associating with $G$. An $H$-factor of graph $G$ is a spanning subgraphs $F$ such that $$d_F(v)\in H(v)4emfor\; everyv\in V(G).$$ Let $f:V(G)\to N$ be an even integer-valued function such that $f\ge 4$ and let $H_f(v)=\{1,3,...,f(v)-1,f(v)\}$ for $v\in V(G)$. In this paper, we investigate $H_f$-factors of graphs $G$ 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)$] $o(G-S)\le f(S)$ for all $S\subseteq V(G)$; [$(ii)$] $|V(G)|$ is odd, $d_G(v)\ge f(v)-1$ for all $v\in V(G)$ and $o(G-S)\le f(S)$ for all $\varnothing \ne S\subseteq V(G)$. As a corollary, we show that if a graph $G$ with odd order and minimum degree $2n-1$ satisfies $$o(G-S)\le 2n|S|4emforall\varnothing \ne S\subseteq V(G),$$ then $G$ contains an $H_n$-factor. In particular, we make progress on the characterization problem for a special family of graphs proposed by Akiyama and Kano.