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 m/+b6, 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 n/−13, which partially confirms a conjecture of Fürst and Rautenbach (Graphs Combin. 35 (2019) 353–361).
Original language | English |
---|---|
Pages (from-to) | 189-194 |
Number of pages | 6 |
Journal | Discrete Applied Mathematics |
Volume | 262 |
DOIs | |
Publication status | Published - 15 Jun 2019 |
Keywords
- Bridge
- Girth
- Matching
- Subcubic
- Uniquely restricted matching
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics