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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1006,
author = {Shiow-Fen Hwang and Gerard J. Chang},
title = {The edge domination problem},
journal = {Discussiones Mathematicae Graph Theory},
volume = {15},
year = {1995},
pages = {51-57},
zbl = {0827.05030},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1006}
}
Shiow-Fen Hwang; Gerard J. Chang. The edge domination problem. Discussiones Mathematicae Graph Theory, Tome 15 (1995) pp. 51-57. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1006/
[000] [1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974). | Zbl 0326.68005
[001] [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. | Zbl 0638.05031
[002] [3] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979). | Zbl 0411.68039
[003] [4] S. R. Jayaram, Line domination in graphs, Graphs and Combin. 3 (1987) 357-363, doi: 10.1007/BF01788558. | Zbl 0628.05056
[004] [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. | Zbl 0433.05023
[005] [6] P. S. Neeralagi, Strong, weak edge domination in a graph, manuscript, November 1988.
[006] [7] M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38 (1980) 364-372, doi: 10.1137/0138030. | Zbl 0455.05047