Mathematics – Combinatorics
Scientific paper
2009-12-15
Mathematics
Combinatorics
19 pages
Scientific paper
We consider sufficient conditions for a degree sequence $\pi$ to be forcibly $k$-factor graphical. We note that previous work on degrees and factors has focused primarily on finding conditions for a degree sequence to be potentially $k$-factor graphical. We first give a theorem for $\pi$ to be forcibly 1-factor graphical and, more generally, forcibly graphical with deficiency at most $\beta\ge0$. These theorems are equal in strength to Chv\'atal's well-known hamiltonian theorem, i.e., the best monotone degree condition for hamiltonicity. We then give an equally strong theorem for $\pi$ to be forcibly 2-factor graphical. Unfortunately, the number of nonredundant conditions that must be checked increases significantly in moving from $k=1$ to $k=2$, and we conjecture that the number of nonredundant conditions in a best monotone theorem for a $k$-factor will increase superpolynomially in $k$. This suggests the desirability of finding a theorem for $\pi$ to be forcibly $k$-factor graphical whose algorithmic complexity grows more slowly. In the final section, we present such a theorem for any $k\ge2$, based on Tutte's well-known factor theorem. While this theorem is not best monotone, we show that it is nevertheless tight in a precise way, and give examples illustrating this tightness.
Bauer David
Broersma H. J.
den Heuvel Jan van
Kahl N.
Schmeichel E.
No associations
LandOfFree
Degree Sequences and the Existence of $k$-Factors does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Degree Sequences and the Existence of $k$-Factors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Degree Sequences and the Existence of $k$-Factors will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-305757