ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


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


Shiow-Fen Hwang

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


Gerard J. Chang

Department of Applied Mathematics, National Chiao Tung University
Hsinchu 30050 Taiwan


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


[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.