Efficient edge domination in regular graphs

DOI10.1016/J.DAM.2008.01.021MaRDI QIDQ1005253zbMATH OpenOpenAlexFDO

Authors C. Delorme, Pedro C. Silva, D. M. 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)

Recommendations

• Efficient edge domination problems in graphs
• Perfect edge domination and efficient edge domination in graphs
• Efficient dominating and edge dominating sets for graphs and hypergraphs
• scientific article; zbMATH DE number 4085682
• Efficient domination and efficient edge domination: a brief survey
• Edge domination in graphs
• Efficient domination in circulant graphs
• Efficient total domination in digraphs
• Efficient edge domination on hole-free graphs in polynomial time
• scientific article; zbMATH DE number 1151809

Cites work

• scientific article; zbMATH DE number 3777544 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1420901 (Why is no real title available?)
• Biclique decompositions and Hermitian rank
• Efficient edge domination problems 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
• Handbook of Graph Theory
• Induced matchings
• Induced matchings in intersection graphs.
• NP-completeness of some generalizations of the maximum matching problem
• New results on induced matchings
• On the approximability of the maximum induced matching problem
• Perfect edge domination and efficient edge domination in graphs
• Regular codes in regular graphs are difficult
• Solving the weighted efficient edge domination problem on bipartite permutation graphs

Cited in

(17)

• scientific article; zbMATH DE number 4057564 (Why is no real title available?)
• Combinatorial and spectral properties of König-Egerváry graphs
• Independent feedback vertex set for \(P_5\)-free graphs
• Some results on dominating induced matchings
• Perfect edge domination: hard and solvable cases
• Bounding and approximating minimum maximal matchings in regular graphs
• Efficient domination through eigenvalues
• Dominating induced matchings in graphs without a skew star
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• The Maximum Number of Dominating Induced Matchings
• Modelling and solving the perfect edge domination problem
• On the dominating induced matching problem: spectral results and sharp bounds
• Dominating induced matchings
• Graphs whose vertices of degree at least 2 lie in a triangle
• Exact algorithms for dominating induced matching based on graph partition
• Exact algorithms for minimum weighted dominating induced matching
• Complexity of simplicial homology and independence complexes of chordal graphs

This page was built for publication: Efficient edge domination in regular graphs

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