Cycle-saturated graphs with minimum number of edges

Younjin Kim (김연진)

Department of Mathematical Sciences, KAIST

Department of Mathematical Sciences, KAIST

2012/9/14 Fri 4PM-5PM

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 prove sat(n,C

Joint work with Zoltan Füredi.

_{k}) = n + n/k + O((n/k^{2}) + k^{2}) holds for all n≥k≥3, where C_{k}is a cycle with length k.Joint work with Zoltan Füredi.

Tags: 김연진