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 language | English |
---|---|
Pages (from-to) | 165-172 |
Number of pages | 8 |
Journal | Discrete Mathematics |
Volume | 315-316 |
Issue number | 1 |
DOIs | |
Publication status | Published - 2014 |
Keywords
- Induced matching
- Strong chromatic index
- Strong matching
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics