## Abstract

We consider the matching polynomials of graphs whose edges have been cyclically labelled with the ordered set of *t* labels {*x*_{1}, . . ., *x _{t}*}.

We first work with the cyclically labelled path, with first edge label *x _{i}*, followed by

*N*full cycles of labels {

*x*

_{1}, . . .,

*x*}, and last edge label

_{t}*x*. Let Φ

_{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 {

*x*

_{1}, . . .,

*x*} and Δ = (−1)

_{t}^{t}

*x*

_{1}· · ·

*x*. A combinatorial/algebraic proof and a matrix proof of this fact are given. Let

_{t}*G*denote the first fundamental solution to the (τ, Δ)-recurrence. We express

_{N}*G*(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.

_{N}## Recommended Citation

McSorley, John P. and Feinsilver, Philip. "Multivariate Matching Polynomials of Cyclically Labelled Graphs." (Jan 2009).

## Comments

Published in McSorley, J. P., & Feinsilver, P. (2009). Multivariate matching polynomials of cyclically labelled graphs.

Discrete Mathematics, 309(10), 3205-3218 .