A lower bound on the acyclic matching number of subcubic graphs
A lower bound on the acyclic matching number of subcubic graphs
复制标题
DOI：
10.1016/j.disc.2018.05.010
复制
发表时间：
2018-08-01
影响因子：
0.8
通讯作者：
Rautenbach, D.
中科院分区：
文献类型：
--
作者：
Fuerst, M.;Rautenbach, D.
图G的无圈匹配数是指图G中的一个无圈匹配的最大尺寸，即图G中的一个匹配M使得由M中的边所关联的顶点所导出的图G的子图是一个森林。本文证明了除5阶和6阶图外，m边连通次立方图G的无圈匹配数至少为m/6. (C)2018 Elsevier B. V.版权所有。
The acyclic matching number of a graph G is the largest size of an acyclic matching in G, that is, a matching M in G such that the subgraph of G induced by the vertices incident to edges in M is a forest. We show that the acyclic matching number of a connected subcubic graph G with m edges is at least m/6 except for two graphs of order 5 and 6. (C) 2018 Elsevier B.V. All rights reserved.