Uniquely restricted matchings in subcubic graphs without short cycles

2018/10/10 by Fürst, Maximilian, Rautenbach, Dieter
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1810.04473

Abstract

A matching M in a graph G is uniquely restricted if no other matching in G covers the same set of vertices. We prove that any connected subcubic graph with n vertices and girth at least 5 contains a uniquely restricted matching of size at least (n-1) / 3 except for two exceptional cubic graphs of order 14 and 20.

Related

• Uniquely restricted matchings in subcubic graphs
• On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs
• Graphs in which some and every maximum matching is uniquely restricted
• Some bounds on the uniquely restricted matching number
• Uniquely restricted matchings and edge colorings