PDF

Discussiones Mathematicae Graph Theory  15(1) (1995)   51-57
DOI: https://doi.org/10.7151/dmgt.1006

THE EDGE DOMINATION PROBLEM

Shiow-Fen Hwang

Department of Computer Science, Feng Chia University
Taichung 40724, Taiwan

and

Gerard J. Chang

Department of Applied Mathematics, National Chiao Tung University
Hsinchu 30050 Taiwan
e-mail: gjchang@math.nctu.edu.tw

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.

Keywords: edge domination, block graph, depth first search

1991 Mathematics Subject Classification: 05C70

References

[1]	A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974).
[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.
[3]	M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).
[4]	S. R. Jayaram, Line domination in graphs, Graphs and Combin. 3 (1987) 357-363, doi: 10.1007/BF01788558.
[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.
[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.