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 tt labels {x1,…,xt}{x1,…,xt}.We first work with the cyclically labelled path, with first edge label xixi, followed by NN full cycles of labels {x1,…,xt}{x1,…,xt}, and last edge label xjxj. Let Φi,Nt+jΦi,Nt+j denote the matching polynomial of this path. It satisfies the (τ,Δ)(τ,Δ)-recurrence: Φi,Nt+j=τΦi,(N−1)t+j−ΔΦi,(N−2)t+j, where ττ is the sum of all non-consecutive cyclic monomials in the variables {x1,…,xt}{x1,…,xt} and Δ=(−1)tx1⋯xt. A combinatorial/algebraic proof and a matrix proof of this fact are given. Let GNGN denote the first fundamental solution to the (τ,Δ)(τ,Δ)-recurrence. We express GNGN (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.