The maximum number of dominating induced matchings
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,...
Guardado en:
| Autores principales: | Lin, M.C., Moyano, V.A., Rautenbach, D., Szwarcfiter, J.L. |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_03649024_v78_n4_p258_Lin |
| Aporte de: |
Ejemplares similares
-
The maximum number of dominating induced matchings
Publicado: (2015) -
O(n) time algorithms for dominating induced matching problems
por: Lin, M.C., et al. -
Fast algorithms for some dominating induced matching problems
por: Lin, M.C., et al. -
Exact Algorithms for Minimum Weighted Dominating Induced Matching
por: Lin, M.C., et al. -
O(n) time algorithms for dominating induced matching problems
Publicado: (2014)