Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648414 | Discrete Mathematics | 2009 | 10 Pages |
Abstract
For every graph GG, let σ2(G)=min{d(x)+d(y):xy∉E(G)}. The main result of the paper says that every nn-vertex graph GG with σ2(G)≥4n3−1 contains each spanning subgraph HH 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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Alexandr V. Kostochka, Gexin Yu,