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,...
| Publicado: |
2015
|
|---|---|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v78_n4_p258_Lin http://hdl.handle.net/20.500.12110/paper_03649024_v78_n4_p258_Lin |
| Aporte de: |
Ejemplares similares
-
The maximum number of dominating induced matchings
por: Lin, M.C., et al. -
O(n) time algorithms for dominating induced matching problems
Publicado: (2014) -
O(n) time algorithms for dominating induced matching problems
por: Lin, M.C., et al. -
Fast algorithms for some dominating induced matching problems
Publicado: (2014) -
Fast algorithms for some dominating induced matching problems
por: Lin, M.C., et al.