Premium
Uniquely restricted matchings in subcubic graphs without short cycles
Author(s) -
Fürst M.,
Rautenbach D.
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22632
Subject(s) - mathematics , combinatorics , matching (statistics) , graph , discrete mathematics , statistics
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.