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,...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Lin, M.C., Moyano, V.A., Rautenbach, D., Szwarcfiter, J.L.
Formato: JOUR
Materias:
Dominating induced matching
Fibonacci numbers
Number theory
Extremal graph
Graph G
Induced matchings
Triangle-free
Upper Bound
Graph theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03649024_v78_n4_p258_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
Descripción
Sumario: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.

Ejemplares similares