文章导读
总览 评价 刘清海 1， ， Xingxing Yu 2，* ， 张昭 3， （ 1、 福州大学离散数学研究中心,福州 350108 ； 2、 School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia, 30318, USA.； 3、 浙江师范大学数理信息学院,金华,浙江,321004；
刘清海1，， Xingxing Yu2，*， 张昭3，
（
1、福州大学离散数学研究中心,福州 350108 ； 2、School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia, 30318, USA.； 3、浙江师范大学数理信息学院,金华,浙江,321004； ）
摘要：
图的周长是指图的最长圈的长度,Bondy 猜想存在一个常数~$c$ 使得任意一个阶数为~$n$ 的三连通三正则图的周长至少为~$n^c$. 该猜想被~Jackson 证明,其中~$c=0.694$. Bilinsi 等人通过研究三边连通图中的欧拉子图又把界提高到了~$Omega(n^{0.753})$。 这篇文章中,我们通过考虑通过任意两条边（包括相邻和不相邻两种情况）的圈的方式进一步把下界提高到~$Omega(n^0.8)$.
关键词：
周长；三正则图；最长圈
Qinghai Liu1,， Xingxing Yu2,*， Zhao Zhang3,
（
1、Center for Discrete Mathematics, Fuzhou University, Fuzhou 350108 ； 2、School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia, 30318, USA； 3、College of Mathematics Physics and Information Engineering, Zhejiang Normal University, Jinhua, Zhejiang, 321004, China； ）
Abstract：
The circumference of a graph is the length of its longest cycles. Jackson established a conjecture of Bondy by showing that the circumference of a 3-connected cubic graph of order $n$ is $Omega(n^{0.694})$.Bilinski {it et al.} improved this lower bound to $Omega(n^{0.753})$ bystudying large Eulerian subgraphs in 3-edge-connected graphs.In this paper, we further improve this lower bound to $Omega(n^{0.8})$.This is done by considering certain 2-connected cubic graphs, finding cycles through two given edges, anddistinguishing the cases whether or not these edges are adjacent.
Tag：
点此返回栏目查看更多>>>参考论文
