On connencted \([g,f+1]\)-factors in graphs. (English) Zbl 1090.05058

Li, Guojun; Xu, Ying; Chen, Chuanping; Liu, Zhenhong

Combinatorica 25, No. 4, 393-405 (2005).

Let \(G=(V(G), E(G))\) be a graph and \(g\) and \(f\) positive integral functions on \(V(G)\) such that \(2 \leq g(v) \leq f(v) \leq d_G(v)\) for all \(v\). The spanning subgraph \(F\) is a \([g, f]\)-factor of \(G\) if \(g(v) \leq d_F(v) \leq f(v)\) for all \(v\). The main result of the paper is that if \(G\) has both a \([g, f]\)-factor and a Hamiltonian path, then \(G\) has a connected \([g, f+1]\)-factor. It is a generalization of Kano’s conjecture first solved by M. Cai [Syst. Sci. Math. Sci. 8, No. 4, 364–368 (1995; Zbl 0851.05083)].

Reviewer: András Pluhár (Szeged)

MSC:

05C70

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

\([g, f]\)-factors; Hamiltonian graphs; Kano’s conjecture