Asymptotic results on saturated graphs

✍ Scribed by Miroslaw Truszczynski; Zsolt Tuza

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 449 KB
• Volume: 87
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(91)90140-w

✦ Synopsis

Truszczynski, M. and Z. Tuza, Asymptotic results on saturated graphs, Discrete Mathematics 87 (1991) 309-314 Let F be a given graph. A graph G is called F-saturated if F & G and F c G + e for every edge e $ E(G), e E V(G). Denote by sat(n, F) the minimum number of edges in an F-saturated graph on n vertices. A conjecture of the second author states that lim,,,

sat(n, F)/n exists for every F. We characterize the case when the limit exists and is smaller than 1.