Generating Orthogonal Polynomials and their Derivatives using Vertex|Matching-Partitions of Graphs

Abstract

A vertex$|$matching-partition $(V|M)$ of a simple graph $G$ is a spanning collection of vertices and independent edges of $G$. Let vertex $v\in V$ have weight $w_v$ and edge $e\in M$ have weight $w_e$. Then the weight of $V|M$ is $w(V|M)=\prod _{v\in V}{w}_v+\prod _{e\in M}{w}_e$. Define the vertex|matching-partition function of $G$ as $W(G)=\sum _{V|M}w(V|M)$.

In this paper, we study this function when $G$ is a path and a cycle. We generate all orthogonal polynomials as vertex|matching-partition functions of suitably labelled paths, and indicate how to find their derivatives in some cases. Here Taylor’s Expansion is used, and an application to associated polynomials is given. We also give a combinatorial interpretation of coefficients in the case of multiplicative and additive weights. Results are extended to the weighted cycle.