ABSTRACT

The resistance distance between any two vertices of G is defined as the network effective resistance between them if each edge of G is replaced by a unit resistor. The Kirchhoff index $Kf\left(G\right)$ is the sum of the resistance distances between all the pairs of vertices in G. In this paper, we obtained the relationship of Kirchhoff index between enhanced hypercube networks $Q_{n,k}$ and its two variant networks $s\left(Q_{n,k}\right)$ and $t\left(Q_{n,k}\right)$ , by deducing the characteristic polynomial of the Laplacian matrix related networks. Meanwhile, the special formulas for the Kirchhoff indexes of $s\left(Q_{n,k}\right)$ and $t\left(Q_{n,k}\right)$ were proposed, respectively.

Keywords:Enhanced Hypercube, Kirchhoff Index, Resistance Distance

增强超立方体剖分图和全图的基尔霍夫指标

许萍

新疆大学数学与系统科学学院，新疆 乌鲁木齐

收稿日期：2019年4月2日；录用日期：2019年4月17日；发布日期：2019年4月24日

摘 要

图G任意两个顶点之间的电阻距离指的是它们之间的网络有效电阻，如果将图G的每一条边都用一个单位电阻代替，图G的基尔霍夫指标指的是图G的所有点对之间电阻距离之和。在本文中，我们通过推导增强超立方体网络 $Q_{n,k}$ 和它的两个变型网络 $s\left(Q_{n,k}\right)$ 和 $t\left(Q_{n,k}\right)$ 的拉普拉斯特征多项式的关系，从而得到了增强超立方体网络 $Q_{n,k}$ 和它的两个变型网络 $s\left(Q_{n,k}\right)$ 和 $t\left(Q_{n,k}\right)$ 的基尔霍夫指标的关系。同时，我们还分别得到了 $s\left(Q_{n,k}\right)$ 和 $t\left(Q_{n,k}\right)$ 的具体的基尔霍夫指标公式。

关键词 :增强超立方体，基尔霍夫指标，电阻距离

Copyright © 2019 by author and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

在这篇文章中考虑的图都是有限、无向、简单的图。图G的剖分图，记作 $s\left(G\right)$，指的是图G的每条边用P₂替代之后得到的图。图G的全图，记作 $t\left(G\right)$，顶点集是图 的顶点集与边集的不交并，两顶点相邻当且仅当所对应的两个元素在图G中是相邻的。

图 $G=\left(V,E\right)$ 中电阻距离的概念最早由Klein和Randić在 [1] 中提出来。图G是连通图， $V=\left\{v_1,v_2,\cdots ,v_n\right\}$ 和 $E=\left\{e_1,e_2,\cdots ,e_m\right\}$ 分别是图G的顶点集和边集。在图G中顶点v_i和v_j之间的电阻距离，记作 $r_{ij}$，指的是把图G中的每条边看作一个单位电阻由欧姆定律计算得到的节点v_i和v_j之间的有效电阻。图G中顶点v_i和v_j之间的普通距离，记作 $d_{ij}$，指的是v_i和v_j之间最短路的长度。在 [2] 中，图G的Wiener指标被定义为 $W\left(G\right)={\displaystyle {\sum }_{i<j}{d}_{ij}}$。在 [2] 中定义了一个与Wiener指标相似的和式 $Kf\left(G\right)={\displaystyle {\sum }_{i<j}{r}_{ij}}$，后来在 [3] 中被称作图G的基尔霍夫指标。Klein和Randić在 [1] 中证明了 $r_{ij}\le d_{ij}$，因此 $Kf\left(G\right)\le W\left(G\right)$，等式成立当且仅当图G是树；基尔霍夫指标在物理解释、电路学、图论、化学等方面有广泛的应用 [5] 。例如，Gutman和Mohar在 [4] 中已经证明有 $n\left(n\ge 2\right)$ 个顶点的连通图的基尔霍夫指标是它的顶点数与所有非零拉普拉斯特征值倒数之和的乘积。

增强超立方体 $Q_{n,k}$ ( $n\ge 2$ , $1\le k\le n-1$ )是超立方体 $Q_n$ 的一个重要变型网络，指的是顶点集为 $V=\left\{x_1{x}_2\cdots x_n|x_i=0\text{or}1,i=1,2,\cdots ,n\right\}$ 的一个无向简单图，两顶点 $X=x_1{x}_2\cdots x_n$ 和 $Y=y_1{y}_2\cdots y_n$ 相邻，只需Y满足其中之一的条件：1) $Y=x_1{x}_2\cdots x_{i-1}{\bar{x}}_i{x}_{i+1}\cdots x_n$，$1\le i\le n$ ；2) $Y=x_1{x}_2\cdots x_{k-1}{\bar{x}}_k{\bar{x}}_{k+1}\cdots {\bar{x}}_n$。由此定义，我们可以看出 $Q_n$ 是 $Q_{n,k}$ 的一个子图。事实上， $Q_{n,k}$ 是一个顶点数为 $2^n$，边数为 $\left(n+1\right)2^{n-1}$ 的 $\left(n+1\right)$ 正则图。当 $k=1$ 时，就是我们熟知的折叠超立方体 $F{Q}_n$。

本文的框架如下。第二部分，我们给出了一些文中要用到的基本定义和引理。第三部分，我们给出了主要结果以及证明。

2. 基本定义和引理

图G的邻接矩阵是一个 $n\times n$ 阶的实对称矩阵，记作 $A\left(G\right)$，其 $\left(i,j\right)$ 阶元素是1若顶点v_i和v_j相邻，否则为0。对 $v_i\in V$，记 $N\left(v_i\right)$ 是v_i的邻集，即 $N\left(v_i\right)=\left\{v_j\in V|v_j~v_i\right\}$。我们把 $N\left(v_i\right)$ 的阶数称作是v_i的度数，记作d_i。图G的度对角矩阵记为 $D\left(G\right)$，其第i个对角元素就等于d_i。图G的拉普拉斯矩阵定义为 $L\left(G\right)=D\left(G\right)-A\left(G\right)$，记 ${\mu }_1\ge \cdots \ge {\mu }_n=0$ 为图G的拉普拉斯特征值。图G的拉普拉斯特征值以及重数构成的多重集称为图G的拉普拉斯谱，记作 ${\text{Spec}}_L\left(G\right)$。

引理2.1： [1] 设图G是一个连通图，顶点数 $n\ge 2$，则

$Kf\left(G\right)=n\underset{i=1}{\overset{n-1}{{\displaystyle \sum }}}\frac{1}{{\mu }_i}$

其中 ${\mu }_i$ 是图G的非零拉普拉斯特征值。

引理2.2： [6] [7] 设图G是一个d正则的连通图，顶点数和边数分别为n和m，则

1) $P_{L\left(l\left(G\right)\right)}={\left(x-2d\right)}^{m-n}{P}_{L\left(G\right)}\left(x\right)$。

2) $P_{L\left(s\left(G\right)\right)}={\left(-1\right)}^n{\left(2-x\right)}^{m-n}{P}_{L\left(G\right)}\left(x\left(d+2-x\right)\right)$。

3) $P_{L\left(t\left(G\right)\right)}=x\left(x-d-2\right){\left(x-2d-2\right)}^{m-n}\underset{i=1}{\overset{n-1}{{\displaystyle \prod }}}\left[\left(x^2-2x-dx\right)+\left(3-2x+d\right){\mu }_i+{\mu }_i^2\right]$。

其中 $P_{L\left(l\left(G\right)\right)}\left(x\right)$，$P_{L\left(s\left(G\right)\right)}\left(x\right)$ 和 $P_{L\left(t\left(G\right)\right)}\left(x\right)$ 分别是图 $l\left(G\right)$，$s\left(G\right)$ 和 $t\left(G\right)$ 的拉普拉斯矩阵的特征多项式。

引理2.3： [6] 设 $P_{L\left(Q_{n,k}\right)}\left(x\right)=x^{2^n}+a_1{x}^{2^n-1}+\cdots +a_{2^n-2}{x}^2+a_{2^n-1}x$，$1\le k\le n$，为增强超立方体 $Q_{n,k}$ 的拉普拉斯特征多项式，那么

$\frac{Kf\left(Q_{n,k}\right)}{2^n}=-\frac{a_{2^n-2}}{a_{2^n-1}}$

其中 $a_{2^n-1},a_{2^n-2}$ 分别为多项式 $P_{L\left(Q_{n,k}\right)}\left(x\right)$ 中x和 $x^2$ 的系数。

引理2.4：设 $1\le k\le n-1$，增强超立方体 $Q_{n,k}$ 的基尔霍夫指标为

$Kf\left(Q_{n,k}\right)=\{\begin{array}{l}{2}^{n-1}\underset{t=0}{\overset{n}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{1}{t+1}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)n\equiv k\left(\mathrm{mod}2\right)\\ 2^{n-1}\underset{t=0}{\overset{n-1}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{1}{t+1}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)n\cancel{\equiv }k\left(\mathrm{mod}2\right)\end{array}$

引理2.5：设 $1\le k\le n-1$，增强超立方体 $Q_{n,k}$ 的拉普拉斯谱为

${\text{Spec}}_L\left(Q_{n,k}\right)=\left\{0,{\left[2\right]}^{k-1},{\left[2t+2\right]}^{{\gamma }_t},{\left[2n+2\right]}^{{\gamma }_n}|t=1,2,\cdots ,n-1\right\}$，

其中 ${\gamma }_t=\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)$，$1\le t\le n-1$，且 ${\gamma }_n=\underset{j=1}{\overset{n}{{\displaystyle \sum }}}\left(\begin{array}{c}n-k+1\\ 2j-1\end{array}\right)\left(\begin{array}{c}k-1\\ n+1-2j\end{array}\right)$。

3. 增强超立方体剖分图和全图的基尔霍夫指标

为了方便，我们把增强超立方体 $Q_{n,k}$ 的顶点数和边数分别记为p和q，显然， $p=2^n$，$q=\left(n+1\right)2^{n-1}$。记 $Q_{n,k}$ 的拉普拉斯特征值为 ${\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_n\ge {\mu }_{n+1}\ge \cdots \ge {\mu }_{2^n-1}\ge {\mu }_{2^n}=0$。

下面我们首先给出增强超立方体 $Q_{n,k}$ 的剖分图 $s\left(Q_{n,k}\right)$ 的基尔霍夫指标。

定理3.1：设 $1\le k\le n-1$，$s\left(Q_{n,k}\right)$ 为增强超立方体 $Q_{n,k}$ 的剖分图，则我们可得

1) $Kf\left(s\left(Q_{n,k}\right)\right)={\left(n+3\right)}^2{2}^{n-2}\left(\underset{t=0}{\overset{n}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{1}{t+1}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)\right)+\left(n-1\right)\left(n+3\right)2^{2n-3}+2^{n-1}$，若n和k有相同的奇偶性；

2) $Kf\left(s\left(Q_{n,k}\right)\right)={\left(n+3\right)}^2{2}^{n-2}\left(\underset{t=0}{\overset{n-1}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{1}{t+1}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)\right)+\left(n-1\right)\left(n+3\right)2^{2n-3}+2^{n-1}$，若n和k有不同的奇偶性。

证明：假设 $n\ge 2$，$P_{L\left(Q_{n,k}\right)}\left(x\right)=x^{2^n}+a_1{x}^{2^n-1}+\cdots +a_{2^n-2}{x}^2+a_{2^n-1}x$，$1\le k\le n$，为增强超立方体 $Q_{n,k}$ 的拉普拉斯特征多项式。则由引理2.2 (2)得

$\begin{array}{c}{P}_{L\left(s\left(Q_{n,k}\right)\right)}={\left(-1\right)}^p{\left(2-x\right)}^{q-p}{P}_{L\left(Q_{n,k}\right)}\left(x\left(n+3-x\right)\right)\\ ={\left(-1\right)}^p{\left(2-x\right)}^{q-p}[x^{2^n}{\left(n+3-x\right)}^{2^n}+a_1{x}^{2^n-1}{\left(n+3-x\right)}^{2^n-1}+\cdots \\ +a_{2^n-2}{x}^2{\left(n+3-x\right)}^2+a_{2^n-1}x\left(n+3-x\right)]\end{array}$

故我们可以得到在 $P_{L\left(s\left(Q_{n,k}\right)\right)}\left(x\right)$ 中 $x^2$ 的系数为

${\left(-1\right)}^p{2}^{q-p}\left[{\left(n+3\right)}^2{a}_{2^n-2}-a_{2^n-1}-\left(q-p\right)\left(n+3\right)2^{-1}{a}_{2^n-1}\right]$。

而在 $P_{L\left(s\left(Q_{n,k}\right)\right)}\left(x\right)$ 中x的系数为 ${\left(-1\right)}^p{2}^{q-p}\left(n+3\right)a_{2^n-1}$。

另外，注意到 $s\left(Q_{n,k}\right)$ 有 $q+p=\left(n+1\right)2^{n-1}+2^n$ 多个顶点，由引理2.3，可得

$\begin{array}{c}\frac{Kf\left(s\left(Q_{n,k}\right)\right)}{2^n+\left(n+1\right)2^{n-1}}=-\frac{{\left(n+3\right)}^2{a}_{2^n-2}-a_{2^n-1}-\left(q-p\right)\left(n+3\right)2^{-1}{a}_{2^n-1}}{\left(n+3\right)a_{2^n-1}}\\ =-\left(n+3\right)\frac{a_{2^n-2}}{a_{2^n-1}}+\frac{q-p}{2}+\frac{1}{n+3}\\ =\frac{\left(n+3\right)}{2^n}Kf\left(Q_{n,k}\right)+\frac{1}{n+3}+\left(n-1\right)2^{n-2}\end{array}$

化简上述等式可得

$Kf\left(s\left(Q_{n,k}\right)\right)=\frac{{\left(n+3\right)}^2}{2}Kf\left(Q_{n,k}\right)+\left(n-1\right)\left(n+3\right)2^{2n-3}+2^{n-1}$

将引理2.4的结果代入上式可得，增强超立方体 $Q_{n,k}$ 的剖分图 $s\left(Q_{n,k}\right)$ 的基尔霍夫指标如下：

若n和k有相同的奇偶性，则

$Kf\left(s\left(Q_{n,k}\right)\right)={\left(n+3\right)}^2{2}^{n-2}\left(\underset{t=0}{\overset{n}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{1}{t+1}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)\right)+\left(n-1\right)\left(n+3\right)2^{2n-3}+2^{n-1}$。

若n和k有不同的奇偶性，则

$Kf\left(s\left(Q_{n,k}\right)\right)={\left(n+3\right)}^2{2}^{n-2}\left(\underset{t=0}{\overset{n-1}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{1}{t+1}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)\right)+\left(n-1\right)\left(n+3\right)2^{2n-3}+2^{n-1}$。

证毕。

定理3.2：设 $1\le k\le n-1$，$t\left(Q_{n,k}\right)$ 为增强超立方体 $Q_{n,k}$ 的全图，则我们可得

1) 若n和k有相同的奇偶性，则

$\begin{array}{c}Kf\left(t\left(Q_{n,k}\right)\right)=2^{n-1}+\frac{\left(n-1\right)\left(n+3\right)}{n+2}{2}^{2n-3}+\frac{\left(n+3\right)\left(3n+13\right)}{n+4}{2}^{n-2}\\ \times \left(\underset{t=0}{\overset{n}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{3t+n+7}{\left(t+1\right)\left(2t+n+6\right)}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)\right)\end{array}$

2) 若n和k有不同的奇偶性，则

$\begin{array}{c}Kf\left(t\left(Q_{n,k}\right)\right)=2^{n-1}+\frac{\left(n-1\right)\left(n+3\right)}{n+2}{2}^{2n-3}+\frac{\left(n+3\right)\left(3n+13\right)}{n+4}{2}^{n-2}\\ \times \left(\underset{t=0}{\overset{n-1}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{3t+n+7}{\left(t+1\right)\left(2t+n+6\right)}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)\right)\end{array}$

证明：我们都知道增强超立方体 $Q_{n,k}$ 是 $\left(n+1\right)$ 正则的。则由引理2.2 (3)可得 $P_{L\left(t\left(Q_{n,k}\right)\right)}\left(x\right)=x\left(x-n-3\right){\left(x-2n-4\right)}^{q-p}\underset{i=1}{\overset{2^n-1}{{\displaystyle \prod }}}\left[x^2-\left(n+3+2{\mu }_i\right)x+{\mu }_i^2+\left(n+4\right){\mu }_i\right]$，

其中 ${\mu }_i$ 是 $Q_{n,k}$ 的非零拉普拉斯特征值。设b，c分别是 $P_{L\left(t\left(Q_{n,k}\right)\right)}$ 中 $x^2$ 和x的系数，则

$\begin{array}{c}{\left(-1\right)}^{q-p}b={\left(2n+4\right)}^{q-p}\underset{i=1}{\overset{2^n-1}{{\displaystyle \prod }}}\left[{\mu }_i^2+\left(n+4\right){\mu }_i\right]+\left(n+3\right)\left(q-p\right){\left(2n+4\right)}^{q-p-1}\underset{i=1}{\overset{2^n-1}{{\displaystyle \prod }}}\left[{\mu }_i^2+\left(n+4\right){\mu }_i\right]\\ +\left(n+3\right){\left(2n+4\right)}^{q-p}\underset{j=1}{\overset{2^n-1}{{\displaystyle \sum }}}\left[\left(2+2{\mu }_j+d\right)\underset{i=1,i\ne j}{\overset{2^n-1}{{\displaystyle \prod }}}\left({\mu }_i^2+\left(n+4\right){\mu }_i\right)\right]\end{array}$。

且 $c={\left(-1\right)}^{q-p-1}\left(n+3\right){\left(2n+4\right)}^{q-p}\underset{i=1}{\overset{2^n-1}{{\displaystyle \prod }}}\left[{\mu }_i^2+\left(n+4\right){\mu }_i\right]$。

注意到 $t\left(Q_{n,k}\right)$ 有 $q+p=\left(n+3\right)2^{n-1}$ 个顶点，由引理2.3可得

$\begin{array}{c}\frac{Kf\left(t\left(Q_{n,k}\right)\right)}{q+p}=-\frac{b}{c}=\frac{1}{n+3}+\frac{q-p}{2\left(n+2\right)}+\underset{i=1}{\overset{2^n-1}{{\displaystyle \sum }}}\frac{2{\mu }_i+n+3}{{\mu }_i\left({\mu }_i+n+4\right)}\\ =\frac{1}{n+3}+\frac{q-p}{2\left(n+2\right)}+\underset{i=1}{\overset{2^n-1}{{\displaystyle \sum }}}\left(\frac{n+3}{n+4}\times \frac{1}{{\mu }_i}+\frac{n+5}{n+4}\times \frac{1}{{\mu }_i+n+4}\right)\\ =\frac{1}{n+3}+\frac{q-p}{2\left(n+2\right)}+\frac{n+3}{\left(n+4\right)2^n}Kf\left(Q_{n,k}\right)+\frac{n+5}{n+4}\underset{i=1}{\overset{2^n-1}{{\displaystyle \sum }}}\frac{1}{{\mu }_i+n+4}\end{array}$

将 $p=2^n$，$q=\left(n+1\right)2^{n-1}$ 代入上式并化简上式，可得

$Kf\left(t\left(Q_{n,k}\right)\right)=2^{n-1}+\frac{\left(n-1\right)\left(n+3\right)}{n+2}{2}^{2n-3}+\frac{{\left(n+3\right)}^2}{2\left(n+4\right)}Kf\left(Q_{n,k}\right)+\frac{\left(n+3\right)\left(n+5\right)}{n+4}{2}^{n-1}\underset{i=1}{\overset{2^n-1}{{\displaystyle \sum }}}\frac{1}{{\mu }_i+n+4}$

再将引理2.4和引理2.5的结果代入上式，由此可得增强超立方体全图的基尔霍夫指标如下：

若n和k有相同的奇偶性，则

$\begin{array}{l}Kf\left(t\left(Q_{n,k}\right)\right)=2^{n-1}+\frac{\left(n-1\right)\left(n+3\right)}{n+2}{2}^{2n-3}+\frac{{\left(n+3\right)}^2}{n+4}{2}^{n-2}\left(\underset{t=0}{\overset{n}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{1}{t+1}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)\right)\\ +\frac{\left(n+3\right)\left(n+5\right)}{n+4}{2}^{n-1}\left(\underset{t=1}{\overset{n-1}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{1}{2t+n+6}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)+\frac{k-1}{n+6}+\frac{1}{3\left(n+2\right)}\right)\\ =2^{n-1}+\frac{\left(n-1\right)\left(n+3\right)}{n+2}{2}^{2n-3}+\frac{{\left(n+3\right)}^2}{n+4}{2}^{n-2}\left(\underset{t=0}{\overset{n}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{1}{t+1}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)\right)\\ +\frac{\left(n+3\right)\left(n+5\right)}{n+4}{2}^{n-1}\left(\underset{t=0}{\overset{n}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{1}{2t+n+6}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)\right)\\ =2^{n-1}+\frac{\left(n-1\right)\left(n+3\right)}{n+2}{2}^{2n-3}+\frac{\left(n+3\right)\left(3n+13\right)}{n+4}{2}^{n-2}\left(\underset{t=0}{\overset{n}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{3t+n+7}{\left(t+1\right)\left(2t+n+6\right)}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)\right)\end{array}$

若n和k有不同的奇偶性，则

$\begin{array}{l}Kf\left(t\left(Q_{n,k}\right)\right)=2^{n-1}+\frac{\left(n-1\right)\left(n+3\right)}{n+2}{2}^{2n-3}+\frac{{\left(n+3\right)}^2}{n+4}{2}^{n-2}\left(\underset{t=0}{\overset{n-1}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{1}{t+1}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)\right)\\ +\frac{\left(n+3\right)\left(n+5\right)}{n+4}{2}^{n-1}\left(\underset{t=1}{\overset{n-1}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{1}{2t+n+6}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)+\frac{k-1}{n+6}\right)\\ =2^{n-1}+\frac{\left(n-1\right)\left(n+3\right)}{n+2}{2}^{2n-3}+\frac{{\left(n+3\right)}^2}{n+4}{2}^{n-2}\left(\underset{t=0}{\overset{n-1}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{1}{t+1}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)\right)\\ +\frac{\left(n+3\right)\left(n+5\right)}{n+4}{2}^{n-1}\left(\underset{t=0}{\overset{n-1}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{1}{2t+n+6}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)\right)\\ =2^{n-1}+\frac{\left(n-1\right)\left(n+3\right)}{n+2}{2}^{2n-3}+\frac{\left(n+3\right)\left(3n+13\right)}{n+4}{2}^{n-2}\left(\underset{t=0}{\overset{n-1}{{\displaystyle \sum }}}\underset{j=0}{\overset{n}{{\displaystyle \sum }}}\frac{3t+n+7}{\left(t+1\right)\left(2t+n+6\right)}\left(\begin{array}{c}n-k+2\\ 2j\end{array}\right)\left(\begin{array}{c}k-1\\ t+1-2j\end{array}\right)\right)\end{array}$

证毕。

文章引用

许 萍. 增强超立方体剖分图和全图的基尔霍夫指标
Kirchhoff Index in Subdivision and Total Graphs of Enhanced Hypercube[J]. 应用数学进展, 2019, 08(04): 691-696. https://doi.org/10.12677/AAM.2019.84078

参考文献