Uniquely restricted matchings in subcubic graphs
read the original abstract
A matching $M$ in a graph $G$ is uniquely restricted if no other matching in $G$ covers the same set of vertices. We conjecture that every connected subcubic graph with $m$ edges and $b$ bridges that is distinct from $K_{3,3}$ has a uniquely restricted matching of size at least $\frac{m+b}{6}$, and we establish this bound with $b$ replaced by the number of bridges that lie on a path between two vertices of degree at most $2$. Moreover, we prove that every connected subcubic graph of order $n$ and girth at least $7$ has a uniquely restricted matching of size at least $\frac{n-1}{3}$, which partially confirms a Conjecture of F\"{u}rst and Rautenbach (Some bounds on the uniquely restricted matching number, arXiv:1803.11032).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.