Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A note on packing graphs without cycles of length up to five. | A note on packing graphs without cycles of length up to five Agnieszka Gorlich Andrzej Zak University of Science and Technology AGH Al. Mickiewicza 30 30-059 Kraków Poland forys zakandrz @ Submitted Feb 3 2009 Accepted Oct 20 2009 Published Oct 26 2009 Mathematics Subject Classification 05C70 Abstract The following statement was conjectured by Faudree Rousseau Schelp and Schuster if a graph G is a non-star graph without cycles of length m 4 then G is a subgraph of its complement. So far the best result concerning this conjecture is that every non-star graph G without cycles of length m 6 is a subgraph of its complement. In this note we show that m 6 can be replaced by m 5. 1 Introduction We deal with finite simple graphs without loops and multiple edges. We use standard graph theory notation. Let G be a graph with the vertex set V G and the edge set E G . The order of G is denoted by G and the size is denoted by G . We say that G is packable in its complement G is packable in short if there is a permutation Ơ on V G such that if xy is an edge in G then ơ x ơ y is not an edge in G. Thus G is packable if and only if G is a subgraph of its complement. In 2 the authors stated the following conjecture Conjecture 1 Every non-star graph G without cycles of length m 4 is packable. In 2 they proved that the above conjecture holds if G 5 G 2. WoZniak proved that a graph G without cycles of length m 7 is packable 6 . His result was improved by Brandt 1 who showed that a graph G without cycles of length m 6 is packable. Another relatively short proof of Brandt s result was given in 3 . In this note we prove the following statement. The research was partially supported by a grant N201 1247 33 THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 N30 1 Theorem 2 If a graph G is a non-star graph without cycles of length m 5 then G is packable. The basic ingredient for the proof of our theorem is the lemma presented below. This lemma is both a modification and an extension of
