基于路的多重完全圖相關圖生成樹計數

譚秋月

（武夷學院數學與計算機系，福建武夷山354300）

基于路的多重完全圖相關圖生成樹計數

譚秋月

（武夷學院數學與計算機系，福建武夷山354300）

利用圖G的標定技巧、矩陣和行列式運算、補生成樹矩陣定理、不等式運算等理論，研究了當m=2, 3, 4, 5，且a1, a2, …, am為任意數時，基于路的多重完全圖相關圖一般情況的生成樹數目，并得到了相關公式。

多重完全圖相關圖；生成樹；補生成樹矩陣定理

0 引言

圖的生成樹數目是圖的重要不變量之一，其應用廣泛。例如在網絡可靠性方面有重要應用：一個網絡可以用一個圖G來模擬，這個網絡中所有的站點之間可以互相通訊，意味著圖G中必須包含一個生成樹，因此，圖的生成樹的數目是評價該圖（網絡）可靠性的重要指標之一，最大化生成樹的數目是加強網絡可靠性的一個途徑。

如果能得到一個圖G生成樹數目的計數公式對確定圖G在完全圖Kn中的補圖（即補圖類Kn-G，其中）的生成樹數目的計數公式也很有意義。文獻[1-3]給出了基于路的多重完全圖相關圖補圖類。本文討論當m=2, 3, 4, 5時基于路的多重完全圖相關圖生成樹的數目，并求出一般情況下（即a1, a2, …, am為任意數時）的計數公式。

1 圖的定義

假設G1=(V1, E1)和G2=(V2, E2)沒有公共頂點，以V1∩V2為頂點集，以E1, E2和為邊集所組成的圖，稱為G2和G2的聯圖，記為[4]。

特別地，一個頂點和完全圖Km的聯圖Km+1為完全圖，如圖1所示。

圖1 Fig.1

定義1[3]由m個完全圖Ka1+1, Ka2+1, Kam+1和連接這m個完全圖上的任意一點形成的路Pm所組成的圖，稱為一個基于路的多重完全圖，記為。

定義2[3]如果基于路的多重完全圖滿足ai≥2(i=1, 2, …, m)以及n≥m+ a1+…+am，在完全圖Kn中刪去圖所有的邊后組成的圖稱為基于路的多重完全圖相關圖，記為。

圖2為一個基于路的4重完全圖PK4(2, 2, 3, 2)，圖3為一個基于路的4重完全圖相關圖K15-PK4(2, 2, 3, 2)的補圖。

圖2 (2, 2, 3, 2)Fig.2(2, 2, 3, 2)

圖3 Fig.3

本文僅討論m=2, 3, 4, 5，且a1, a2, …, am為任意數時，多重完全圖相關圖生成樹數目的計數公式。

2.1 結論

定理1當m=2，且a1, a2為任意數時，基于路P2的多重完全圖相關圖的生成樹數目為

特殊地，當m=2，a1=a2=a時，的生成樹數目為

定理2當m=3，且a1, a2, a3為任意數時，基于路P3的多重完全圖相關圖的生成樹數目為

特殊地，當m=3，a1=a2=a3=a時，的生成樹數目為

定理3當m=4，且a1, a2, a3, a4為任意數時，基于路P4的多重完全圖相關圖的生成樹數目為

特殊地，當m=4，a1=a2=a3=a4=a時，的生成樹數目為

定理4當m=5，且a1, a2, a3, a4, a5為任意數時，基于路P5的多重完全相關圖的生成樹數目為

2.2 結論的證明

式中

因此，根據補生成樹矩陣定理[1]，生成樹的數目為。

3 結語

對定理1至定理4中的生成樹數目公式進行比較，沒有找到規律，目前無法用數學歸納法推導出圖更一般（即m為任意大于1的整數時）的生成樹數目的公式，希望在進一步工作中有所突破。

[1]Nikolopoulos S D，Rondogiannis P. On the Number of Spanning Trees of Multi-Star Related Graphs[J]. Information Processing Letters，1998，65(4)：183-188.

[2]Yan W M，Myrvold W，Chung K L. A Formula for the Number of Spanning Trees of a Multi-Star Related Graph [J]. Information Processing Letters, 1998, 68(6)：295-298.

[3]譚秋月.基于路的多重完全圖相關圖的生成樹數目[J].曲阜師范大學學報：自然科學版，2012，38(3)：47-52. Tan Qiuyue. The Number of Spanning Trees of Multi-Complete Related Graphs Based on Paths[J]. Journal of Qufu Normal University：Natural Science，2012，38(3)：47-52.

[4]李曉明，黃振杰. 圖中樹的數目計算及其在網絡可靠性中的作用[M]. 哈爾濱：哈爾濱工業大學出版社，1993：1-9. Li Xiaoming，Huang Zhenjie. The Number of Trees in Graph Calculation and Its Role in the Network Reliability [M]. Harbin：Harbin Institute of Technology Press，1993：1-9.

[5]譚秋月. 基于圈或路的多重星相關圖的生成樹數目[J].天津師范大學學報：自然科學版， 2013，33(1)：30-34. Tan Qiuyue. Number of Spanning Trees of Multi-Star Related Graphs Based on Cycles or Paths[J]. Journal of Tianjin Normal University：Natural Science Edition，2013，33(1)：30-34.

（責任編輯：鄧光輝）

The Path-Based Enumeration of Spanning Trees of Multi-Complete Related Graphs

Tan Qiuyue
（Department of Mathematics and Computer，Wuyi University，Wuyishan Fujian 354300，China）

By means of Graph G labeling techniques, matrix and determinant computations, the complement-spanning-tree matrix theorem and inequalities computing etc., studies the number of spanning trees of the general situation of the path-based multi-complete related graphswhen m=2, 3, 4, 5, and a1, a2, …, amare arbitrary numbers, and gets relative counting formula.

multi-complete related graphs；spanning trees；complement-spanning-tree matrix theorem

O157.5

A

1673-9833(2014)05-0001-04

10.3969/j.issn.1673-9833.2014.05.001

2014-01-18

福建省教育廳科技基金資助項目（JK2012056），武夷學院一般基金資助項目（xq0933）

譚秋月（1980-），女，陜西楊凌人，武夷學院講師，碩士，主要研究方向為圖論和離散數學，E-mail：tqyspa@163.com