A short proof of Kundu's k-factor theorem

DOI10.1016/0012-365X(88)90070-2MaRDI QIDQ1106246zbMATH OpenOpenAlexFDO

Authors William Y. C. Chen

Publication date 1988

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(88)90070-2

zbMATH Keywords

graphical degree sequencegraphical sequencesk-factor Theorem

Mathematics Subject Classification ID

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

Review text

This note gives a very short proof of the k-factor theorem due to \textit{S. Kundu} [Discrete Math. 6, 367-376 (1973; Zbl 0278.05115)]: Theorem. Let \((d_ 1,d_ 2,...,d_ n)\) and \((d_ 1-k_ 1,d_ 2-k_ 2,...,d_ n-k_ n)\) be two graphical sequences satisfying \(k\leq k_ i\leq k+1\), \(1\leq i\leq n\), for some \(k\geq 0\). Then there exists a graph \(G=(V,E)\) which contains a subgraph F such that \(d_ G(v_ i)=d_ i\) and \(d_ F(v_ i)=k_ i\) for all \(v_ i\in \{v_ 1,v_ 2,...,v_ n\}=V(G).\) The above theorem was conjectured by \textit{A. R. Rao} and \textit{S. B. Rao} [J. Comb. Theory, Ser. B 13, 185-191 (1972; Zbl 0224.05126)] for the case \(k_ i=k\) for all i, and independently by B. Grünbaum for the special case \(k_ i=1\) for all i. The proof in this note readily extends to derive the generalizations of the k-factor Theorem obtained by Kundu, Kleitman and Wang, and also provides us with a simple algorithm for constructing the graph G in the theorem. The results for directed graphs may be proved similarly. \{Remark: Lemma 1 is not really necessary in the proof, but it is of some independent interest.\}

Recommendations

• Degree sequences and the existence of k-factors
• Minimum degree of bipartite graphs and the existence of k-factors
• Minimum degree of a graph and the existence of k-factors
• One-factors and \(k\)-factors
• Neighborhood conditions and k-factors

Cites work

• Algorithms for constructing graphs and digraphs with given valences and factors
• Factors and factorizations of graphs—a survey
• Generalizations of the k-factor theorem
• On factorable degree sequences
• Parallel concepts in graph theory
• The k-factor conjecture is true
• Valencies of graphs with 1-factors

Cited in

(17)

• On joint realization of (0,1) matrices
• A quick proof that \(K_{10}\neq{}P+P+P\)
• Degree sequences and the existence of k-factors
• Navigating between packings of graphic sequences
• On factorable bigraphic pairs
• Packing tree degree sequences
• The structure matrix of the class of r-multigraphs with a prescribed degree sequence
• Half-regular factorizations of the complete bipartite graph
• Packing of graphic n-tuples
• New results on degree sequences of uniform hypergraphs
• Graphic Sequences Have Realizations Containing Bisections of Large Degree
• Multi-switch: a tool for finding potential edge-disjoint 1-factors
• A note on packing of graphic \(n\)-tuples
• Maximally edge‐connected realizations and Kundu's k k‐factor theorem
• Realizing disjoint degree sequences of span at most two: a tractable discrete tomography problem
• On a conjecture that strengthens Kundu's k-factor theorem
• Graphic approximation of integer sequences

This page was built for publication: A short proof of Kundu's k-factor theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1106246)