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 1 , … , x t } . st work with the cyclically labelled path, with first edge label x i , followed by N full cycles of labels { x 1 , … , x t } , and last edge label x j . Let Φ i , N t + j denote the matching polynomial of this path. It satisfies the ( τ , Δ ) -recurrence: Φ i , N t + j = τ Φ i , ( N − 1 ) t + j − Δ Φ i , ( N − 2 ) t + j , where τ is the sum of all non-consecutive cyclic monomials in the variables { x 1 , … , x t } and Δ = ( − 1 ) t x 1 ⋯ x t . 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.