pith. sign in

arxiv: 1805.00840 · v1 · pith:JHKSB4YVnew · submitted 2018-05-02 · 🧮 math.CO

Uniquely restricted matchings in subcubic graphs

classification 🧮 math.CO
keywords matchingrestricteduniquelygraphleastsubcubicbridgesconjecture
0
0 comments X
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.