Optimum Domination in Unicyclic Graphs
Sandra Hedetniemi
Committee:
Technical Report(May 1980)
Keywords:

A dominating set is a set of vertices of a graph such that every vertex not in the set is adjacent to a vertex in the set. The problem of dete:rmining a minimum dominating set in an arbitrary graph is known to be NP-complete. An algorithm which is linear in the number of vertices is presented for unicyclic graphs. This result extends the classes of graphs for which linear algorithms exist, i.e. trees and interval graphs.