The \(m\)-path cover polynomial of a graph and a model for general coefficient linear recurrences (Q2248725)

Summary: An \(m\)-path cover \(\Gamma=\{P_{\ell_1},P_{\ell_2},\dots,P_{\ell_r}\}\) of a simple graph \(G\) is a set of vertex disjoint paths of \(G\), each with \(\ell_k\leq m\) vertices, that span \(G\). With every \(P_\ell\) we associate a weight, \(\omega(P_\ell)\), and define the weight of \(\Gamma\) to be \(\omega(\Gamma)=\prod_{k=1}^r\omega(P_{\ell_k})\). The \(m\)-path cover polynomial of \(G\) is then defined as \(\mathbb P_m(G)=\sum_\Gamma\omega(\Gamma)\) where the sum is taken over all \(m\)-path covers \(\Gamma\) of \(G\). This polynomial is a specialization of the path-cover polynomial of Farrell. We consider the \(m\)-path cover polynomial of a weighted path \(P(m-1,n)\) and find the \((m+1)\)-term recurrence that it satisfies. The matrix form of this recurrence yields a formula equating the trace of the recurrence matrix with the \(m\)-path cover polynomial of a suitably weighted cycle \(C(n)\). A directed graph, \(T(m)\), the edge-weighted \(m\)-trellis, is introduced and so a third way to generate the solutions to the above \((m+1)\)-term recurrence is presented. We also give a model for general-term linear recurrences and time-dependent Markov chains.