Connected \([k,k+1]\)-factors of graphs (Q1357718)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Connected \([k,k+1]\)-factors of graphs
scientific article

    Statements

    Connected \([k,k+1]\)-factors of graphs (English)
    0 references
    0 references
    16 June 1997
    0 references
    The author studies degree conditions for the existence of almost \(k\)-regular factors and connected \([k,k+1]\)-factors in graphs of order \(n\). He treats especially the case \(kn\) odd, continuing his previous work from [Syst. Sci. Math. Sci. 8, No. 4, 364-368 (1995; Zbl 0851.05083)]. He proves that if \(k\geq 3\) is odd, \(\varepsilon \in \{-1,+1\}\), and \(G\) is a connected graph of odd order \(n\geq 4k-3\) with minimum degree at least \(k\) and such that of any two nonadjacent vertices, at least one has degree larger than \({n\over 2}\), then \(G\) has a factor in which all vertices with one exception have degree \(k\), and the exceptional vertex has degree \(k+ \varepsilon\). The exceptional vertex can be chosen in advance from the vertices with degree larger than \({n \over 2}\). He also shows that by adding a properly chosen matching one can obtained a connected \([k,k+1]\)-factor, thereby proving a conjecture of Kano for \(kn\) odd.
    0 references
    0 references
    degree conditions
    0 references
    factors
    0 references
    matching
    0 references
    conjecture of Kano
    0 references
    0 references