Minimum Edge Dominating Sets
Authors:
- J. D. HortonJHJ. D. Horton
- K. KilakosKKK. Kilakos
- 1 August 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 6 (3) , 375-387
Abstract
Let $G = ( V,E )$ be a finite undirected graph with n vertices and m edges. A minimum edge dominating set of G is a set of edges D, of smallest cardinality $\gamma ' ( G )$, such that each edge of $E - D$ is adjacent to some edge of D. Let $S( G )$ be the subdivision graph of G and let $T( G )$ be the total graph of G. Let $\alpha ( G )$ be the stability number of G (cardinality of a largest stable set) and let $\alpha _2 ( G )$ be the 2-stability number of G (cardinality of a largest set of vertices in G, no two of which are joined by a path of length 2 or less). The following results are obtained. For any $G,\gamma' ( S ( G ) ) + \alpha _2 ( G ) = n$ and $2\gamma ' ( T ( G ) ) + \alpha ( T ( G ) ) = n + m$ or $n + m + 1$. Also, for any depth-first search tree S of $G,\gamma ' ( S )/2\leqq \gamma ' ( G )\leqq 2\gamma ' (S)$, and these bounds are tight. The edge domination problem is NP-complete for planar bipartite graphs, their subdivision, line, and total graphs, perfect claw-free graphs, and planar cubic graphs. The stable set problem and the edge domination problem are NP-complete for iterated total graphs. The edge domination problem is solvable in $O( n^3 )$ time for claw-free chordal graphs, locally connected claw-free graphs, the line graphs of total graphs, the line graphs of chordal graphs, the line graph of any graph in which each nonbridge edge is in a triangle, and the total graphs of any of the preceding graphs.
Keywords
This publication has 14 references indexed in Scilit:
- A Dynamic Programming Approach to the Dominating Set Problem on k-TreesSIAM Journal on Algebraic Discrete Methods, 1987
- On partitioning the edges of graphs into connected subgraphsJournal of Graph Theory, 1985
- The k-Domination and k-Stability Problems on Sun-Free Chordal GraphsSIAM Journal on Algebraic Discrete Methods, 1984
- On maximal independent sets of vertices in claw-free graphsJournal of Combinatorial Theory, Series B, 1980
- On domination and independent domination numbers of a graphDiscrete Mathematics, 1978
- The Rectilinear Steiner Tree Problem is $NP$-CompleteSIAM Journal on Applied Mathematics, 1977
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal GraphSIAM Journal on Computing, 1972
- GRAPH THEORY1969
- Paths, Trees, and FlowersCanadian Journal of Mathematics, 1965