On the matching polynomial of subdivision graphs |
| |
Authors: | Weigen Yan Yeong-Nan Yeh |
| |
Institution: | a School of Sciences, Jimei University, Xiamen 361021, China b Institute of Mathematics, Academia Sinica, Taipei 11529, Taiwan |
| |
Abstract: | Let G be a simple graph and let S(G) be the subdivision graph of G, which is obtained from G by replacing each edge of G by a path of length two. In this paper, by the Principle of Inclusion and Exclusion we express the matching polynomial and Hosoya index of S(G) in terms of the matchings of G. Particularly, if G is a regular graph or a semi-regular bipartite graph, then the closed formulae of the matching polynomial and Hosoya index of S(G) are obtained. As an application, we prove a combinatorial identity. |
| |
Keywords: | Subdivision Matching polynomial Matching generating function Hosoya index |
本文献已被 ScienceDirect 等数据库收录! |
|