Degree Sequences and the Existence of <Emphasis Type="Italic">k</Emphasis>-Factors |
| |
Authors: | D?Bauer H?J?Broersma Email author" target="_blank">J?van den?HeuvelEmail author N?Kahl E?Schmeichel |
| |
Institution: | 1.Department of Mathematical Sciences,Stevens Institute of Technology,Hoboken,USA;2.Department of Computer Science,Durham University,Durham,UK;3.Department of Applied Mathematics,University of Twente,Enschede,The Netherlands;4.Department of Mathematics,London School of Economics,London,UK;5.Department of Mathematics and Computer Science,Seton Hall University,South Orange,USA;6.Department of Mathematics,San José State University,San José,USA |
| |
Abstract: | We consider sufficient conditions for a degree sequence π 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 π to be forcibly 1-factor graphical and, more generally, forcibly graphical with deficiency at most β ≥ 0. These theorems are equal in strength to Chvátal’s well-known hamiltonian theorem, i.e., the best monotone degree condition
for hamiltonicity. We then give an equally strong theorem for π 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 π to be forcibly k-factor graphical whose algorithmic complexity grows more slowly. In the final section, we present such a theorem for any
k ≥ 2, 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|