广义轮型完全多部图的生成树数  

THE NUMBER OF SPANNING TREES IN GENERALIZED COMPLETE MULTIPARTITE GRAPHS OF WHEEL-TYPE

作　　者：左亚丽[1] 蔡俊亮[2] 

机构地区：[1]河北民族师范学院数学与计算机系,承德067000 [2]北京师范大学数学科学学院,数学与复杂系统教育部重点实验室,北京100875

出　　处：《北京师范大学学报（自然科学版）》2012年第4期335-340,共6页Journal of Beijing Normal University(Natural Science)

基　　金：中央高校基本科研业务费专项资金资助项目;北京师范大学重点学科基金资助项目

摘　　要：证明了如下结论:设KWk,n是由轮图集W={Wn1,Wn2,…,Wnk}生成的n阶广义轮型完全k-部图,其中n={n1,n2,…,nk},n=|n|=n1+n2+…+nk,1≤k≤n.那么KWk,n的生成树数目为t(KWk,n)=n2k-2∏ki=1αni-1i+βni-1i-2n-ni+1,其中αi=(di+d2i-4)/2,βi=(di-d2i-4)/2,di=n-ni+3.The following is proved in this paper. Let Kk,n^W be a generalized complete k-partitegraph of order n spanned by the wheel set W={Wn,Wn2,…,Wnk}wheren n={n,n2,…,nk},n=｜n｜=n1＋n2＋n2＋…nk,1≤k≤n.then the number of spanning trees in Kk,n^W is t（Kk,n^W）=n^2k-2∏i=1^kai^ni-1＋βi^ni-1-2/n-ni＋1, and ai=（di＋√di^2-4）/2,βi-（di-√di^2-4）/2,di=n-ni＋3.

关 键 词：简单连通图 完全图 k-部图 树 

分 类 号：O157.5[理学—数学]