The Maximum Number of Dominating Induced Matchings

DOI10.1002/JGT.21804MaRDI QIDQ4982287zbMATH OpenOpenAlexFDO

Authors Min Chih Lin, Veronica A. Moyano, Dieter Rautenbach, Jayme L. 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

dominating induced matchingFibonacci numbers

Mathematics Subject Classification ID

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

Recommendations

• Maximum induced matchings in graphs
• Some results on dominating induced matchings
• Dominating induced matchings
• Induced matchings in graphs of bounded maximum degree
• On maximum induced matchings in bipartite graphs
• Maximum induced matchings close to maximum matchings
• scientific article; zbMATH DE number 866672
• Maximum Induced Matchings in Grids

Cites work

• 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
• Dominating induced matchings for \(P _{7}\)-free graphs in linear time
• Efficient dominating and edge dominating sets for graphs and hypergraphs
• Efficient edge domination in regular graphs
• Efficient edge domination on hole-free graphs in polynomial time
• Efficient edge domination problems in graphs
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Perfect edge domination and efficient edge domination in graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs

Cited in

(7)

• Maximum induced matchings in graphs
• Perfect edge domination: hard and solvable cases
• On the dominating induced matching problem: spectral results and sharp bounds
• Some results on dominating induced matchings
• On H-dominating matchings and some number partitions
• Maximum Induced Matchings in Grids
• Dominating induced matching in some subclasses of bipartite graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4982287)