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.