Connected \([k,k+1]\)-factors of graphs
type: Item
instance of: scholarly article
title: Connected \([k,k+1]\)-factors of graphs
zbMATH Open document ID: 0879.05061
DOI: 10.1016/0012-365X(95)00328-T
author: Mao-Cheng Cai
published in: Discrete Mathematics
publication date: 1997-06-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1021668
zbMATH Keywords: degree conditions
zbMATH Keywords: factors
zbMATH Keywords: matching
zbMATH Keywords: conjecture of Kano
reviewed by: Peter Brass
MaRDI profile type: Publication
cites work: Q5422499
cites work: Q4887674
cites work: An Ore-type condition for the existence of \(k\)-factors in graphs
cites work: Minimum degree of a graph and the existence of k-factors
cites work: BINDING NUMBERS OF GRAPHS AND THE EXISTENCE OF k-FACTORS
cites work: A degree condition for the existence ofk-factors
cites work: The Factors of Graphs
cites work: Graph factors
full work available at URL: 0012-365x(95)00328-t
OpenAlex ID: W2051773042
description: scientific article; zbMATH DE number 1021668