Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "A note on packing graphs without cycles of length up to five"

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 @agh.edu.pl 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