Minimizing the number of edges in $mathcal{C}_{ge r}$-saturated graphs
Minimizing the number of edges in $mathcal{C}_{ge r}$-saturated graphs
复制标题
最小化 $mathcal{C}_{ge r}$ 饱和图中的边数
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Jun
中科院分区：
文献类型：
--
作者：
Yue Ma;Xinmin Hou;Jun
给定一组图$mathcal{F}$，如果$G$不包含$F$的副本作为任意$Finmathcal{F}$的子图，而只包含任意边$e的加法，则称为$mathcal{F}$-饱和图$G$
Given a family of graphs $mathcal{F}$, a graph $G$ is said to be $mathcal{F}$-saturated if $G$ does not contain a copy of $F$ as a subgraph for any $Finmathcal{F}$ but the addition of any edge $e
otin E(G)$ creates at least one copy of some $Finmathcal{F}$ within $G$. The minimum and maximum size of an $mathcal{F}$-saturated graph on $n$ vertices are called the saturation number and the Tur'an number of $mathcal{F}$, denoted by $sat(n, mathcal{F})$ and $ex(n, mathcal{F})$, respectively. Let $mathcal{C}_{ge r}$ be the family of cycles of length at least $r$. ErdH{o}s and Gallai (1959) proved that $ex(n, mathcal{C}_{ge r})le frac{(r-1)(n-1)}2,$ where $nge rge 3$. In this paper, we determine the exact values of $sat(n,mathcal{C}_{ge r})$ for $rin{3,4,5}$ and $frac n2le rle n$ and give upper and lower bounds for the other cases.