Efficient edge domination in regular graphs

DOI10.1016/j.dam.2008.01.021zbMath1210.05094OpenAlexW2103621629MaRDI QIDQ1005253

Charles Delorme, Pedro C. Silva, Domingos Moreira Cardoso, Jorge Orestes Cerdeira

Publication date: 9 March 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.01.021

zbMATH Keywords

NP-completenessregular graphsspectra of graphsinduced matchingsdomination in graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Perfect edge domination: hard and solvable cases ⋮ Efficient domination through eigenvalues ⋮ Modelling and solving the perfect edge domination problem ⋮ On the dominating induced matching problem: spectral results and sharp bounds ⋮ Dominating induced matchings in graphs without a skew star ⋮ Bounding and approximating minimum maximal matchings in regular graphs ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Complexity of simplicial homology and independence complexes of chordal graphs ⋮ Combinatorial and spectral properties of König-Egerváry graphs ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ The Maximum Number of Dominating Induced Matchings ⋮ Dominating Induced Matchings ⋮ Exact algorithms for dominating induced matching based on graph partition ⋮ Some results on dominating induced matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Biclique decompositions and Hermitian rank
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Efficient edge domination problems in graphs
• Regular codes in regular graphs are difficult
• Induced matchings in intersection graphs.
• Perfect edge domination and efficient edge domination in graphs
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• On the approximability of the maximum induced matching problem
• New results on induced matchings
• Handbook of Graph Theory