Multivariate matching polynomials of cyclically labelled graphs

We consider the matching polynomials of graphs whose edges have been cyclically labelled with the ordered set of t labels {x₁,…,x_t}.We first work with the cyclically labelled path, with first edge label x_i, followed by N full cycles of labels {x₁,…,x_t}, and last edge label x_j. Let Φ_i,Nt+j denote the matching polynomial of this path. It satisfies the (τ,Δ)-recurrence: , where τ is the sum of all non-consecutive cyclic monomials in the variables {x₁,…,x_t} and . A combinatorial/algebraic proof and a matrix proof of this fact are given. Let G_N denote the first fundamental solution to the (τ,Δ)-recurrence. We express G_N (i) as a cyclic binomial using the symmetric representation of a matrix, (ii) in terms of Chebyshev polynomials of the second kind in the variables τ and Δ, and (iii) as a quotient of two matching polynomials. We extend our results from paths to cycles and rooted trees.