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: | , , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_03649024_v78_n4_p258_Lin |
| Aporte de: |
| id |
todo:paper_03649024_v78_n4_p258_Lin |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_03649024_v78_n4_p258_Lin2023-10-03T15:27:41Z The maximum number of dominating induced matchings Lin, M.C. Moyano, V.A. Rautenbach, D. Szwarcfiter, J.L. Dominating induced matching Fibonacci numbers Number theory Extremal graph Fibonacci numbers Graph G Induced matchings Triangle-free Upper Bound Graph theory 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) & le; 3n/3 μ(G) & le; 4n/5 provided G is triangle-free; and μ(G) & le; 4 n-1/5 provided n ≤ 9 and G is connected. © 2014 Wiley Periodicals, Inc. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03649024_v78_n4_p258_Lin |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Dominating induced matching Fibonacci numbers Number theory Extremal graph Fibonacci numbers Graph G Induced matchings Triangle-free Upper Bound Graph theory |
| spellingShingle |
Dominating induced matching Fibonacci numbers Number theory Extremal graph Fibonacci numbers Graph G Induced matchings Triangle-free Upper Bound Graph theory Lin, M.C. Moyano, V.A. Rautenbach, D. Szwarcfiter, J.L. The maximum number of dominating induced matchings |
| topic_facet |
Dominating induced matching Fibonacci numbers Number theory Extremal graph Fibonacci numbers Graph G Induced matchings Triangle-free Upper Bound Graph theory |
| description |
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) & le; 3n/3 μ(G) & le; 4n/5 provided G is triangle-free; and μ(G) & le; 4 n-1/5 provided n ≤ 9 and G is connected. © 2014 Wiley Periodicals, Inc. |
| format |
JOUR |
| author |
Lin, M.C. Moyano, V.A. Rautenbach, D. Szwarcfiter, J.L. |
| author_facet |
Lin, M.C. Moyano, V.A. Rautenbach, D. Szwarcfiter, J.L. |
| author_sort |
Lin, M.C. |
| title |
The maximum number of dominating induced matchings |
| title_short |
The maximum number of dominating induced matchings |
| title_full |
The maximum number of dominating induced matchings |
| title_fullStr |
The maximum number of dominating induced matchings |
| title_full_unstemmed |
The maximum number of dominating induced matchings |
| title_sort |
maximum number of dominating induced matchings |
| url |
http://hdl.handle.net/20.500.12110/paper_03649024_v78_n4_p258_Lin |
| work_keys_str_mv |
AT linmc themaximumnumberofdominatinginducedmatchings AT moyanova themaximumnumberofdominatinginducedmatchings AT rautenbachd themaximumnumberofdominatinginducedmatchings AT szwarcfiterjl themaximumnumberofdominatinginducedmatchings AT linmc maximumnumberofdominatinginducedmatchings AT moyanova maximumnumberofdominatinginducedmatchings AT rautenbachd maximumnumberofdominatinginducedmatchings AT szwarcfiterjl maximumnumberofdominatinginducedmatchings |
| _version_ |
1807323415379443712 |