Symmetry characterization for independence polynomials of lexicographic products

There is a terminology discrepancy: in the original conjecture, $G\circ H$ denotes the corona product, not the lexicographic product. The two interpretations have different answers.

For the lexicographic product appearing in the problem description, the stated characterization is false. Take

$$G=K_2,\qquad H=K_2-e=2K_1.$$

Then

$$G[H]=K_{2,2}, \qquad I(G[H];x)=1+4x+2x^2,$$

which is not symmetric. Thus $H=K_2-e$ already contradicts the claimed lexicographic-product conclusion.

For the corona product used by the original paper, the intended conjecture is true. In fact the following stronger two-test characterization holds:

$$I(G\circ H;x)\text{ is symmetric for every graph }G$$

if and only if it is symmetric for $G=K_1$ and $G=K_2$, if and only if

$$H\cong K_r-e \quad\text{for some }r\ge2.$$

Write $P(x)=I(H;x)$. If $G$ has $n$ vertices, classification by the independent set of selected base vertices gives

$$I(G\circ H;x)=P(x)^nI\left(G;\frac{x}{P(x)}\right). \tag{1}$$

In particular,

$$I(K_1\circ H;x)=P(x)+x=:Q(x),$$ $$I(K_2\circ H;x)=P(x)^2+2xP(x)=Q(x)^2-x^2. \tag{2}$$

Suppose both polynomials in (2) are symmetric. If $H$ is empty, the second polynomial is $1+2x$, which is not symmetric. If $\alpha(H)=1$, write

$$P(x)=1+rx,\qquad r\ge1.$$

Then $Q(x)=1+(r+1)x$ is not symmetric. Hence

$$d:=\alpha(H)\ge2.$$

Now $Q$ has degree $d$, and both $Q^2$ and $Q^2-x^2$ have degree $2d$. Since $Q$ is symmetric, $Q^2$ is symmetric of degree $2d$. Subtracting the two symmetric degree-$2d$ polynomials shows that $x^2$ itself must be symmetric in degree $2d$. Thus

$$x^2=x^{2d}(1/x)^2=x^{2d-2},$$

forcing $d=2$.

Write

$$P(x)=1+rx+s_2x^2,\qquad r=|V(H)|.$$

Symmetry of

$$Q(x)=1+(r+1)x+s_2x^2$$

forces $s_2=1$. Therefore $H$ has exactly one independent vertex pair, equivalently exactly one missing edge:

$$H\cong K_r-e.$$

Conversely, for $H=K_r-e$,

$$P(x)=1+rx+x^2,\qquad x^2P(1/x)=P(x),$$

and

$$\frac{1/x}{P(1/x)}=\frac{x}{P(x)}.$$

Since $\alpha(G\circ H)=2n$, formula (1) gives

$$\begin{aligned} x^{2n}I(G\circ H;1/x) &=[x^2P(1/x)]^n I\left(G;\frac{1/x}{P(1/x)}\right)\\ &=P(x)^nI\left(G;\frac{x}{P(x)}\right) =I(G\circ H;x). \end{aligned}$$

Hence the corona independence polynomial is symmetric for every graph $G$. The original corona conjecture is therefore proved, while the differently worded lexicographic-product statement is disproved.