Abstract
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.
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 .