Published in McSorley, J. P., & Feinsilver, P. (2009). Multivariate matching polynomials of cyclically labelled graphs. Discrete Mathematics, 309(10), 3205-3218 .


We consider the matching polynomials of graphs whose edges have been cyclically labelled with the ordered set of t labels {x1, . . ., xt}.

We first work with the cyclically labelled path, with first edge label xi, followed by N full cycles of labels {x1, . . ., xt}, and last edge label xj . Let Φ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} and Δ = (−1)t x1 · · ·xt. A combinatorial/algebraic proof and a matrix proof of this fact are given. Let GN denote the first fundamental solution to the (τ, Δ)-recurrence. We express GN (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.