Weighted matchings of the square of a path and simplicial-clique deletion
Deleting a simplicial clique from a claw-free graph gives an interlacing weighted independence polynomial. For line graphs this is vertex deletion for weighted matching polynomials, and for the square of a path it makes consecutive weighted matching polynomials interlace.
Results
The square of the infinite path has vertex set $\mathbb N$ and edges $\{i,i+1\}$ (short) and $\{i,i+2\}$ (long). Give each short edge weight $u$ and each long edge weight $v$. Let $P_n(x)=P_n^{(u,v)}(x)$ be the weighted matching-generating polynomial of the path square on the vertices $0,\dots,n-1$. Then $P_0=P_1=1$, $P_2=1+ux$, $P_3=1+(2u+v)x$ and $$ P_{n+4}=P_{n+3}+u\,x\,P_{n+2}+v\,x\,P_{n+1}+v^2x^2P_n, $$ and this recurrence with these initial rows determines the family.
Theorem (path squares). If $u,v\ge0$, then every $P_n$ has constant term $1$, nonnegative coefficients and only real negative roots, and $P_n\ll P_{n+1}$ for all $n$. If $u>0$, then $\deg P_n=\lfloor n/2\rfloor$.
Theorem (simplicial-clique deletion). Let $G$ be a finite claw-free graph with weights $w(v)\ge0$, let $S$ be a vertex set, and let $K\subseteq S$ be a clique such that, for each $v\in K$, the neighbors of $v$ in $S\setminus K$ form a clique. Then the weighted independence polynomial of $G[S\setminus K]$ interlaces that of $G[S]$.
Corollary (vertex deletion). Let $G$ be a finite graph with edge weights $w(e)\ge0$ and let $v$ be a vertex. The weighted matching-generating polynomial of $G-v$ interlaces that of $G$.
Proof
The weighted matching-generating polynomial of $G$ is the weighted independence polynomial of the claw-free line graph $L(G)$. The edges at a vertex $v$ form a clique of $L(G)$ whose outside neighbors form a clique, so the clique deletion theorem gives the corollary. For path squares, delete the edges at the last vertex.
References
The clique deletion theorem refines the induction in [CS07]; see the Chudnovsky--Seymour page.
- [CS07] The roots of the independence polynomial of a clawfree graph. Journal of Combinatorial Theory, Series B, 97(3), 350-357, 2007.
BibTeX
@article{ChudnovskySeymour2007, doi = {10.1016/j.jctb.2006.06.001}, url2 = {https://doi.org/10.1016/j.jctb.2006.06.001}, year = {2007}, month = may, publisher = {Elsevier {BV}}, volume = {97}, number = {3}, pages = {350--357}, author = {Maria Chudnovsky and Paul Seymour}, title = {The roots of the independence polynomial of a clawfree graph}, journal = {Journal of Combinatorial Theory, Series B} }