On the Roots of Connected Domination Polynomials

Abstract

We determine the distribution of the roots of the connected domination polynomial $D_c(G,x)$. The main tool is a substitution formula for the lexicographic product with a complete graph, $D_c(G[K_n],x)=D_c(G,(x+1{)}^n-1)$, which we prove here. Combining the formula with two explicit families of seed roots, the real roots of the cycles $C_n$ and the real roots of the joins $C_m\vee C_n$ lying in $(-1,0)$, we prove that the closure of the real connected domination roots is $(-\infty ,0]$, and that the closure of all connected domination roots is the whole complex plane. These are the connected domination analogues of the root-density theorems of Brown and Tufts and of Brown and Beaton for the ordinary domination polynomial.

15 pages, 0 figures