Log-concavity of the independence polynomials of ${\mathbf{W}}_p$ graphs

Abstract

Let $G$ be a graph of order $n$. For a positive integer $p$, $G$ is said to be a ${\mathbf{W}}_p$ graph if $n\ge p$ and every $p$ pairwise disjoint independent sets of $G$ are contained within $p$ pairwise disjoint maximum independent sets. In this paper, we establish that every connected ${\mathbf{W}}_p$ graph $G$ is $p$-quasi-regularizable if and only if $n\ge (p+1)\cdot \alpha$, where $\alpha$ is the independence number of $G$ and $p\ne 2$. This finding ensures that the independence polynomial of a connected ${\mathbf{W}}_p$ graph $G$ is log-concave whenever $(p+1)\cdot \alpha \le n\le p\cdot \alpha +2\sqrt{p\cdot \alpha +p}$ and $\frac{{\alpha }^2}{4\left(\alpha +1\right)}\le p$, or $p\cdot \alpha +2\sqrt{p\cdot \alpha +p}<n\le \frac{\left({\alpha }^2+1\right)\cdot p+{\left(\alpha -1\right)}^2}{\alpha -1}$ and $\frac{\alpha \left(\alpha -1\right)}{\alpha +1}\le p$. Moreover, the clique corona graph $G\circ K_p$ serves as an example of the ${\mathbf{W}}_p$ graph class. We further demonstrate that the independence polynomial of $G\circ K_p$ is always log-concave for sufficiently large $p$. Keywords: very well-covered graph; quasi-regularizable graph; corona graph; ${\mathbf{W}}_p$ graph; independence polynomial; log-concavity.

16 pages, 2 figures