链状割点图的Hosoya多项式

摘要

任一连通图的Hosoya多项式的定义如下:H(G)≡H(G,x):=∑d(G,k)xk k≥0,其中d(G,k)是图G中距离为k的点对的个数。事实上,d(G,0)等于图G的点数,而d(G,k)等于图G的边数。设{Gi}ni=1是一个两两不交的图的集合,并且Vi,Vi∈V(Gi),所谓链图C(G1,G2,…,Gn)≡C(G1,G2,…Gn;v1,w1,v2,w2,…,vn,wn)指的是将各点对wi和vi+1粘合起来而得到的图,其中i=1,2,…,n-1。文章得到了链状割点图的Hosoya多项式,并且,作为引理,并给出了树的Hosoya多项式。