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 connecting 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.
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.
Read more about this topic: Connected Dominating Set
Famous quotes containing the word definitions:
“What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
—G.C. (Georg Christoph)
“Lord Byron is an exceedingly interesting person, and as such is it not to be regretted that he is a slave to the vilest and most vulgar prejudices, and as mad as the winds?
There have been many definitions of beauty in art. What is it? Beauty is what the untrained eyes consider abominable.”
—Edmond De Goncourt (1822–1896)