Connected dominating set
In
Definitions
A connected dominating set of a graph G is a set D of vertices with two properties:
- Any node in D can reach any other node in D by a path that stays entirely within D. That is, D induces a connected subgraph of G.
- Every vertex in G either belongs to D or is adjacent to a vertex in D. That is, D is a dominating set of G.
A minimum connected dominating set of a graph G is a connected dominating set with the smallest possible cardinality among all connected dominating sets of G. The connected domination number of G is the number of vertices in the minimum connected dominating set.[1]
Any spanning tree T of a graph G has at least two leaves, vertices that have only one edge of T incident to them. A maximum leaf spanning tree is a spanning tree that has the largest possible number of leaves among all spanning trees of G. The max leaf number of G is the number of leaves in the maximum leaf spanning tree.[2]
Complementarity
If d is the connected domination number of an n-vertex graph G, where n > 2, and l is its max leaf number, then the three quantities d, l, and n obey the simple equation
If D is a connected dominating set, then there exists a spanning tree in G whose leaves include all vertices that are not in D: form a spanning tree of the subgraph induced by D, together with edges connecting each remaining vertex v that is not in D to a neighbor of v in D. This shows that l ≥ n − d.
In the other direction, if T is any spanning tree in G, then the vertices of T that are not leaves form a connected dominating set of G. This shows that n − l ≥ d. Putting these two inequalities together proves the equality n = d + l.
Therefore, in any graph, the sum of the connected domination number and the max leaf number equals the total number of vertices. Computationally, this implies that determining the connected domination number is equally difficult as finding the max leaf number.
Algorithms
It is
When viewed in terms of approximation algorithms, connected domination and maximum leaf spanning trees are not the same: approximating one to within a given
Both problems may be solved, on n-vertex graphs, in time O(1.9n).[7] The maximum leaf problem is fixed-parameter tractable, meaning that it can be solved in time exponential in the number of leaves but only polynomial in the input graph size. The klam value of these algorithms (intuitively, a number of leaves up to which the problem can be solved within a reasonable amount of time) has gradually increased, as algorithms for the problem have improved, to approximately 37,[8] and it has been suggested that at least 50 should be achievable.[9]
In graphs of maximum
Applications
Connected dominating sets are useful in the computation of
The max leaf number has been employed in the development of
See also
- Universal vertex, a vertex that (when it exists) gives a minimum connected dominating set of size one