Back to Search Start Over

Uniquely restricted matchings in subcubic graphs without short cycles

Authors :
Fürst, Maximilian
Rautenbach, Dieter
Publication Year :
2018

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$.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1810.04473
Document Type :
Working Paper