Mathematics – Combinatorics
Scientific paper
2009-09-09
Advances in Applied Mathematics, vol 46, no 1-4, January 2011, pp 226-246
Mathematics
Combinatorics
21 pages, many TikZ figures; v2: minor clarifications and additions
Scientific paper
10.1016/j.aam.2009.12.008
We show combinatorially that the higher-order matching polynomials of several families of graphs are d-orthogonal polynomials. The matching polynomial of a graph is a generating function for coverings of a graph by disjoint edges; the higher-order matching polynomial corresponds to coverings by paths. Several families of classical orthogonal polynomials -- the Chebyshev, Hermite, and Laguerre polynomials -- can be interpreted as matching polynomials of paths, cycles, complete graphs, and complete bipartite graphs. The notion of d-orthogonality is a generalization of the usual idea of orthogonality for polynomials and we use sign-reversing involutions to show that the higher-order Chebyshev (first and second kinds), Hermite, and Laguerre polynomials are d-orthogonal. We also investigate the moments and find generating functions of those polynomials.
No associations
LandOfFree
Higher order matching polynomials and d-orthogonality does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Higher order matching polynomials and d-orthogonality, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Higher order matching polynomials and d-orthogonality will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-385834