错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Fractional matchings on regular graphs

  • Xiaxia Guan,
  • Tianlong Ma

摘要

Every k-regular graph has a fractional perfect matching via assigning each edge a fractional number \(\frac{1}{k}\) 1 k . How many edges are deleted from a regular graph so that the resulting graph still has a fractional perfect matching? Let G be a k-regular graph with n vertices. In this paper, we prove that the fractional matching number of the resulting graph deleting any \(\left\lfloor \frac{(t+1)k-1}{2}\right\rfloor\) ( t + 1 ) k - 1 2 edges from G is not less than \(\frac{1}{2}(n-t)\) 1 2 ( n - t ) . In particular, taking \(t=0\) t = 0 , we deduce that the resulting graph deleting any \(\lfloor \frac{k-1}{2}\rfloor\) k - 1 2 edges from G has a fractional perfect matching. Specially, we can delete any \(k-1\) k - 1 edges from G other than exceptions such that the resulting graph has a fractional perfect matching when \(n\le 2k-2\) n 2 k - 2 . Further, the resulting graph deleting any \(\left\lfloor \frac{k+l-1}{2}\right\rfloor\) k + l - 1 2 edges from a k-regular l-edge-connected graph with an even number of vertices has a fractional perfect matching. As applications, some values or bounds on the fractional matching preclusion number of regular graphs are deduced immediately.