Induced matchings in subcubic graphs without short cycles

Michael A. Henning, Dieter Rautenbach

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)

Abstract

An induced matching of a graph G is a set M of edges of G such that every two vertices of G that are incident with distinct edges in M have distance at least 2 in G. The maximum number of edges in an induced matching of G is the induced matching number (G) of G. In contrast to ordinary matchings, induced matchings in graphs are algorithmically difficult. Next to hardness results and efficient algorithms for restricted graph classes, lower bounds are therefore of interest. We show that if G is a connected graph of order n(G), maximum degree at most 3, girth at least 6, and without a cycle of length 7, then (G)≥n(G)-15, and we characterize the graphs achieving equality in this lower bound.

Original languageEnglish
Pages (from-to)165-172
Number of pages8
JournalDiscrete Mathematics
Volume315-316
Issue number1
DOIs
Publication statusPublished - 2014

Keywords

  • Induced matching
  • Strong chromatic index
  • Strong matching

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Induced matchings in subcubic graphs without short cycles'. Together they form a unique fingerprint.

Cite this