On connencted \([g,f+1]\)-factors in graphs (Q2568495)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On connencted \([g,f+1]\)-factors in graphs
scientific article

    Statements

    On connencted \([g,f+1]\)-factors in graphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    27 June 2006
    0 references
    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 \textit{M. Cai} [Syst. Sci. Math. Sci. 8, No. 4, 364--368 (1995; Zbl 0851.05083)].
    0 references
    0 references
    \([g, f]\)-factors
    0 references
    Hamiltonian graphs
    0 references
    Kano's conjecture
    0 references
    0 references