Download PDF - The edge domination problemAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

The edge domination problem

Authors 1, 2

Affiliations

  1. Department of Computer Science, Feng Chia University
  2. Department of Applied Mathematics, National Chiao Tung University

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

ENG
edge domination, block graph, depth first search

Bibliography

  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.
Discussiones Mathematicae Graph Theory
1995/15/1
Export to PBN, Opens in new tab
Pages:
51-57
Main language of publication
English
Received
1994-04-27
Published
1995
Exact and natural sciences