# The edge domination problem

Shiow-Fen Hwang; Gerard J. Chang

Discussiones Mathematicae Graph Theory (1995)

- Volume: 15, Issue: 1, page 51-57
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topShiow-Fen Hwang, and Gerard J. Chang. "The edge domination problem." Discussiones Mathematicae Graph Theory 15.1 (1995): 51-57. <http://eudml.org/doc/270268>.

@article{Shiow1995,

abstract = {An edge dominating set of a graph is a set D of edges such that every edge not in D is adjacent to at least one edge in D. In this paper we present a linear time algorithm for finding a minimum edge dominating set of a block graph.},

author = {Shiow-Fen Hwang, Gerard J. Chang},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {edge domination; block graph; depth first search; mixed edge dominating set; linear time algorithm},

language = {eng},

number = {1},

pages = {51-57},

title = {The edge domination problem},

url = {http://eudml.org/doc/270268},

volume = {15},

year = {1995},

}

TY - JOUR

AU - Shiow-Fen Hwang

AU - Gerard J. Chang

TI - The edge domination problem

JO - Discussiones Mathematicae Graph Theory

PY - 1995

VL - 15

IS - 1

SP - 51

EP - 57

AB - An edge dominating set of a graph is a set D of edges such that every edge not in D is adjacent to at least one edge in D. In this paper we present a linear time algorithm for finding a minimum edge dominating set of a block graph.

LA - eng

KW - edge domination; block graph; depth first search; mixed edge dominating set; linear time algorithm

UR - http://eudml.org/doc/270268

ER -

## References

top- [1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974). Zbl0326.68005
- [2] R. D. Dutton and R. C. Brigham, An extremal problem for the edge domination insensitive graphs, Discrete Applied Math. 20 (1988) 113-125, doi: 10.1016/0166-218X(88)90058-3. Zbl0638.05031
- [3] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979). Zbl0411.68039
- [4] S. R. Jayaram, Line domination in graphs, Graphs and Combin. 3 (1987) 357-363, doi: 10.1007/BF01788558. Zbl0628.05056
- [5] S. Mitchell and S. T. Hedetniemi, Edge domination in trees, in: Proc. 8th S. E. Conf. Combin., Graph Theory and Computing, Congr. Numer. 19 (1977) 489-509. Zbl0433.05023
- [6] P. S. Neeralagi, Strong, weak edge domination in a graph, manuscript, November 1988.
- [7] M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38 (1980) 364-372, doi: 10.1137/0138030. Zbl0455.05047

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.