On a relationship between the characteristic and matching polynomials of a uniform hypertree

Abstract

A hypertree is a connected hypergraph without cycles. Further a hypertree is called an $r$-tree if, additionally, it is $r$-uniform. Note that 2-trees are just ordinary trees. A classical result states that for any 2-tree $T$ with characteristic polynomial $\ddot{I}{•}_T(\hat{I}»)$ and matching polynomial $\ddot{I}{†}_T(\hat{I}»)$, then $\ddot{I}{•}_T(\hat{I}»)=\ddot{I}{†}_T(\hat{I}»).$ More generally, suppose $\mathcal{T}$ is an $r$-tree of size $m$ with $r\ge 2$. In this paper, we extend the above classical relationship to $r$-trees and establish that \[ ϕ_{\mathcal{T}}(λ)=\prod_{H \sqsubseteq \mathcal{T}}φ_{H}(λ)^{a_{H}}, \] where the product is over all connected subgraphs $H$ of $\mathcal{T}$, and the exponent $a_H$ of the factor $\ddot{I}{†}_H(\hat{I}»)$ can be written as \[ a_H=b^{m-e(H)-|\partial(H)|}c^{e(H)}(b-c)^{|\partial(H)|}, \] where $e(H)$ is the size of $H$, $\partial (H)$ is the boundary of $H$, and $b=(r-1{)}^{r-1},c=r^{r-2}$. In particular, for $r=2$, the above correspondence reduces to the classical result for ordinary trees. In addition, we resolve a conjecture by Clark-Cooper [{\em Electron. J. Combin.}, 2018] and show that for any subgraph $H$ of an $r$-tree $\mathcal{T}$ with $r\ge 3$, $\ddot{I}{†}_H(\hat{I}»)$ divides $\ddot{I}{•}_{\mathcal{T}}(\hat{I}»)$, and additionally $\ddot{I}{•}_H(\hat{I}»)$ divides $\ddot{I}{•}_{\mathcal{T}}(\hat{I}»)$, if either $r\ge 4$ or $H$ is connected when $r=3$. Moreover, a counterexample is given for the case when $H$ is a disconnected subgraph of a 3-tree.

36 pages, 4 figures