1. 引言
在这篇文章中考虑的图都是有限、无向、简单的图。图G的剖分图,记作
,指的是图G的每条边用P2替代之后得到的图。图G的全图,记作
,顶点集是图 的顶点集与边集的不交并,两顶点相邻当且仅当所对应的两个元素在图G中是相邻的。
图
中电阻距离的概念最早由Klein和Randić在 [1] 中提出来。图G是连通图,
和
分别是图G的顶点集和边集。在图G中顶点vi和vj之间的电阻距离,记作
,指的是把图G中的每条边看作一个单位电阻由欧姆定律计算得到的节点vi和vj之间的有效电阻。图G中顶点vi和vj之间的普通距离,记作
,指的是vi和vj之间最短路的长度。在 [2] 中,图G的Wiener指标被定义为
。在 [2] 中定义了一个与Wiener指标相似的和式
,后来在 [3] 中被称作图G的基尔霍夫指标。Klein和Randić在 [1] 中证明了
,因此
,等式成立当且仅当图G是树;基尔霍夫指标在物理解释、电路学、图论、化学等方面有广泛的应用 [5] 。例如,Gutman和Mohar在 [4] 中已经证明有
个顶点的连通图的基尔霍夫指标是它的顶点数与所有非零拉普拉斯特征值倒数之和的乘积。
增强超立方体
(
,
)是超立方体
的一个重要变型网络,指的是顶点集为
的一个无向简单图,两顶点
和
相邻,只需Y满足其中之一的条件:1)
,
;2)
。由此定义,我们可以看出
是
的一个子图。事实上,
是一个顶点数为
,边数为
的
正则图。当
时,就是我们熟知的折叠超立方体
。
本文的框架如下。第二部分,我们给出了一些文中要用到的基本定义和引理。第三部分,我们给出了主要结果以及证明。
2. 基本定义和引理
图G的邻接矩阵是一个
阶的实对称矩阵,记作
,其
阶元素是1若顶点vi和vj相邻,否则为0。对
,记
是vi的邻集,即
。我们把
的阶数称作是vi的度数,记作di。图G的度对角矩阵记为
,其第i个对角元素就等于di。图G的拉普拉斯矩阵定义为
,记
为图G的拉普拉斯特征值。图G的拉普拉斯特征值以及重数构成的多重集称为图G的拉普拉斯谱,记作
。
引理2.1: [1] 设图G是一个连通图,顶点数
,则
其中
是图G的非零拉普拉斯特征值。
引理2.2: [6] [7] 设图G是一个d正则的连通图,顶点数和边数分别为n和m,则
1)
。
2)
。
3)
。
其中
,
和
分别是图
,
和
的拉普拉斯矩阵的特征多项式。
引理2.3: [6] 设
,
,为增强超立方体
的拉普拉斯特征多项式,那么
其中
分别为多项式
中x和
的系数。
引理2.4:设
,增强超立方体
的基尔霍夫指标为
引理2.5:设
,增强超立方体
的拉普拉斯谱为
,
其中
,
,且
。
3. 增强超立方体剖分图和全图的基尔霍夫指标
为了方便,我们把增强超立方体
的顶点数和边数分别记为p和q,显然,
,
。记
的拉普拉斯特征值为
。
下面我们首先给出增强超立方体
的剖分图
的基尔霍夫指标。
定理3.1:设
,
为增强超立方体
的剖分图,则我们可得
1)
,若n和k有相同的奇偶性;
2)
,若n和k有不同的奇偶性。
证明:假设
,
,
,为增强超立方体
的拉普拉斯特征多项式。则由引理2.2 (2)得
故我们可以得到在
中
的系数为
。
而在
中x的系数为
。
另外,注意到
有
多个顶点,由引理2.3,可得
化简上述等式可得
将引理2.4的结果代入上式可得,增强超立方体
的剖分图
的基尔霍夫指标如下:
若n和k有相同的奇偶性,则
。
若n和k有不同的奇偶性,则
。
证毕。
定理3.2:设
,
为增强超立方体
的全图,则我们可得
1) 若n和k有相同的奇偶性,则
2) 若n和k有不同的奇偶性,则
证明:我们都知道增强超立方体
是
正则的。则由引理2.2 (3)可得
,
其中
是
的非零拉普拉斯特征值。设b,c分别是
中
和x的系数,则
。
且
。
注意到
有
个顶点,由引理2.3可得
将
,
代入上式并化简上式,可得
再将引理2.4和引理2.5的结果代入上式,由此可得增强超立方体全图的基尔霍夫指标如下:
若n和k有相同的奇偶性,则
若n和k有不同的奇偶性,则
证毕。