Disjoint Chorded Cycles of the Same Length
Disjoint Chorded Cycles of the Same Length
复制标题
DOI：
10.1137/130929837
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
Guantao Chen;R. Gould;Kazuhide Hirohata;K. Ota;Songling Shan
中科院分区：
文献类型：
--
作者：
Guantao Chen;R. Gould;Kazuhide Hirohata;K. Ota;Songling Shan
Bollobas 和 Thomason 证明，阶数为 $n$ 且大小至少为 $n+c\,(c\ge 1)$ 的多重图包含长度最多为 $2(\lfloor n/c\rfloor+1)\lfloor \log_2 2c\rfloor$ 的循环。我们在本文中证明，阶数为 $n$ 且最小度数至少为 5 的多重图（无环）包含长度最多为 $300\log_2 n$ 的弦环（具有弦的环）。作为该结果的应用，我们表明，最小度至少为 $3k+8$ 的足够大阶图包含相同长度的 $k$ 个顶点不相交弦循环，这类似于 Verstraete 的结果：最小度至少为 $2k$ 的足够大阶图包含相同长度的 $k$ 个顶点不相交循环。
Bollobas and Thomason showed that a multigraph of order $n$ and size at least $n+c\,(c\ge 1)$ contains a cycle of length at most $2(\lfloor n/c\rfloor+1)\lfloor \log_2 2c\rfloor$. We show in this paper that a multigraph (with no loop) of order $n$ and minimum degree at least 5 contains a chorded cycle (a cycle with a chord) of length at most $300\log_2 n$. As an application of this result, we show that a graph of sufficiently large order with minimum degree at least $3k+8$ contains $k$ vertex-disjoint chorded cycles of the same length, which is analogous to Verstraete's result: A graph of sufficiently large order with minimum degree at least $2k$ contains $k$ vertex-disjoint cycles of the same length.