Higher-order matching polynomials and d-orthogonality

DOI10.1016/J.AAM.2009.12.008zbMATH Open1227.05256arXiv0909.1655OpenAlexW2150723726MaRDI QIDQ534193FDOQ534193

Authors: Dan Drake 

Publication date: 17 May 2011

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/0909.1655

Recommendations

• Generalization of matching extensions in graphs -- combinatorial interpretation of orthogonal and \(q\)-orthogonal polynomials
• Matching polynomials and duality
• The higher-order matching polynomial of a graph
• Higher order matching polynomial
• scientific article; zbMATH DE number 3989395

zbMATH Keywords

orthogonal polynomials\(d\)-orthogonalitymatching polynomials

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15) Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.) (33C45)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Title not available (Why is that?)
• On the theory of the matching polynomial
• L'orthogonalité et les récurrences de polynômes d'ordre supérieur à deux
• Combinatorial aspects of continued fractions
• Distribution of crossings, nestings and alignments of two edges in matchings and partitions
• The umbral calculus
• Catalan numbers, their generalization, and their uses
• A Course in Enumeration
• Octabasic Laguerre polynomials and permutation statistics
• Title not available (Why is that?)
• Hermite polynomials and a duality relation for matchings polynomials
• Title not available (Why is that?)
• On a general class of graph polynomials
• The Combinatorics of Laguerre, Charlier, and Hermite Polynomials
• Higher-order Fibonacci numbers
• Combinatoire des polynômes orthogonaux classiques: Une approche unifiée. (Combinatorics of classical orthogonal polynomials: A unified approach)
• The higher-order matching polynomial of a graph
• Orthogonal polynomials and combinatorics
• Title not available (Why is that?)
• Counting on Chebyshev polynomials
• Fibonacci polynomials: compositions and cyclic products
• Title not available (Why is that?)
• Specializations of Generalized Laguerre Polynomials
• Title not available (Why is that?)
• Path decompositions of chains and circuits

Cited In (8)

• Matching polynomials and duality
• On a class of polynomial sets generated by \(F(xt-R(t))\)
• Higher order matching polynomial
• A generalization of the symmetric classical polynomials: Hermite and Gegenbauer polynomials
• Generalization of matching extensions in graphs -- combinatorial interpretation of orthogonal and \(q\)-orthogonal polynomials
• On semi-classical \(d\)-orthogonal polynomials
• Title not available (Why is that?)
• Orthogonal polynomials through complex matrix graph theory

Uses Software

• OEIS

This page was built for publication: Higher-order matching polynomials and \(d\)-orthogonality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q534193)