tailieunhanh - Báo cáo toán học: "Constructive Upper Bounds for Cycle-Saturated Graphs of Minimum Size"

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: Constructive Upper Bounds for Cycle-Saturated Graphs of Minimum Size. | Constructive Upper Bounds for Cycle-Saturated Graphs of Minimum Size Ronald Gould Department of Mathematics and Computer Science 400 Dowman Drive Emory University Atlanta GA 30322 Tomasz Luczak Department of Mathematics and Computer Science 400 Dowman Drive Emory University Atlanta GA 30322 and Department of Discrete Mathematics Faculty of Mathematics and CS Adam Mickiewicz University Poznan Poland John Schmitt Department of Mathematics Middlebury College Middlebury VT 05753 Submitted Jun 19 2005 Accepted Mar 26 2006 Published Mar 31 2006 Mathematics Subject Classification 05C35 05C38 Abstract A graph G is said to be Cl-saturated if G contains no cycle of length l but for any edge in the complement of G the graph G e does contain a cycle of length l. The minimum number of edges of a Cl-saturated graph was shown by Barefoot et al. to be between n Cl n and n c2 n for some positive constants C1 and c2. This confirmed a conjecture of Bollobás. Here we improve the value of c2 for l 8. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R29 1 1 Introduction We let G V E be a graph on VI n vertices and EI m edges. We denote the cycle on l vertices by Cl and the complete graph on t vertices by K . The graph G is said to be F-saturated if G contains no copy of F as a subgraph but for any edge e in the complement of G the graph G e contains a copy of F where G e denotes the graph V E u e . For a subgraph F we will denote the minimum size of an F-saturated graph by sat n F . In 1964 Erdos Hajnal and Moon 10 determined the minimum number of edges in a graph that is K saturated. This number sat n Kt is t 2 n 1 Ợ 2 and arises from the graph Kt-2 K t 2 where denotes the join. Determining the exact value of this function for a given graph F has been quite difficult and is known for relatively few graphs. Kaszonyi and Tuza in 12 proved the best known general upper bound for sat n F . Cycle-saturated graphs of minimum size have been considered by various authors. The case l 3 is covered