Cycle‐Saturated Graphs with Minimum Number of Edges |
| |
| Authors: | Zoltán Füredi Younjin Kim |
| |
| Institution: | 1. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF ILLINOIS, , URBANA, ILLINOIS;2. RéNYI INSTITUTE OF MATHEMATICS OF THE HUNGARIAN, ACADEMY OF SCIENCES, , BUDAPEST, P.O. BOX 127 HUNGARY;3. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF ILLINOIS AT URBANA‐CHAMPAIGN, , URBANA, ILLINOIS |
| |
| Abstract: | A graph G is called H‐saturated if it does not contain any copy of H, but for any edge e in the complement of G, the graph  contains some H. The minimum size of an n‐vertex H‐saturated graph is denoted by  . We prove ![urn:x-wiley:03649024:media:jgt21668:jgt21668-math-0003]( "urn:x-wiley:03649024:media:jgt21668:jgt21668-math-0003") holds for all  , where  is a cycle with length k. A graph G is H‐semisaturated if  contains more copies of H than G does for  . Let  be the minimum size of an n‐vertex H‐semisaturated graph. We have ![urn:x-wiley:03649024:media:jgt21668:jgt21668-math-0009]( "urn:x-wiley:03649024:media:jgt21668:jgt21668-math-0009") We conjecture that our constructions are optimal for  . © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 203–215, 2013 |
| |
| Keywords: | graphs cycles extremal graphs minimal saturated graphs |
|
|
