×

zbMATH — the first resource for mathematics

On connencted \([g,f+1]\)-factors in graphs. (English) Zbl 1090.05058
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)].

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI