Efficient edge domination problems in graphs
From MaRDI portal
In a graph \(G=(V,E)\), an edge \(uv\in E\) is said to dominate itself and any edge \(ux\) or \(vx\) in \(E\), where \(x\in V\). An efficient edge dominating set for the graph \(G\) is a subset \(E'\subseteq E\) such that all edges in \(E\) are dominated by exactly one edge in \(E'\). It is proved that the efficient edge domination problem is NP-complete for general graphs and also for line graphs. The authors define a series-parallel graph \(G\), denoted by \((G,(u,v))\), to be a graph which has no subgraph homeomorphic to the complete graph \(K_ 4\) and which has two distinguished vertices \(u\) and \(v\) denoted as the left and right terminal of \(G\), respectively. They describe an algorithm which computes the maximum number of edges that can be efficiently dominated in a series-parallel graph in \(O(n)\) time where \(n=| V|\).
Recommendations
- Perfect edge domination and efficient edge domination in graphs
- scientific article; zbMATH DE number 4085682
- Efficient domination and efficient edge domination: a brief survey
- Efficient dominating and edge dominating sets for graphs and hypergraphs
- Efficient edge domination on hole-free graphs in polynomial time
Cites work
- A recurrence template for several parameters in series-parallel graphs
- Graph-theoretic parameters concerning domination, independence, and irredundance
- scientific article; zbMATH DE number 3648727 (Why is no real title available?)
- scientific article; zbMATH DE number 3172309 (Why is no real title available?)
- scientific article; zbMATH DE number 4057564 (Why is no real title available?)
- scientific article; zbMATH DE number 4085682 (Why is no real title available?)
- scientific article; zbMATH DE number 4101265 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Perfect codes in graphs
- Towards a theory of domination in graphs
Cited in
(51)- Efficient edge domination in regular graphs
- Solving the weighted efficient edge domination problem on bipartite permutation graphs
- Perfect edge domination and efficient edge domination in graphs
- Perfect edge domination: hard and solvable cases
- On the dominating induced matching problem: spectral results and sharp bounds
- Independent feedback vertex set for P₅-free graphs
- Weighted efficient domination for some classes of H-free and of (H₁, H₂)-free graphs
- Fast algorithms for some dominating induced matching problems
- Efficient domination for classes of \(P_6\)-free graphs
- Some results on dominating induced matchings
- Finding dominating induced matchings in P₉-free graphs in polynomial time
- Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs
- Modelling and solving the perfect edge domination problem
- Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
- Stable-\(\Pi\) partitions of graphs
- An overview of \((\kappa, \tau)\)-regular sets and their applications
- Exact algorithms for dominating induced matching based on graph partition
- Efficient domination in knights graphs
- Maximum \(k\)-regular induced subgraphs
- Dominating induced matchings in graphs without a skew star
- Efficient domination and efficient edge domination: a brief survey
- Complexity and kernels for bipartition into degree-bounded induced graphs
- Efficient domination through eigenvalues
- Kernelization of edge perfect code and its variants
- scientific article; zbMATH DE number 5080622 (Why is no real title available?)
- Minimum Dominating Trail Set for Two-Terminal Series Parallel Graphs
- Efficient edge domination on hole-free graphs in polynomial time
- Dominating induced matchings
- scientific article; zbMATH DE number 4057564 (Why is no real title available?)
- On weighted efficient total domination
- scientific article; zbMATH DE number 1092952 (Why is no real title available?)
- Efficient total domination in digraphs
- Dominating induced matchings for \(P_7\)-free graphs in linear time
- THE PARALLEL ALGORITHMS FOR DETERMINING EDGE-PACKING AND EFFICIENT EDGE DOMINATING SETS IN INTERVAL GRAPHS
- Efficient dominating and edge dominating sets for graphs and hypergraphs
- The Maximum Number of Dominating Induced Matchings
- Exact algorithms for minimum weighted dominating induced matching
- Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time
- Dominating induced matching in some subclasses of bipartite graphs
- Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
- Linear-time algorithm for paired-domination on distance-hereditary graphs
- Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time
- Graphs whose vertices of degree at least 2 lie in a triangle
- The efficiency of AC graphs
- Dominating induced matchings and other graph parameters
- On the complexity of the dominating induced matching problem in hereditary classes of graphs
- Complexity and kernels for bipartition into degree-bounded induced graphs
- Perfect edge domination in P₆-free graphs and in graphs without efficient edge dominating sets
- A study on the weighted efficient domination problem for C₄-free bipartite graphs
- Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time
- Weighted efficient domination in two subclasses of P₆-free graphs
This page was built for publication: Efficient edge domination problems in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1313728)
