The Maximum Number of Dominating Induced Matchings

DOI10.1002/jgt.21804zbMath1309.05137OpenAlexW2141726500MaRDI QIDQ4982287

Dieter Rautenbach, Min Chih Lin, Veronica A. Moyano, Jayme Luiz Szwarcfiter

Publication date: 24 March 2015

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.21804

zbMATH Keywords

Fibonacci numbersdominating induced matching

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Related Items

Perfect edge domination: hard and solvable cases ⋮ On the dominating induced matching problem: spectral results and sharp bounds ⋮ Dominating induced matching in some subclasses of bipartite graphs

Cites Work

• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Efficient edge domination in regular graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Efficient edge domination problems in graphs
• Perfect edge domination and efficient edge domination in graphs
• A Polynomial-time Algorithm for the Dominating Induced Matching Problem in the Class of Convex Graphs
• An O *(1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching
• Dominating Induced Matchings for P 7-free Graphs in Linear Time
• Efficient Edge Domination on Hole-Free Graphs in Polynomial Time
• Dominating Induced Matchings
• Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs

This page was built for publication: The Maximum Number of Dominating Induced Matchings