新疆师范大学数学科学学院，新疆 乌鲁木齐

收稿日期：2021年11月23日；录用日期：2021年12月21日；发布日期：2021年12月28日

摘要

超立方体Q_n及其变体作为许多大型处理机系统的一种常用网络拓扑结构，是迄今为止最为重要和最具吸引力的网络拓扑结构之一。一个简单图G的线图line(G)是以图G的边集作为其顶点集，两个顶点之间有一条边当且仅当这两个点对应的边在原图G中是相邻的。1993年张福基等人利用超立方体的邻接多项式给出了超立方体的线图的邻接多项式的具体表达式。时隔近30年，随着图论的发展和兴起衍生出很多新的工具，本文从图的无符号拉普拉斯矩阵与其线图的邻接矩阵关系的角度出发，进一步研究超立方体的线图的一些性质，如：更为简化的超立方体线图的邻接多项式、邻接谱、生成树的个数以及超立方体线图的二部图的判定等。

关键词

超立方体，线图，特征多项式，二部图，谱半径

Research on the Properties of Spectrum on the Line Graph of Hypercube

Shengzhe Hou^*, Hong Bian^#

School of Mathematical Sciences, Xinjiang Normal University, Urumqi Xinjiang

Received: Nov. 23^rd, 2021; accepted: Dec. 21^st, 2021; published: Dec. 28^th, 2021

ABSTRACT

The hypercube Q_n coupled with their variants is used to construct various common network topology models for many large processor systems, hypercube network is one of the most essential and inviting network topological structures today. The line graph line(G) of simple graph G is a graph with vertex set E(G) and there is an edge between two vertices if and only if the edges corresponding to these two points are adjacent in graph G. In 1993 Zhang Fuji et al. gave the specific adjacent polynomial of the line graph of the hypercube. After nearly 30 years, with the development of graph theory, a series of new tools are derived. In this paper, starting from the perspective of the relation of the unsigned Laplacian matrix of the graph and its adjacency matrix of the line graph, we further study some properties of the line graph of the hypercube, such as the more simplified adjacency polynomial, the number of span ning trees, and the determination of the bipartite graph of the line graph of hypercube.

Keywords:Hypercube, Line Graph, Characteristic Polynomial, Bipartite Graph, Spectral Radius

Copyright © 2021 by author(s) and Hans Publishers Inc.

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

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

1. 序言

1993年11月张福基和林国宁在《超立方体的线图》 [1] 一文中探讨了超立方体线图的邻接多项式，利用超立方体的邻接特征多项式，分奇数和偶数两种情形，给出了超立方体线图的邻接多项式的表达式为：

$A\left(line\left(Q_n\right),x\right)=\{\begin{array}{l}{\left(x+2\right)}^{2^{i-1}\left(i-2\right)}{\displaystyle \underset{j=0}{\overset{\frac{i-1}{2}}{\prod }}{\left({\left(x+2-i\right)}^2-{\left(i-2j\right)}^2\right)}^{C_i^j}},当i为奇数;\\ {\left(x+2\right)}^{2^{i-1}\left(i-2\right)}{\left(x+2-i\right)}^{C_i^{\frac{i}{2}}}{\displaystyle \underset{j=0}{\overset{\frac{i-2}{2}}{\prod }}{\left({\left(x+2-i\right)}^2-{\left(i-2j\right)}^2\right)}^{C_i^j}},当i为偶数.\end{array}$

本文将采用新的工具导出新的表达式。

对于超立方体线图的研究，国内外文献还比较少，其中比较突出的有Mirafzal [2] 证明了如果 $k\ge 3$ 和 $n\ne 2k+1$，则除 $k=3,n=9$ 和 $k=3,n=33$ 的情况外， $Q_n\left(k,k+1\right)$ 的线图是顶点传递的非Cayley图，其中 $Q_n\left(k,k+1\right)$ 表示 $Q_n$ 由层 $L_k$ 和 $L_{k+1}$ 诱导的子图。孟吉翔等人 [3]，对超立方体的线图的限制性点连通度进行了研究，得到 ${\kappa }^1\left(line\left(Q_k\right)\right)=3n-4$，${\kappa }^2\left(line\left(Q_k\right)\right)=3n-4$，其中 ${\kappa }^1\left(G\right),{\kappa }^2\left(G\right)$ 表示图G的 ${\kappa }^1,{\kappa }^2$ 限制性点连通度。

Cheng等 [4] 给出了超立方体的线图中包含 $2n-2$ 个节点的独立生成数的 $O\left(N\right)$ 时间算法，其中 $N=n\times 2^{n-1}$, 同时证明了 $line\left(Q_n\right)$ 可以划分成 $2^{n-1}$ 个完全子图。本文力图从拉普拉斯谱出发，探讨更为简化的超立方体线图的邻接多项式、邻接谱，从而推导出更为方便的生成树的个数表达形式以及更简单的超立方体线图的二部图的判定求证方法。

2. 定义与符号

n维超立方体 $Q_n$ 通常有两种不同的定义方式，一种是利用图的笛卡尔积运算给出的递归定义：

定义1 [2]：n维超立方体 $Q_n\left(n\ge 1\right)$ 的递归定义。

$\{\begin{array}{l}{Q}_1=K_2,\hfill \\ Q_n=Q_{n-1}\times K_2,n>1.\hfill \end{array}$

另外一种是利用二进制序列给出的定义 [2]：n维超立方体 $Q_n\left(n\ge 1\right)$ 是 $2^n$ 阶的简单无向图，其中：

$V\left(Q_n\right)=\left\{x_1{x}_2\cdots x_n|x_i\in \left\{0,1\right\},i=1,2,\cdots ,n\right\}$

任意 $x,y\in V\left(Q_n\right)$ 且 $x=x_1{x}_2\cdots x_n$ 与 $y=y_1{y}_2\cdots y_n$，x与y相邻当且仅当n位二进制序列 $x_1{x}_2\cdots x_n$ 与 $y_1{y}_2\cdots y_n$ 恰恰差一位，即 ${\displaystyle \underset{i=1}{\overset{n}{\sum }}\left|x_i-y_i\right|}=1$。

令 $G=\left(V,E\right)$ 是一个简单图，图G的邻接矩阵用 $A\left(G\right)$ 表示；图G的拉普拉斯矩阵定义为： $L\left(G\right)=D\left(G\right)-A\left(G\right)$，其中 $D\left(G\right)$ 为图G的度对角矩阵，即对角线上的元素为图中点对应的度；无符号拉普拉斯矩阵定义为： $Q\left(G\right)=D\left(G\right)+A\left(G\right)$ ；图G邻接矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵对应的特征多项式为 $A\left(G,x\right)$ 、 $L\left(G,x\right)$ 、 $Q\left(G,x\right)$。矩阵X的特征值是指其特征多项式的根, 矩阵X的谱(简称X-谱)是指它的所有特征值连同其重数构成的重集，记为：

$SpecX=\left[\begin{array}{cccc}{\rho }_1& {\rho }_2& \cdots & {\rho }_s\\ x\left({\rho }_1\right)& x\left({\rho }_2\right)& \cdots & x\left({\rho }_s\right)\end{array}\right]$

其中 $x\left({\rho }_i\right)$ 表示特征值 ${\rho }_i$ 的重数， $i\in N^{*}$，共n个不同的根， $n\in N^{*}$，邻接矩阵谱的特征值用 ${\lambda }_i$ 表示，无符号拉普拉斯矩阵的谱的特征值用 $q_i$ 表示，谱半径是指其特征值绝对值集合的上确界。图的邻接矩阵的特征值、谱、特征多项式简称图的特征值、谱、多项式。图G的线图 $line\left(G\right)$ 的顶点集为图G的边集，两个顶点在线图中相邻当且仅当其对应的两条边在图G中是相邻的。用 $C_n^r$ 表示从n个不同的数中任取r个数的组合数； $C_n$ 代表n长圈。特别地，本文为简单起见直接用V代表图的顶点的个数，E代表图的边的个数。

3. 超立方体的线图的性质

根据n维超立方体 $Q_n$ 的结构，文献 [5] 得出其邻接矩阵具有如下明确的递推关系：

引理1 [5]：一般地，n维超立方体 $Q_n\left(n\ge 1\right)$ 的邻接矩阵为 $A\left(Q_n\right)=\left(\begin{array}{cc}A\left(Q_{n-1}\right)& I\\ I& A\left(Q_{n-1}\right)\end{array}\right)$，这里I为 $2^{n-1}$ 阶单位矩阵。

引理2 [6]：二部图的无符号拉普拉斯矩阵的特征多项式等于其拉普拉斯矩阵的特征多项式，即 $L_{二部图}\left(x\right)=Q_{二部图}\left(x\right)$。

引理3 [7]：n维超立方体 $Q_n\left(n\ge 1\right)$ 是二部图。

由引理2和引理3可知，n维超立方体的拉普拉斯矩阵的特征多项式和无符号拉普拉斯矩阵的特征多项式相同，故有如下结论：

定理1：设n维超立方体 $Q_n\left(n\ge 1\right)$ 的拉普拉斯矩阵为 $L\left(Q_n\right)$，无符号拉普拉斯矩阵为 $Q\left(Q_n\right)$，则 $L\left(Q_n\right)=Q\left(Q_n\right)$，即 $L\left(Q_n\right)$ 与 $Q\left(Q_n\right)$ 有相同的谱。

殷剑宏等人利用超立方体的邻接矩阵的递推关系给出了如下超立方体的拉普拉斯谱：

引理4 [8]：设n维超立方体 $Q_n\left(n\ge 1\right)$ 的拉普拉斯矩阵为 $L\left(Q_n\right)=D\left(Q_n\right)-A\left(Q_n\right)$，则 $Q_n$ 的拉普拉斯谱为 $SpecL\left(Q_n\right)=\left(\begin{array}{ccccc}0& 2& 4& \cdots & 2n\\ C_n^0& C_n^1& C_n^2& \cdots & C_n^n\end{array}\right)$，其中 $2t$ ( $t=0,1,2,\cdots ,n$ )为 $L\left(Q_n\right)$ 的 $n+1$ 个不同的特征根，且其重数为二项式系数 $C_n^t$。

由超立方体的定义易知，超立方体的顶点数和边数分别为： $\left|V\left(Q_n\right)\right|=2^n$，$\left|E\left(Q_n\right)\right|=2^{n-1}\times n$。而超立方体是一个正则度为 $k=n$ 的正则图，其边数也可以表示为 $E\left(Q_n\right)=\frac{k\times 2^n}{2}$，其中k是超立方体的正则度。由线图的定义可知，超立方体的线图也是正则度为 $k_l=2\left(n-1\right)$ 的正则图，且超立方体的线图的点数和边数分别为 $V\left(line\left(Q_k\right)\right)=2^{n-1}\times n$，$E\left(line\left(Q_k\right)\right)=\left(n-1\right)\left(2^{n-1}\times n\right)$。

令M是图G的关联矩阵，则 $Q=M{M}^{\text{T}}$ [7]，且 $A\left(line\left(G\right)\right)+2I=M^{\text{T}}M$ [6]。而 $M{M}^{\text{T}}$ 和 $M^{\text{T}}M$ 有相同的非零特征值，所以直接可以得到如下结论：

引理5 [8]： $X\left(G,x\right)$ 表示关于连通图G的X矩阵的特征多项式，变量为x， $E\ge V$，则：

$A\left(line\left(G\right),x\right)={\left(x+2\right)}^{E-V}Q\left(G,x+2\right)$.

定理2： $SpecA\left(line\left(Q_n\right)\right)=\left(\begin{array}{cccccc}-2& 0& 2& \cdots & 2n-2& -2\\ C_n^0& C_n^1& C_n^2& \cdots & C_n^n& E-V\end{array}\right)$，其中 $V=\left|V\left(Q_n\right)\right|=2^n$，$E=\left|E\left(Q_n\right)\right|=2^{n-1}\times n$。

证明：由引理5可知 $A\left(line\left(G\right),x\right)={\left(x+2\right)}^{E-V}Q\left(G,x+2\right)$，若G的Q-特征值为： $q_1\ge q_2\ge \cdots \ge q_n$，则 $q_1-2,q_2-2,\cdots ,q_n-2$，$E-V$ 个 $\left(-2\right)$ 是图G的线图 $line\left(G\right)$ 的邻接特征值。由定理1可知， $SpecQ\left(Q_n\right)=\left(\begin{array}{ccccc}0& 2& 4& \cdots & 2n\\ C_n^0& C_n^1& C_n^2& \cdots & C_n^n\end{array}\right)$，且根据 $V\left(Q_n\right)=2^n$，$E\left(Q_n\right)=2^{n-1}\times n$ 可以得到该结论。

例1：实验验证 $line\left(Q_3\right)$ 的谱符合定理2。

解：如图1所示，可以得出超立方体的线图的邻接矩阵如下：

$\begin{array}{l}{u}_1{u}_2{u}_3{u}_4{u}_5{u}_6{u}_7{u}_8{u}_9{u}_{10}{u}_{11}{u}_{12}\\ A\left(line\left(Q_3\right)\right)=\begin{array}{c}{u}_1\\ u_2\\ u_3\\ u_4\\ u_5\\ u_6\\ u_7\\ u_8\\ u_9\\ u_{10}\\ u_{11}\\ u_{12}\end{array}\left(\begin{array}{cccccccccccc}& 1& 1& & & & 1& 1& & & & \\ 1& & 1& & & & & & 1& 1& & \\ 1& 1& & 1& 1& & & & & & & \\ & & 1& & 1& & & & & 1& 1& \\ & & 1& 1& & 1& 1& & & & & \\ & & & & 1& & 1& & & & 1& 1\\ 1& & & & 1& 1& & 1& & & & \\ 1& & & & & & 1& & 1& & & 1\\ & 1& & & & & & 1& & 1& & 1\\ & 1& & 1& & & & & 1& & 1& \\ & & & 1& & 1& & & & 1& & 1\\ & & & & & 1& & 1& 1& & 1& \end{array}\right)\end{array}$

图1. 实线为 $Q_3$ 的平面图，虚线为 $Q_3$ 的线图 $line(\; Q\; 3\; )$

经Matlab计算得 $SpecA\left(line\left(Q_3\right)\right)\text{=}\left(\begin{array}{cccc}-2& 0& 2& 4\\ 5& 3& 3& 1\end{array}\right)$。而根据定理2的结论可得：

$SpecA\left(line\left(Q_3\right)\right)=\left(\begin{array}{ccccc}-2& 0& 2& 4& -2\\ C_3^0& C_3^1& C_3^2& C_3^3& 12-8\end{array}\right)=\left(\begin{array}{ccccc}-2& 0& 2& 4& -2\\ 1& 3& 3& 1& 4\end{array}\right)=\left(\begin{array}{cccc}-2& 0& 2& 4\\ 5& 3& 3& 1\end{array}\right)$

定理3：超立方体线图 $line\left(Q_n\right)$ 的邻接矩阵的特征多项式为：

$A\left(line\left(Q_n\right),x\right)={\left[x-\left(-2\right)\right]}^{C_n^0}{\left[x\right]}^{C_n^1}{\left[x-2\right]}^{C_n^2}\cdots {\left[x-\left(2n-2\right)\right]}^{C_n^n}{\left[x+2\right]}^{2^{n-1}\left(n-2\right)}$。

证明：根据定理2及矩阵特征多项式的定义可得：

$\begin{array}{c}A\left(line\left(Q_n\right),x\right)={\left[x-\left(-2\right)\right]}^{C_n^0}{\left[x\right]}^{C_n^1}{\left[x-2\right]}^{C_n^2}\cdots {\left[x-\left(2n-2\right)\right]}^{C_n^n}{\left[x+2\right]}^{2^{n-1}\times n-2^n}\\ ={\left[x-\left(-2\right)\right]}^{C_n^0}{\left[x\right]}^{C_n^1}{\left[x-2\right]}^{C_n^2}\cdots {\left[x-\left(2n-2\right)\right]}^{C_n^n}{\left[x+2\right]}^{2^{n-1}\left(n-2\right)}\end{array}$

显然，定理3利用超立方体的线图的谱给出的邻接矩阵的特征多项式的表达式比文献 [1] 给出的超立方体的线图的邻接矩阵的特征多项式的表达式要更为简洁。

袁西英等人根据图G的最大度 $\Delta \left(G\right)$，给出了图G的谱半径的上、下界：

引理6 [9]：对任意一个简单图G，我们有 $\sqrt{\Delta \left(G\right)}\le \rho \left(G\right)\le \Delta \left(G\right)$。

因为在超立方体的线图中， $\Delta \left(line\left(Q_n\right)\right)=k_l=2n-2$，$\rho \left(line\left(G\right)\right)=2n-2$。显然超立方体的线图的谱半径是达到其上界的一类极图。

引理7 [1]：若G为k度正则图，其谱为： $SpecA\left(G\right)=\left(\begin{array}{ccccc}k& {\lambda }_1& {\lambda }_2& \cdots & {\lambda }_{s-1}\\ 1& x_1& x_2& \cdots & x_{s-1}\end{array}\right)$，$s\in N^{*}$。则其生成树的个数为： $t\left(G\right)=\frac{1}{\left|V\left(G\right)\right|}{\displaystyle \underset{i=1}{\overset{s-1}{\prod }}{\left(k-{\lambda }_i\right)}^{x_i}}$。

定理4： $line\left(Q_n\right)$ 是度为 $k_l$ 正则图，其谱为：

$SpecA\left(line\left(Q_n\right)\right)=\left(\begin{array}{ccccccc}{k}_l=2\left(n-1\right)& -2& 0& 2& \cdots & 2n-4& -2\\ 1=C_n^n& C_n^0& C_n^1& C_n^2& \cdots & C_n^{n-1}& E-V\end{array}\right)$，则其生成树的个数为：

$t\left(line\left(Q_n\right)\right)=\frac{1}{2^{n-1}n}{\displaystyle \underset{i=0}{\overset{n-1}{\prod }}{\left(2n-2i\right)}^{C_n^{i-1}}}\times {\left(2n\right)}^{2^{n-1}n-2^n}$。

证明：由引理7可知，

$\begin{array}{c}t\left(line\left(Q_n\right)\right)=\frac{1}{2^{n-1}\times n}{\displaystyle \underset{i=0}{\overset{s-1}{\prod }}{\left[\left[2\left(n-1\right)\right]-{\lambda }_i\right]}^{x_i}}\\ =\frac{1}{2^{n-1}\times n}{\displaystyle \underset{i=0}{\overset{n-1}{\prod }}{\left[\left[2\left(n-1\right)\right]-\left(2i-2\right)\right]}^{C_n^{i-1}}}\times {\left[\left[2\left(n-1\right)\right]-\left(-2\right)\right]}^{E-V}\\ =\frac{1}{2^{n-1}n}{\displaystyle \underset{i=0}{\overset{n-1}{\prod }}{\left(2n-2i\right)}^{C_n^{i-1}}}\times {\left(2n\right)}^{2^{n-1}n-2^n}\end{array}$

例2：验证 $G=line\left(Q_2\right)$ 符合定理4的结论。

$t\left(G\right)=\frac{1}{2^{n-1}n}{\displaystyle \underset{i=0}{\overset{n-1}{\prod }}{\left(2n-2i\right)}^{C_n^{i-1}}}\times {\left(2n\right)}^{2^{n-1}n-2^n}=\frac{1}{2\times 2}\times {\left(2\times 2\right)}^{C_2^1}\times {\left(2\times 2-2\times 2\right)}^{C_2^2}\times {\left(2\times 2\right)}^{2\times 2-2^2}=4$，由生成树的定义，易知 $line\left(G\right)$ 的生成树的个数为4。

引理8 [10]：设简单图G的特征多项式为

$A\left(G,x\right)=x^V+c_1{x}^{V-1}+c_2{x}^{V-2}+\cdots +c_V{x}^{V-V}$。

则(1) $c_1=0$ ；(2) $c_2=-E$ ；(3) $-c_3$ 为G中三角形的个数的两倍，其中V代表图G的顶点数。

显然二部图不含奇圈，而我们知道超立方体是二部图，但是其线图不一定是二部图。由引理8可知，根据超立方体的线图的特征多项式中的系数 $-c_3$ 可以来判断超立方体的线图是否是二部图。如果 $n=1$，$Q_1$ 为一个点，不讨论是否为二部图。如果 $n=2$，$A\left(line\left(Q_2\right),x\right)=\left[x-\left(-2\right)\right]{\left[x\right]}^{C_2^1}=\left(x+2\right)x^2$，其 $-c_3=0$ 无三角形，且根据定义知 $line\left(Q_2\right)=C_4$ 自然为二部图。

定理5：超立方体的线图 $line\left(Q_n\right),n=3,4$ 不是二部图。

证明：由定理3可知 $A\left(line\left(Q_n\right),x\right)={\left[x-\left(-2\right)\right]}^{C_n^0}{\left[x\right]}^{C_n^1}{\left[x-2\right]}^{C_n^2}\cdots {\left[x-\left(2n-2\right)\right]}^{C_n^n}{\left[x+2\right]}^{2^{n-1}\left(n-2\right)}$。

如果 $n=3$ ；

$\begin{array}{c}A\left(line\left(Q_3\right),x\right)=\left[x-\left(-2\right)\right]{\left[x\right]}^{C_3^1}{\left[x-2\right]}^{C_3^2}{\left[x-4\right]}^{C_3^3}{\left[x+2\right]}^{2^2}=\left(x+2\right)x^3{\left(x-2\right)}^3\left(x-4\right){\left(x+2\right)}^4\\ =x^{12}-24x^{10}-16x^9+192x^8+192x^7-640x^6-768x^5+768x^4+1024x^3\end{array}$

只需看 $x^{V-3}=x^{12-3}=x^9$ 的系数， $-c_3=16$，即有8个三角形，如图1中虚线所示，可以看出包含每个顶点 $v_1,v_2,\cdots ,v_8$ 都有1个三角形，共8个三角形，根据二部图无奇圈得知 $Q_3$ 非二部图。

如果 $n=4$ ；

$\begin{array}{c}A\left(line\left(Q_4\right),x\right)={\left[x-\left(-2\right)\right]}^{C_4^0}{\left[x\right]}^{C_4^1}{\left[x-2\right]}^{C_4^2}{\left[x-4\right]}^{C_4^3}{\left[x-6\right]}^{C_4^4}{\left[x+2\right]}^{2^{4-1}\times \left(4-2\right)}\\ =\left(x+2\right)x^4{\left(x-2\right)}^6{\left(x-4\right)}^4\left(x-6\right){\left(x+2\right)}^{16}\\ =x^{32}-96x^{30}-128x^{29}+3936x^{28}+\cdots +\left(-55834574848x^5-12884901888x^4\right)\end{array}$

对于连通图G，只需看 $x^{V-3}=x^{32-3}=x^{29}$ 的系数， $-c_3=128$，即有64个三角形。故其也不是二部图。

定理5的方法，虽然思想简单，但是当n很大，难以判断。对于比较大的n，可以根据下面的二部图的邻接特征值的性质来判断 $line\left(Q_n\right)$ 是否是二部图。

引理9 [8]：1) 一个图G是二部图当且仅当对于G的每个特征值 $\lambda$，则 $-\lambda$ 也是一个特征值且其重数是一样的，即图G的谱是对称的。

2) 一个连通图G是二部图， $\rho$ 为其最大特征值当且仅当 $-\rho$ 也是G一个特征值。

定理6：超立方体的线图 $line\left(Q_n\right)$，$n\ge 3$ 不是二部图。

证明：根据上述引理9(1)可以发现 $line\left(Q_2\right)$ 是二部图，这是因为 $SpecA\left(line\left(Q_2\right)\right)=\left(\begin{array}{ccc}-2& 0& 2\\ 1& 2& 1\end{array}\right)$ 是对称的。但是 $line\left(Q_3\right),line\left(Q_4\right),\cdots$ 以及 $line\left(Q_n\right)$，根据 $specA\left(line\left(Q_n\right)\right)=\left(\begin{array}{cccccc}-2& 0& 2& \cdots & 2n-2& -2\\ C_n^0& C_n^1& C_n^2& \cdots & C_n^n& E-V\end{array}\right)$，它们的谱都不是对称的，故结论成立。

这个问题如果直接用图论的方法判断很难，可见本篇文章所求的超立方体的线图的谱形式的优越性和图谱理论的妙处。

定理7： $\Delta$ 为G的特征值 $\iff$ G为正则图，若 $\Delta$ 为G的特征值，则重数 $x\left(\Delta \right)=1$。

证明：显然G为正则图 $\iff$ $AE=\Delta E$$\iff$$\Delta$ 为G的特征值。

例如 $A\left(Q_2\right)$ 为正则图，有 $\left(\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 0& 1\\ 1& 0& 0& 1\\ 0& 1& 1& 0\end{array}\right)\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)=2\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)$。而从中可以看出其对应的特征向量只可能为 $E_{1\times V}$，$\therefore x\left(\Delta \right)=1$。该定理虽然在文献 [7] 未明确给出，但在其叙述中可以体现此证明思想。通过超立方体的线图也可以验证该结论，因为我们总有 $\Delta =k_l=2n-2$ 对应的重数为 $C_n^n=1$。

基金项目

国家自然科学基金项目(11761070, 61662079)；新疆师范大学2020年数学与应用数学校级一流专业、一流课程专项经费；新疆维吾尔自治区自然科学基金联合项目(2021D01C078)。

文章引用

侯胜哲,边 红. 超立方体线图的谱相关性质的研究
Research on the Properties of Spectrum on the Line Graph of Hypercube[J]. 应用数学进展, 2021, 10(12): 4415-4421. https://doi.org/10.12677/AAM.2021.1012470

参考文献