Ore-type conditions implying 2-factors consisting of short cycles

Research output: Contribution to journalArticlepeer-review

Abstract

For every graph G, let σ2 (G) = min {d (x) + d (y) : x y ∉ E (G)}. The main result of the paper says that every n-vertex graph G with σ2 (G) ≥ frac(4 n, 3) - 1 contains each spanning subgraph H all whose components are isomorphic to graphs in {K1, K2, C3, K4-, C5+}. This generalizes the earlier results of Justesen, Enomoto, and Wang, and is a step towards an Ore-type analogue of the Bollobás-Eldridge-Catlin Conjecture.

Original languageEnglish (US)
Pages (from-to)4762-4771
Number of pages10
JournalDiscrete Mathematics
Volume309
Issue number14
DOIs
StatePublished - Jul 28 2009

Keywords

  • Degree conditions
  • Packing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Ore-type conditions implying 2-factors consisting of short cycles'. Together they form a unique fingerprint.

Cite this