Science Fair Project Encyclopedia
Dominating set
In graph theory, a dominating set for a graph G = (V, E) is a subset V′ of V such that every vertex not in V′ is joined to at least one member of V′ by some edge.
See also
References
- Garey, M. and D. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, 1979.
- Mitchell, S., and S. Hedetniemi, "Edge domination in trees", Proceedings of the 8th Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica Publishing, Winnipeg, 489-509.
- Yannakakis, M. and F. Gavril, "Edge dominating sets in graphs", unpublished manuscript.
Last updated: 06-01-2005 20:18:24
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details