首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号