Uniquely restricted matchings in subcubic graphs

Maximilian Fürst, Michael A. Henning, Dieter Rautenbach

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

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 languageEnglish
Pages (from-to)189-194
Number of pages6
JournalDiscrete Applied Mathematics
Volume262
DOIs
Publication statusPublished - 15 Jun 2019

Keywords

  • Bridge
  • Girth
  • Matching
  • Subcubic
  • Uniquely restricted matching

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Uniquely restricted matchings in subcubic graphs'. Together they form a unique fingerprint.

Cite this