Let G and H be graphs, let I(G;x) denote the independence polynomial of G, and let G circ H denote their lexicographic product. Symmetry characterization. I(G circ H;x) is symmetric for every graph G if and only if H=K_r-e for some r≥ 2. This characterizes the graphs H for which lexicographic products have symmetric independence polynomials for every choice of G. The source presents the statement in its conclusions, but the supplied text gives no evidence that it has been proved or resolved.

Symmetry characterization for independence polynomials of lexicographic products

About 13 years old · traced to 2013

Let $G$ and $H$ be graphs, let $I(G;x)$ denote the independence polynomial of $G$ , and let $G\circ H$ denote their lexicographic product.

Symmetry characterization. $I(G\circ H;x)$ is symmetric for every graph $G$ if and only if $H=K_r-e$ for some $r\geq 2$ .

This characterizes the graphs $H$ for which lexicographic products have symmetric independence polynomials for every choice of $G$ . The source presents the statement in its conclusions, but the supplied text gives no evidence that it has been proved or resolved.

References

Primary source

Vadim E. Levit and Eugen Mandrescu, “On f-Symmetries of the Independence Polynomial”, arXiv:1303.2564 (2013).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A posted explicit example claims the lexicographic statement is false, while the published result concerns a different graph product and does not settle this version.

The statement uses the lexicographic product, whereas the stored 2013 paper uses the same notation for the corona product. That paper records the analogous corona characterization as a conjecture, not as a theorem.

Known results

Levit and Mandrescu (2013): for the corona product and $H=K_r-e$ , $I(G\circ H;x)$ is symmetric and unimodal for every graph $G$ .
The same paper proves $f$ -symmetry for corona products when $\alpha(H)=2$ , but does not prove the claimed characterization.

Posted attempt

A posted calculation claims a counterexample to the lexicographic statement: $G=K_2$ and $H=K_2-e=2K_1$ give $G[H]=K_{2,2}$ and $I(G[H];x)=1+4x+2x^2$ , which is not symmetric. It also claims a stronger two-test proof for the intended corona conjecture. Neither claim has been independently verified.

Current status (as of August 2026): The lexicographic characterization has an explicit unverified counterexample claim, while the published source establishes only corona-product partial results and the corona characterization remains unverified here.

Sources

arxiv.org

CounterexampleThis solution needs a summarySee full solutionHide full solution

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.