论文标题
最小化$ \ Mathcal {c} _ {\ ge r} $饱和图中边缘的数量
Minimizing the number of edges in $\mathcal{C}_{\ge r}$-saturated graphs
论文作者
论文摘要
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 $F\in\mathcal{F}$ but the addition of any edge $e\notin E(G)$ creates at least one copy of some $ f \ in \ Mathcal {f} $ in $ g $。 $ n $顶点上$ \ mathcal {f} $ - 饱和图的最小大小称为饱和号，由$ \ sat（n，\ nyclcal {f}）$表示。令$ \ Mathcal {C} _ {\ ge r} $为长度至少$ r $的循环的家族。 Ferrara等。 （2012年）给出了$ \ sat（n，c _ {\ ge r}）$的下限和上限，并确定$ \ sat（n，c _ {\ ge r}）$的确切值，价格为$ 3 \ le r \ l \ le 5 $。在本文中，我们确定$ \ sat（N，\ Mathcal {c} _ {\ ge r}）$的确切值，$ r = 6 $和$ 28 \ le \ le \ frac {n} 2 \ le r \ le r \ le r \ le \ le \ le n $并给其他情况下的新上限和下限。
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 $F\in\mathcal{F}$ but the addition of any edge $e\notin E(G)$ creates at least one copy of some $F\in\mathcal{F}$ within $G$. The minimum size of an $\mathcal{F}$-saturated graph on $n$ vertices are called the saturation number, denoted by $\sat(n, \mathcal{F})$. Let $\mathcal{C}_{\ge r}$ be the family of cycles of length at least $r$. Ferrara et al. (2012) gave lower and upper bounds of $\sat(n, C_{\ge r})$ and determined the exact values of $\sat(n, C_{\ge r})$ for $3\le r\le 5$. In this paper, we determine the exact value of $\sat(n,\mathcal{C}_{\ge r})$ for $r=6$ and $28\le \frac{n}2\le r\le n$ and give new upper and lower bounds for the other cases.
