Premium
The Maximum Number of Dominating Induced Matchings
Author(s) -
Lin Min Chih,
Moyano Veronica A.,
Rautenbach Dieter,
Szwarcfiter Jayme L.
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21804
Subject(s) - combinatorics , mathematics , graph , matching (statistics) , discrete mathematics , statistics
Abstract A matching M of a graph G is a dominating induced matching (DIM) of G if every edge of G is either in M or adjacent with exactly one edge in M . We prove sharp upper bounds on the number μ ( G ) of DIMs of a graph G and characterize all extremal graphs. Our results imply that if G is a graph of order n , then μ ( G ) ≤ 3 n 3; μ ( G ) ≤ 4 n 5provided G is triangle‐free; and μ ( G ) ≤ 4 n − 1 5provided n ≥ 9 and G is connected.