TOPICS
Search

Domination Root


A root of the domination polynomial is called a domination root (Akbari et al. 2010).

The set of distinct domination roots of a given graph G with domination polynomial D(G,x) may be denoted Z(D(G,x)) (Akbari et al. 2010). Akbari et al. (2010) showed that if a graph G has two distinct domination roots, then Z(D(G,x))={-2,0}. Furthermore, if G is a graph with no pendant vertex and |Z(D(G,x))|=3, then the elements of Z(D,G) must be 0, -2+/-sqrt(2)i, or (-3+/-sqrt(3)i)i/2 (Akbari et al. 2010). If pendant vertices are allowed for three distinct domination roots, then Z(D,G) may also include (-3+/-sqrt(5))/2.

Domination roots on the real line and in the complex plane

The plots above show a histogram of domatic roots along the real axis and the positions of domatic roots in the complex plane for graphs in GraphData.

The smallest real domination roots appear to occur for star graphs, corresponding to the smallest real roots of their domination polynomials x^(n-1)+x(x+1)^(n-1).

DominationRootsMinus1

Akbari et al. (2010) found that no graphs on 6 or fewer vertices contain a domination root of -1 and conjectured that this hold for all graphs. This is true for all graphs in GraphData, as suggested in the histogram above, as well as for all graphs up to 10 vertices (E. Weisstein, Nov. 26, 2024). Furthermore, the only integers that occur among the domination roots of these graphs are -2 and 0 (E. Weisstein, Dec. 1, 2024).


See also

Dominating Set, Domination Polynomial

Explore with Wolfram|Alpha

References

Akbari, S.; Alikhani, S.; and Peng, Y.-H. "Characterization of Graphs Using Domination Polynomials." Eur. J. Combin. 31, 1714-1724, 2010.

Cite this as:

Weisstein, Eric W. "Domination Root." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DominationRoot.html

Subject classifications