Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423979 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
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 G+e contains some H. The minimum size of an n-vertex H-saturated graph is denoted by sat(n,H). We provesat(n,Ck)=n+n/k+O((n/k2)+k2) holds for all n⩾k⩾3, where Ck is a cycle with length k.We conjecture that our constructions are essentially optimal.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zoltán Füredi, Younjin Kim,