论文标题
立方图中的围绕围栏问题的方法
An approach to the girth problem in cubic graphs
论文作者
论文摘要
我们为立方图最大的围绕围栏问题提供了一种新的渐进方法。很容易观察到，在所有$ n $ vertex立方图中，最大的腰围是通过$ 2 $连接的图$ g =（v，e）$实现的。彼得森的图定理，$ e $是$ 2 $ fector和完美匹配的$ m $的脱节结合。我们将$ m $的边缘称为和弦，并将周期按$ g $进行分类。我们将$γ_k（n）$定义为最大的整数$ g $，以便每个立方$ n $ n $ vertex图具有给定的完美匹配$ m $，最多具有$ g $的循环，最多$ k $ chords。在这里，我们确定此功能为$ k = 1、2 $的小添加剂常数，最多可用于较大$ k $的小乘法常数。
We offer a new, gradual approach to the largest girth problem for cubic graphs. It is easily observed that the largest possible girth of all $n$-vertex cubic graphs is attained by a $2$-connected graph $G=(V,E)$. By Petersen's graph theorem, $E$ is the disjoint union of a $2$-factor and a perfect matching $M$. We refer to the edges of $M$ as chords and classify the cycles in $G$ by their number of chords. We define $γ_k(n)$ to be the largest integer $g$ such that every cubic $n$-vertex graph with a given perfect matching $M$ has a cycle of length at most $g$ with at most $k$ chords. Here we determine this function up to small additive constant for $k= 1, 2$ and up to a small multiplicative constant for larger $k$.
