Constructive Upper Bounds for Cycle-Saturated Graphs of Minimum Size
Constructive Upper Bounds for Cycle-Saturated Graphs of Minimum Size
复制标题
最小尺寸循环饱和图的构造上界
DOI：
--
复制
发表时间：
2006
影响因子：
0.7
通讯作者：
John R. Schmitt
中科院分区：
文献类型：
--
作者：
R. Gould;T. Luczak;John R. Schmitt
一个图G$被称为$C_l$-饱和的，如果$G$不包含长度为$l$的圈，但是对于$G$的补图中的任何边，$G $+e$都包含长度为$l$的圈。Barefoot等人证明了对于某些正的常数c_1和c_2，$C_1 $-饱和图的最小边数在$n+c_1{novel}$和$n+c_2{novel}$之间.这证实了Bollobas的一个猜想。在这里，我们改进了$c_2$的值为$l geq 8$。
A graph $G$ is said to be $C_l$-saturated if $G$ contains no cycle of length $l$, but for any edge in the complement of $G$ the graph $G+e$ does contain a cycle of length $l$. The minimum number of edges of a $C_l$-saturated graph was shown by Barefoot et al. to be between $n+c_1{nover l}$ and $n+c_2{nover l}$ for some positive constants $c_1$ and $c_2$. This confirmed a conjecture of Bollobas. Here we improve the value of $c_2$ for $l geq 8$.