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
Publicado: 2015
Materias:
Dominating induced matching
Fibonacci numbers
Number theory
Extremal graph
Graph G
Induced matchings
Triangle-free
Upper Bound
Graph theory
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:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_03649024_v78_n4_p258_Lin
record_format dspace
spelling paper:paper_03649024_v78_n4_p258_Lin2023-06-08T15:35:38Z The maximum number of dominating induced matchings 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. 2015 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
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
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.
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
publishDate 2015
url 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
_version_ 1768542888790065152

Ejemplares similares