论文标题
完美的匹配索引与立方图的圆流数量
Perfect matching index vs. circular flow number of a cubic graph
论文作者
论文摘要
Cubic Graph $ G $的完美匹配索引，用$π（G）$表示，是覆盖$ G $的所有边缘的最少匹配数量。根据Berge-Fulkerson的猜想，每个Bridgeless Cubic Graph〜$ G $ $π（G）\ le5 $。具有$π\ ge 5 $的图表特别令人感兴趣，因为许多猜想和开放问题（包括著名的循环双重覆盖猜想）可以减少到其中。尽管此类图的非平凡示例很难找到，但已知一些无限的家庭，所有圆周流量$φ_C（g）= 5 $。因此，有人建议[电子。 J. Combin。 23（2016），$ \＃$ p3.54] $π（g）\ ge 5 $可能意味着$φ_C（g）\ ge 5 $。在本文中，我们消除了这些希望，并提出了一个周期性的$ 4 $ - 边缘连接的腰围的立方图，至少$ 5 $（snarks），$π\ ge 5 $和$φ_c\ le 4+ \ frac23 $。
The perfect matching index of a cubic graph $G$, denoted by $π(G)$, is the smallest number of perfect matchings that cover all the edges of $G$. According to the Berge-Fulkerson conjecture, $π(G)\le5$ for every bridgeless cubic graph~$G$. The class of graphs with $π\ge 5$ is of particular interest as many conjectures and open problems, including the famous cycle double cover conjecture, can be reduced to it. Although nontrivial examples of such graphs are very difficult to find, a few infinite families are known, all with circular flow number $Φ_c(G)=5$. It has been therefore suggested [Electron. J. Combin. 23 (2016), $\#$P3.54] that $π(G)\ge 5$ might imply $Φ_c(G)\ge 5$. In this article we dispel these hopes and present a family of cyclically $4$-edge-connected cubic graphs of girth at least $5$ (snarks) with $π\ge 5$ and $Φ_c\le 4+\frac23$.
