Degree sequences and the existence of k-factors

D. Bauer, Haitze J. Broersma, J. van den Heuvel, N. Kahl, E. Schmeichel

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
18 Downloads (Pure)

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.
Original languageUndefined
Pages (from-to)149-166
Number of pages18
JournalGraphs and combinatorics
Volume28
Issue number2
DOIs
Publication statusPublished - Mar 2012

Keywords

  • k-Factor
  • EWI-22742
  • MSC-05C
  • Best monotone condition
  • METIS-296437
  • IR-83470
  • Degree sequence

Cite this

Bauer, D., Broersma, H. J., van den Heuvel, J., Kahl, N., & Schmeichel, E. (2012). Degree sequences and the existence of k-factors. Graphs and combinatorics, 28(2), 149-166. https://doi.org/10.1007/s00373-011-1044-z
Bauer, D. ; Broersma, Haitze J. ; van den Heuvel, J. ; Kahl, N. ; Schmeichel, E. / Degree sequences and the existence of k-factors. In: Graphs and combinatorics. 2012 ; Vol. 28, No. 2. pp. 149-166.
@article{314a3ce8de1343698621781b8544efbc,
title = "Degree sequences and the existence of k-factors",
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{\'a}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 = "k-Factor, EWI-22742, MSC-05C, Best monotone condition, METIS-296437, IR-83470, Degree sequence",
author = "D. Bauer and Broersma, {Haitze J.} and {van den Heuvel}, J. and N. Kahl and E. Schmeichel",
note = "eemcs-eprint-22742",
year = "2012",
month = "3",
doi = "10.1007/s00373-011-1044-z",
language = "Undefined",
volume = "28",
pages = "149--166",
journal = "Graphs and combinatorics",
issn = "0911-0119",
publisher = "Springer",
number = "2",

}

Bauer, D, Broersma, HJ, van den Heuvel, J, Kahl, N & Schmeichel, E 2012, 'Degree sequences and the existence of k-factors' Graphs and combinatorics, vol. 28, no. 2, pp. 149-166. https://doi.org/10.1007/s00373-011-1044-z

Degree sequences and the existence of k-factors. / Bauer, D.; Broersma, Haitze J.; van den Heuvel, J.; Kahl, N.; Schmeichel, E.

In: Graphs and combinatorics, Vol. 28, No. 2, 03.2012, p. 149-166.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Degree sequences and the existence of k-factors

AU - Bauer, D.

AU - Broersma, Haitze J.

AU - van den Heuvel, J.

AU - Kahl, N.

AU - Schmeichel, E.

N1 - eemcs-eprint-22742

PY - 2012/3

Y1 - 2012/3

N2 - 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.

AB - 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.

KW - k-Factor

KW - EWI-22742

KW - MSC-05C

KW - Best monotone condition

KW - METIS-296437

KW - IR-83470

KW - Degree sequence

U2 - 10.1007/s00373-011-1044-z

DO - 10.1007/s00373-011-1044-z

M3 - Article

VL - 28

SP - 149

EP - 166

JO - Graphs and combinatorics

JF - Graphs and combinatorics

SN - 0911-0119

IS - 2

ER -