International Journal of Mathematics and Mathematical Sciences
Volume 2005 (2005), Issue 10, Pages 1565-1576

The higher-order matching polynomial of a graph

Oswaldo Araujo,1 Mario Estrada,2 Daniel A. Morales,3 and Juan Rada1

1Departamento de Matemáticas, Facultad de Ciencias, Universidad de Los Andes, Mérida 5101, Venezuela
2ICIMAF, La Habana, Cuba
3Facultad de Ciencias, Universidad de Los Andes, Apartado Postal A61, La Hechicera, Mérida 5101, Venezuela

Received 27 April 2004; Revised 1 March 2005

Copyright © 2005 Oswaldo Araujo et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


Given a graph G with n vertices, let p(G,j) denote the number of ways j mutually nonincident edges can be selected in G. The polynomial M(x)=j=0[n/2](1)jp(G,j)xn2j, called the matching polynomial of G, is closely related to the Hosoya index introduced in applications in physics and chemistry. In this work we generalize this polynomial by introducing the number of disjoint paths of length t, denoted by pt(G,j). We compare this higher-order matching polynomial with the usual one, establishing similarities and differences. Some interesting examples are given. Finally, connections between our generalized matching polynomial and hypergeometric functions are found.