Graphs Containing Every 2-Factor

Research output: Contribution to journalArticlepeer-review

Abstract

For a graph G, let σ 2 = min {d(u) + d(υ): uυ E(G)}. We prove that every n-vertex graph G with σ 2(G) ≥ 4n/3 - 1 contains each 2-regular n-vertex graph. This extends a theorem due to Aigner and Brandt and to Alon and Fisher.

Original languageEnglish (US)
Pages (from-to)687-716
Number of pages30
JournalGraphs and Combinatorics
Volume28
Issue number5
DOIs
StatePublished - Sep 1 2012

Keywords

  • 2-factors
  • Graph packing
  • Ore-type degree conditions

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Graphs Containing Every 2-Factor'. Together they form a unique fingerprint.

Cite this