The higher-order matching polynomial of a graph
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)xn−2j, called the matching polynomial of G, is closely related to the Hosoya index introduced in applications in physics and chemistry. In...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2005-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Online Access: | http://dx.doi.org/10.1155/IJMMS.2005.1565 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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)xn−2j, 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. |
|---|---|
| ISSN: | 0161-1712 1687-0425 |