On the matching polynomial of subdivision graphs

被引：17

作者：

Yan, Weigen ^{[1
]}

Yeh, Yeong-Nan ^{[2
]}

机构：

[1] Jimei Univ, Sch Sci, Xiamen 361021, Peoples R China

[2] Acad Sinica, Inst Math, Taipei 11529, Taiwan

来源：

DISCRETE APPLIED MATHEMATICS | 2009年 / 157卷 / 01期

关键词：

Subdivision; Matching polynomial; Matching generating function; Hosoya index; NUMBER; INDEX; TREES;

D O I：

10.1016/j.dam.2008.05.005

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (c) 2008 Elsevier B.V. All rights reserved.

引用

页码：195 / 200

页数：6

共 19 条

[1] MATRIX REPRESENTATION OF AN OLEFINIC REFERENCE STRUCTURE FOR MONOCYCLIC CONJUGATED COMPOUNDS [J].