Article ID Journal Published Year Pages File Type
4648414 Discrete Mathematics 2009 10 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,