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 $\phi_T(\lambda)$ and matching polynomial $\varphi_T(\lambda)$, then $\phi_T(\lambda)=\varphi_T(\lambda).$ More generally, suppose $\mathcal{ T}$ is an $r$-tree of size $m$ with $r\geq2$. In this paper, we extend the above classical relationship to $r$-trees and establish that \[ \phi_{ \mathcal{ T}}(\lambda)=\prod_{ H \sqsubseteq \mathcal{ T}}\varphi_{ H}(\lambda)^{ a_{ H}}, \] where the product is over all connected subgraphs $H$ of $\mathcal{ T}$, and the exponent $a_{ H}$ of the factor $\varphi_{ H}(\lambda)$ 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\geq3$, $\varphi_H(\lambda)$ divides $\phi_{ \mathcal{ T}}(\lambda)$, and additionally $\phi_H(\lambda)$ divides $\phi_{ \mathcal{ T}}(\lambda)$, if either $r\geq 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.

Categories: math.CO

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