Article ID Journal Published Year Pages File Type
6423446 Discrete Mathematics 2012 8 Pages PDF
Abstract

A graph is packable if it is a subgraph of its complement. The following statement was conjectured by Faudree, Rousseau, Schelp and Schuster in 1981: every non-star graph G with girth at least 5 is packable.The conjecture was proved by Faudree et al. with the additional condition that G has at most 65n−2 edges. In this paper, for each integer k≥3, we prove that every non-star graph with girth at least 5 and at most 2k−1kn−αk(n) edges is packable, where αk(n) is o(n) for every k. This implies that the conjecture is true for sufficiently large planar graphs.

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