dominating set of a tournament graph

Question

I am writing an algorithm to find the dominating set of a tournament graph. Is the minimum spanning tree of a directed graph equivalent to the dominating set of the graph? In other words, if I find the smallest MST for the tournament graph (by iterating through all of the vertices), can I then say this is equivalent to the dominating set of the graph?

Answer 1

This Wikipedia article states that the problems of finding a dominating set and finding a spanning tree are equivalent. Given a spanning tree, the non-leaf nodes form a dominating set, and given a connected dominating set, you can easily obtain of the original graph joining one spanning tree of it with the vertexes that do not belong to it. However, finding a minimum spanning tree and finding a minimal dominating set are different problems. I guess that they are equivalent again, but I'm not sure.

Answer 2

No, because the MST will include all vertices of the graph, and the dominating set might not.

See for example the graph here: http://en.wikipedia.org/wiki/Tournament_(graph_theory) Vertices 2 and 4 create a dominating set, and not a spanning tree.