谭秋月

（武夷学院数学与计算机系，福建武夷山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中删去图所有的边后组成的图称为基于路的多重完全图相关图，记为。……