论文标题
立方匹配的覆盖图中的可移动边缘
Removable edges in cubic matching covered graphs
论文作者
论文摘要
{如果$ g-e $涉及匹配的匹配图，则在匹配的覆盖图中的边缘$ e $是{\ em emovable}，这是由Lovász和Plummer引入的，与匹配覆盖的图形的耳朵分解有关。 {\ it Brick}}是一个非双方匹配的覆盖图，而无需非平凡的紧密切割。砖的重要性源于它们是匹配覆盖图的基础。 Carvalho等人改善了Lovász的结果。 [匹配覆盖图的耳朵分解，{\ em combinatorica}，19（2）：151-174，1999]表明，除$ k_4 $和$ \ overline {c_6} $都具有$Δ2$可移动边缘的每个砖，而$δ$是$δ$的最高$ g $。在本文中，我们表明，除$ k_4 $以外的每个立方砖$ g $，而$ \ overline {c_6} $具有至少$ | v（g）|/8 $的匹配，每个边缘的每个边缘都可以在$ g $中移动。
{ An edge $e$ in a matching covered graph $G$ is {\em removable} if $G-e$ is matching covered, which was introduced by Lovász and Plummer in connection with ear decompositions of matching covered graphs. A {\it brick}} is a non-bipartite matching covered graph without non-trivial tight cuts. The importance of bricks stems from the fact that they are building blocks of matching covered graphs. Improving Lovász's result, Carvalho et al. [Ear decompositions of matching covered graphs, {\em Combinatorica}, 19(2):151-174, 1999] showed that each brick other than $K_4$ and $\overline{C_6}$ has $Δ-2$ removable edges, where $Δ$ is the maximum degree of $G$. In this paper, we show that every cubic brick $G$ other than $K_4$ and $\overline{C_6}$ has a matching of size at least $|V(G)|/8$, each edge of which is removable in $G$.
