کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649831 1342467 2009 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Multivariate matching polynomials of cyclically labelled graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 10, 28 May 2009, Pages 3205–3218
نویسندگان
, ,