Cycle-saturated graphs with minimum number of edges

- 연사: 김연진박사 (MSRI)
- 일시: 2012년 3월 27일 (화) 오후 5시
- 장소: 이화-포스코관 강의실 360호

-Abstract :

 Extremal graph theory studies the maximum or minimum size of edges in a graph on n vertices that satisfies certain given conditions. 
A graph G is called H-saturated if it does not contain H as a subgraph but the addition of any new edge creates at least one copy of H in G. A classic question in graph theory is “What is the maximum number of edges in an H-saturated graph on n vertices? “  This maximum is denoted as ex(n, H) and called the extremal number of H. The minimum size of edges in an H-saturated graph on n-vertices is denoted by sat(n,H), called the saturation number of H. Given H, it is difficult to determine sat(n,H) because this function is not necessarily monotone in n or in H. “What is the saturation number for the k-cycle, Ck?´´ This problem has been considered by various authors, however, in most cases it has remained unsolved for almost forty-five years.
Here relatively tight bounds are given. We prove 
sat(n, Ck) = n + n/k + O((n/k2) + k2)
 holds for all n≥k≥3, where Ck  is a cycle with length k.