«上一篇
文章快速检索     高级检索
下一篇»
  哈尔滨工程大学学报  2020, Vol. 41 Issue (9): 1366-1370  DOI: 10.11990/jheu.201906057
0

引用本文  

卢鹏丽, 刘文智. Indu-Bala乘积图的广义距离谱[J]. 哈尔滨工程大学学报, 2020, 41(9): 1366-1370. DOI: 10.11990/jheu.201906057.
LU Pengli, LIU Wenzhi. Generalized distance spectrum of Indu-Bala product of graphs[J]. Journal of Harbin Engineering University, 2020, 41(9): 1366-1370. DOI: 10.11990/jheu.201906057.

基金项目

国家自然科学基金项目(11361033)

通信作者

卢鹏丽, E-mail:lupengli88@163.com

作者简介

卢鹏丽, 女, 教授, 博士生导师

文章历史

收稿日期:2019-06-17
网络出版日期:2020-07-14
Indu-Bala乘积图的广义距离谱
卢鹏丽 , 刘文智     
兰州理工大学 计算机与通信学院, 甘肃 兰州 730050
摘要:为了完善组合图的距离谱理论,减少图谱的计算复杂度,本文依据矩阵论和图论相关知识,计算了Indu-Bala乘积图G1G2的广义距离谱,进而得到其距离拉普拉斯谱和距离无符号拉普拉斯谱;由所得谱证明了一类距离(无符号)拉普拉斯整谱图KnKn+1;作为应用,得到了一类特殊图KnKn+1的距离(无符号)拉普拉斯谱能量。
关键词图论    距离(无符号)拉普拉斯矩阵    广义距离矩阵    组合图    广义距离谱    距离(无符号)拉普拉斯谱    整谱图    谱能量    
Generalized distance spectrum of Indu-Bala product of graphs
LU Pengli , LIU Wenzhi     
School of Computer and Communication, Lanzhou University of Technology, Lanzhou 730050, China
Abstract: This study aims to improve the distance spectrum theory of composite graphs and reduce the computational complexity of spectral graph. The generalized distance spectrum of Indu-Bala product of graphs G1G2 is calculated using related knowledge of matrix theory and graph theory, and then the distance Laplacian spectrum and the distance (signless) Laplacian integral spectrum are obtained. Furthermore, a type of distance (signless) Laplacian integral spectrum graph KnKn+1 is proved based on the spectra obtained. As an application, the distance (signless) Laplacian spectrum energy of a special graph KnKn+1 is obtained on the basis of previous results.
Keywords: graph theory    distance (signless) Laplacian matrix    generalized distance matrix    composite graphs    generalized distance spectrum    distance (signless) Laplacian spectrum    integral spectrum graph    spectrum energy    

距离谱理论[1]作为图论的一个重要研究方向,主要是通过图的各类矩阵(距离矩阵、距离拉普拉斯矩阵等)、特征根及其特征向量来研究图的拓扑结构和代数性质,广泛应用于计算机、复杂系统、化学、物理等学科中。关于距离谱和距离(无符号)拉普拉斯谱的研究现状如下:学者们已经计算得到了圈图[2]、路图[3]和完全二部图[4]等简单图的距离谱;Stevanovic和Indulal[5-6]得到了正则图的联图的距离谱,距离正则图和完全图的簇图的距离谱;Barik和Sahoo[7]得到了距离正则图和正则图的冠图的距离谱和距离(无符号)拉普拉斯谱;其他研究成果见文献[8-11]。在此基础上,本文计算了一类组合图的广义距离谱。通过简单地参数赋值,就可以得到距离(无符号)拉普拉斯谱,大大减少了距离矩阵相关谱的计算量。

1 基本概念和引理

本文只讨论简单连通图。图G=(V(G), E(G)),其中顶点集和边集分别为V(G)={v1, v2, …, vn},E(G)={e1, e2, …, em}。图G中任意2个顶点uv之间的距离记为dG(u, v),它表示顶点u和顶点v之间最短路径的长度。顶点u的传递Tr(u)定义为顶点uG中其他顶点距离的和,记为Tr(u)=$\sum\limits_{v \in V(G)} {{d_G}} (u, v)$,平均传递t(G)=$\frac{1}{n}\sum\limits_{i = 1}^n {{\mathop{\rm Tr}\nolimits} } \left( {{v_i}} \right)$。图G的距离矩阵记为D(G)=(duv)n×n,是一个n×n维矩阵,其中duv=dG(u, v),矩阵D(G)的特征值记为λ1D(G)≥λ2D(G)≥…≥λnD(G),距离矩阵D(G)的特征值及其对应重数所构成的集合为图G的距离谱,记为D-谱。图G的距离谱能量[14]定义为:

$ \mathit{\boldsymbol{D}}E(G) = \sum\limits_{i = 1}^n | \lambda _i^D(G)| $

2013年,Aouchiche和Hansen[1]受拉普拉斯矩阵和无符号拉普拉斯矩阵的启发,提出了图的距离拉普拉斯矩阵和距离无符号拉普拉斯矩阵的概念,并研究它们的谱。图G的传递矩阵记为Tr(G),是对角线元素为Tr(vi)的n×n维对角矩阵。图G的距离拉普拉斯矩阵和距离无符号拉普拉斯矩阵分别记为L(G)=Tr(G)-D(G)和Q(G)=Tr(G)+D(G),相应的特征值分别为λ1L(G)≥λ2L(G)≥…≥λnL(G)=0,λ1Q(G)≥λ2Q(G)≥…≥λnQ(G),相应的特征值及其重数所构成的集合称为图G的距离拉普拉斯谱和距离无符号拉普拉斯谱,记为L-谱和Q-谱。

2019年,Guixian Tian[16]等研究了距离矩阵和传递矩阵的线性组合,提出了广义距离矩阵,记作Dα(G)=αTr(G)+(1-α)D(G),0≤α≤1。由此可以通过一个参数α将3个矩阵联系在一起,D0(G)=D(G),${\mathit{\boldsymbol{D}}_{\frac{1}{2}}}(G) = \frac{1}{2}\mathit{\boldsymbol{Q}}(G)$D1(G)=Tr(G),Dα(G)-Dβ(G)=(α-β)L(G)。广义距离矩阵的特征值记作λ1(Dα)≥λ2(Dα)≥…≥λn(Dα),特征值及其重数的集合称作广义距离谱。

受到Ligong Wang[12]和G. Indulal[13]论文的启发。文献[12]中,图Kn, n+1Kn+1, n是将Kn, n+1复制2次,然后将2个复制图中的n+1个对应顶点相连接,其中Kn, n+1是完全二部图,作者证明了Kn, n+1Kn+1, n是邻接整谱图。文献[13]中,作者将图Kn, n+1Kn+1, n一般化到图G1G2,是将G1G2的联图复制2次,然后将2个复制图中G2的对应顶点相连接所得到的图,计算了其距离谱。明显地,图Kn, n+1Kn+1, n是图G1G2的一种特殊图$\overline {{K_n}} \nabla \overline {{K_{n + 1}}} $,在此基础上计算了G1G2的广义距离谱,进而求得距离(无符号)拉普拉斯谱。

引理1[15]  设图G的距离拉普拉斯谱为{λL1(G)≥λL2(G)≥…≥λnL(G)=0},平均传递为t(G),则图G的距离拉普拉斯谱能量定义为:

$ {\rm{DLE}} (G) = \sum\limits_{i = 1}^n | {\lambda _i}^L(G) - t(G)| $

引理2[15]  设图G的距离无符号拉普拉斯谱为{λQ1(G)≥λQ2(G)≥…≥λnQ(G)},平均传递为t(G),则图G的距离无符号拉普拉斯谱能量定义为:

$ {\rm{DSLE}} (G) = \sum\limits_{i = 1}^n | {\lambda _i}^Q(G) - t(G)| $
2 图G1G2的广义距离谱

定理1   设图Gi是有ni个顶点的ri-正则图,其邻接矩阵Ai对应的邻接谱为{ri, λi2, λi3, …, λini},i=1, 2。那么图G1G2的广义距离谱为:

1)(5n1+3n2-r1+λ1j)α-λ1j-2,j=2, 3, …, n1, 每一个重数为2;

2)(3n1+5n2-2r2+2λ2j)α-2λ2j-4,j=2, 3, …, n2

3)(3n1+5n2-2r2-4)α,重数为n2-1;

4) 方程组的解

$ \left\{ {\begin{array}{*{20}{l}} {{B^*}\beta + (1 - \alpha ){n_2}\gamma + 2(1 - \alpha ){n_2}\delta + }\\ {3(1 - \alpha ){n_1}\varepsilon = \sigma \beta }\\ {(1 - \alpha ){n_1}\beta + {C^*}\gamma + (1 - \alpha )(3{n_2} - {r_2} - 2)\delta }\\ {2(1 - \alpha ){n_1}\varepsilon = \sigma \gamma }\\ {2(1 - \alpha ){n_1}\beta + (1 - \alpha )(3{n_2} - {r_2} - 2)\gamma + }\\ {{C^*}\delta + (1 - \alpha ){n_1}\varepsilon = \sigma \delta }\\ {3(1 - \alpha ){n_1}\beta + 2(1 - \alpha ){n_2}\gamma + (1 - \alpha ){n_2}\delta + }\\ {{B^*}\varepsilon = \sigma \varepsilon } \end{array}} \right. $

其中,B*=(3n1+3n2)α+2n1-r1-2,C*=(3n1+3n2-r2-2)α+2n2-r2-2。

证明:对图G1G2的顶点进行适当编号,图G1G2的距离矩阵可以表示为:

$ \mathit{\boldsymbol{D}}({G_1}\nabla {G_2}) = \left[ {\begin{array}{*{20}{c}} {2(\mathit{\boldsymbol{J}} - \mathit{\boldsymbol{I}}) - {\mathit{\boldsymbol{A}}_1}}&\mathit{\boldsymbol{J}}&{2\mathit{\boldsymbol{J}}}&{3\mathit{\boldsymbol{J}}}\\ \mathit{\boldsymbol{J}}&{2(\mathit{\boldsymbol{J}} - \mathit{\boldsymbol{I}}) - {\mathit{\boldsymbol{A}}_2}}&{3\mathit{\boldsymbol{J}} - 2\mathit{\boldsymbol{I}} - {\mathit{\boldsymbol{A}}_2}}&{2\mathit{\boldsymbol{J}}}\\ {2\mathit{\boldsymbol{J}}}&{3\mathit{\boldsymbol{J}} - 2\mathit{\boldsymbol{I}} - {\mathit{\boldsymbol{A}}_2}}&{2(\mathit{\boldsymbol{J}} - \mathit{\boldsymbol{I}}) - {\mathit{\boldsymbol{A}}_2}}&\mathit{\boldsymbol{J}}\\ {3\mathit{\boldsymbol{J}}}&{2\mathit{\boldsymbol{J}}}&\mathit{\boldsymbol{J}}&{2(\mathit{\boldsymbol{J}} - \mathit{\boldsymbol{I}}) - {\mathit{\boldsymbol{A}}_1}} \end{array}} \right] $

根据距离矩阵,得到图G1G2中每个顶点的传递Tr(u)=5n1+3n2-r1-2,uV(G1);Tr(v)=3n1+5n2-2r2-4,vV(G2)。因此,图G1G2的广义距离矩阵可以表示为:

$ {\mathit{\boldsymbol{D}}_\alpha }({G_1}\nabla {G_2}) = = \left[ {\begin{array}{*{20}{c}} {{N^*}}&{(1 - \alpha )\mathit{\boldsymbol{J}}}&{2(1 - \alpha )\mathit{\boldsymbol{J}}}&{3(1 - \alpha )\mathit{\boldsymbol{J}}}\\ {(1 - \alpha )\mathit{\boldsymbol{J}}}&{{M^*}}&{(1 - \alpha )(3\mathit{\boldsymbol{J}} - 2\mathit{\boldsymbol{I}} - {\mathit{\boldsymbol{A}}_2})}&{2(1 - \alpha )\mathit{\boldsymbol{J}}}\\ {2(1 - \alpha )\mathit{\boldsymbol{J}}}&{(1 - \alpha )(3\mathit{\boldsymbol{J}} - 2\mathit{\boldsymbol{I}} - {\mathit{\boldsymbol{A}}_2})}&{{\mathit{\boldsymbol{M}}^*}}&{(1 - \alpha )\mathit{\boldsymbol{J}}}\\ {3(1 - \alpha )\mathit{\boldsymbol{J}}}&{2(1 - \alpha )\mathit{\boldsymbol{J}}}&{(1 - \alpha )\mathit{\boldsymbol{J}}}&{{N^*}} \end{array}} \right] $

式中:M*=(3n1+5n2-2r2-4)αI+(1-α)(2J-2I-A2); N*=(5n1+3n2-r1-2)αI+(1-α) (2J-2I-A1); J是全1矩阵; I是单位矩阵。

因为Giri-正则图,所以Ai的特征值ri所对应的特征向量是全1向量1,其他特征向量都和1正交。设Ai的特征值λiri所对应的特征向量为Xi,则AiXi=λiXi1TXi=0,i=1, 2。

向量ϕ1=[X1  0  0  0]T是矩阵Dα(G1G2)的特征值(5n1+3n2-r1+λ1j)α-λ1j-2,j=2, 3, …, n1所对应的特征向量。即:

$ \begin{array}{l} {\mathit{\boldsymbol{D}}_\alpha }({G_1}\nabla {G_2}){\phi _1} = \left[ {\begin{array}{*{20}{c}} {{N^*}}&{(1 - \alpha )\mathit{\boldsymbol{J}}}&{2(1 - \alpha )\mathit{\boldsymbol{J}}}&{3(1 - \alpha )\mathit{\boldsymbol{J}}}\\ {(1 - \alpha )\mathit{\boldsymbol{J}}}&{{M^*}}&{(1 - \alpha )(3\mathit{\boldsymbol{J}} - 2\mathit{\boldsymbol{I}} - {\mathit{\boldsymbol{A}}_2})}&{2(1 - \alpha )\mathit{\boldsymbol{J}}}\\ {2(1 - \alpha )\mathit{\boldsymbol{J}}}&{(1 - \alpha )(3\mathit{\boldsymbol{J}} - 2\mathit{\boldsymbol{I}} - {\mathit{\boldsymbol{A}}_2})}&M&{(1 - \alpha )\mathit{\boldsymbol{J}}}\\ {3(1 - \alpha )\mathit{\boldsymbol{J}}}&{2(1 - \alpha )\mathit{\boldsymbol{J}}}&{(1 - \alpha )\mathit{\boldsymbol{J}}}&{{N^*}} \end{array}} \right] \times \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{X}}_1}}\\ {\bf{0}}\\ {\bf{0}}\\ {\bf{0}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {((5{n_1} + 3{n_2} - {r_1} - 2)\alpha \mathit{\boldsymbol{I}} + (1 - \alpha )(2\mathit{\boldsymbol{J}} - 2\mathit{\boldsymbol{I}} - {\mathit{\boldsymbol{A}}_1})){\mathit{\boldsymbol{X}}_1}}\\ {\bf{0}}\\ {\bf{0}}\\ {\bf{0}} \end{array}} \right]{\rm{ = }}\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} (5{n_1} + 3{n_2} - {r_1} + {\lambda _{{1_j}}})\alpha - {\lambda _{{1_j}}} - 2\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{X}}_1}}\\ {\bf{0}}\\ {\bf{0}}\\ {\bf{0}} \end{array}} \right] \end{array} $

同样地,向量ϕ2=[0  0  0  X1]T是矩阵Dα(G1G2)的特征值(5n1+3n2-r1+λ1j)α-λ1j-2,j=2, 3, …, n1所对应的特征向量。

设向量ψ=[0  tX2  X2  0]T是矩阵Dα(G1G2)的特征值μ所对应的特征向量,然后根据Dα(G1G2)ψ=μψ可得:

$ \left\{ {\begin{array}{*{20}{l}} {[(3{n_1} + 5{n_2} - 2{r_2} + {\lambda _2} - 2)\alpha - 2 - {\lambda _2}]t - (1 - \alpha )({\lambda _2} + 2) = \mu t}\\ { - (1 - \alpha )({\lambda _2} + 2)t + (3{n_1} + 5{n_2} - 2{r_2} + {\lambda _2} - 2)\alpha - 2 - {\lambda _2} = \mu } \end{array}} \right. $

求解方程组可得:

μ=(3n1+5n2-2r2+2λ2j)α-2λ2j-4,j=2, 3, …, n2μ=(3n1+5n2-2r2-4)α,重数为n2-1。

已经得到了2(n1-1)+2(n2-1)=2(n1+n2)-4个特征向量,这些特征向量正交于[1  0  0  0]T、[0  1  0  0]T、[0  0  1  0]T和[0  0  0  1]T

因此,剩余4个特征向量有如下形式φ=[β1  γ1  δ1  ε1]T,(β, γ, δ, ε)≠(0, 0, 0, 0)。

σ是矩阵Dα(G1G2)的特征向量φ所对应的特征值,根据Dα(G1G2)φ=σφAi1=ri1i=1, 2可得:

$ \left\{ {\begin{array}{*{20}{l}} {{B^*}\beta + (1 - \alpha ){n_2}\gamma + 2(1 - \alpha ){n_2}\delta + 3(1 - \alpha ){n_1}\varepsilon = \sigma \beta }\\ {(1 - \alpha ){n_1}\beta + {C^*}\gamma + (1 - \alpha )(3{n_2} - {r_2} - 2)\delta + 2(1 - \alpha ){n_1}\varepsilon = \sigma \gamma }\\ {2(1 - \alpha ){n_1}\beta + (1 - \alpha )(3{n_2} - {r_2} - 2)\gamma + {C^*}\delta + (1 - \alpha ){n_1}\varepsilon = \sigma \delta }\\ {3(1 - \alpha ){n_1}\beta + 2(1 - \alpha ){n_2}\gamma + (1 - \alpha ){n_2}\delta + {B^*}\varepsilon = \sigma \varepsilon } \end{array}} \right. $

式中:B*=(3n1+3n2)α+2n1-r1-2,C*=(3n1+3n2-r2-2)α+2n2-r2-2。

假设β=0代入上面方程组,化简得γ=δ=ε=0,矛盾。因此,不失一般性,假设α=1求解上面方程组可得定理中的第(4)部分,证毕。

3 图G1G2的距离拉普拉斯谱

定理2   设图Gi是有ni个顶点的ri-正则图,其邻接矩阵Ai对应的邻接谱为{ri, λi2, λi3, …, λini},i=1, 2。那么图G1G2的距离拉普拉斯谱为:

1) 5n1+3n2-r1+λ1jj=2, 3, …, n1, 每一个重数为2;

2) 3n1+5n2-2r2+2λ2jj=2, 3, …, n2

3) 3n1+5n2-2r2-4,重数为n2-1;

4) $\frac{{9{n_1}}}{2} + \frac{{9{n_2}}}{2} - {r_2} - 2 \pm \frac{{\sqrt {{A^*}} }}{2}$;3(n1+n2);0。

其中A*=9n12-14n1n2+12n1r2+24n1+9n22-12n2r2-24n2+4r22+16r2+16。

证明:已知Dα(G)-Dβ(G)=(α-β)L(G),取α=1,β=0得L(G1G2)=D1(G1G2)-D0(G1G2),则由定理1可得定理2,证毕。

推论1   设图Knn个顶点的完全图的补图,图Kn+1n+1个顶点的完全图的补图,则图KnKn+1是距离拉普拉斯整谱图。

证明:在定理2中,令G1=KnG2=Kn+1。即:n1=n, n2=n+1和r1=r2=0,则KnKn+1的距离拉普拉斯谱为:

$\left[ {\begin{array}{*{20}{c}} {10n + 3}&{8n + 5}&{8n + 3}&{8n + 2}&{8n + 1}&{6n + 3}&0\\ 1&n&{2(n - 1)}&1&n&1&1 \end{array}} \right]$显然,$\overline {{K_n}} \nabla \overline {{K_{n + 1}}} $是距离拉普拉斯整谱图。

推论2   图$\overline {{K_n}} \nabla \overline {{K_{n + 1}}} $的距离拉普拉斯谱能量为DLE(KnKn+1)=32n2-28n+9-$\frac{7}{{2n + 1}}$

证明:已知$\sum\limits_{i = 1}^n {\lambda _i^L} (G) = \sum\limits_{i = 1}^n {Tr} \left( {{v_i}} \right)$=nt(G), 则t(KnKn+1)=$\frac{1}{{4n + 2}}\sum\limits_{i = 1}^n {\lambda _i^L} $(KnKn+1)= 12-$\frac{7}{{4n + 2}}$,当n≥2时,除了特征值0之外,其余特征值λiL(KnKn+1)>t(KnKn+1)。最后由引理1得到推论2,得证。

4 图G1G2的距离无符号拉普拉斯谱

定理3   设图Gi是有ni个顶点的ri-正则图,其邻接矩阵Ai对应的邻接谱为{ri, λi2, λi3, …, λini},i=1, 2。那么图G1G2的距离无符号拉普拉斯谱为:

1) 5n1+3n2-r1-λ1j-4,j=2, 3, …, n1, 每一个重数为2;

2) 3n1+5n2-2r2-2λ2j-8,j=2, 3, …, n2

3) 3n1+5n2-2r2-4,重数为n2-1;

4) $\frac{{7{n_1}}}{2} + \frac{{7{n_2}}}{2}$-r1-r2-4±$\frac{{\sqrt {{A^*}} }}{2}$$\frac{{13{n_1}}}{2} + \frac{{13{n_2}}}{2}$-r1-2r2-6±$\frac{{\sqrt {{A^{**}}} }}{2}$ 2。

其中A*=n12+2n1n2-4n1r1+4n1r2+n22+4n2r1-4n2r2+4r12-8r1r2+4r22; A**=49n12-62n1n2-28n1r1+56n1+49n22+28n2r1-56n2r2-56n2+4r12-16r1r2-16r1+16r22+32r2+16。

证明:已知${\mathit{\boldsymbol{D}}_{\frac{1}{2}}}(G) = \frac{1}{2}\mathit{\boldsymbol{Q}}(G)$,则Q(G1G2)=2${\mathit{\boldsymbol{D}}_{\frac{1}{2}}}$(G1G2),由定理1可得定理3,证毕。

推论3   图Knn个顶点的完全图的补图,图Kn+1是n+1个顶点的完全图的补图,则图KnKn+1是距离无符号拉普拉斯整谱图。

证明:在定理3中,令G1=KnG2=Kn+1。即:n1=n, n2=n+1和r1=r2=0,则KnKn+1的距离无符号拉普拉斯谱为:

$\left[ {\begin{array}{*{20}{c}} {16n + 2}&{10n - 1}&{8n + 1}&{8n}&{8n - 1}&{8n - 3}&{6n - 1}\\ 1&1&n&1&{2(n - 1)}&n&1 \end{array}} \right]$显然,KnKn+1是距离无符号拉普拉斯整谱图。

推论4   图KnKn+1的距离无符号拉普拉斯谱能量为DSLE(KnKn+1)=32n2-44n-1。

证明:已知$\sum\limits_{i = 1}^n {\lambda _i^L} (G) = \sum\limits_{i = 1}^n {{\rm{Tr}}} \left( {{v_i}} \right)$=nt(G), 则t(KnKn+1)=$\frac{1}{{4n + 2}}\sum\limits_{i = 1}^n {\lambda _i^Q} $(KnKn+1)=16-$\frac{{29}}{{4n + 2}}$,当n≥3时,特征值λiL(KnKn+1)>t(KnKn+1)。最后由引理2得到推论4,得证。

5 结论

1) 主要研究了2个正则图经过Indu-Bala乘积这一图操作之后所形成的合成图的广义距离谱,揭示了合成图的广义距离谱、距离(无符号)拉普拉斯谱与原图的邻接谱之间的关系,不仅拓宽了组合图广义距离谱的研究范围,而且大大减少了距离(无符号)拉普拉斯谱的计算量;

2) 得到了一类特殊的距离(无符号)拉普拉斯整谱图;

3) 得到了特殊图的距离(无符号)拉普拉斯谱能量公式。

参考文献
[1]
AOUCHICHE M, HANSEN P. Two Laplacians for the distance matrix of a graph[J]. Linear algebra and its applications, 2013, 439(1): 21-33. (0)
[2]
GRAOVAC A, JASHARI G, STRUNJE M. On the distance spectrum of a cycle[J]. Aplikace matematiky, 1985, 30(4): 286-290. (0)
[3]
RUZIEH S N, POWERS D L. The distance spectrum of the path Pn and the first distance eigenvector of connected graphs[J]. Linear and multilinear algebra, 1990, 28(1/2): 75-81. (0)
[4]
KRIVKA P, TRINAJSTIĆ N. On the distance polynomial of a graph[J]. Aplikace matematiky, 1983, 28(5): 357-363. (0)
[5]
STEVANOVIĆ D, INDULAL G. The distance spectrum and energy of the compositions of regular graphs[J]. Applied mathematics letters, 2009, 22(7): 1136-1140. DOI:10.1016/j.aml.2008.11.007 (0)
[6]
INDULAL G, STEVANOVIĆ D. The distance spectrum of corona and cluster of two graphs[J]. AKCE international journal of graphs and combinatorics, 2015, 12(2/3): 186-192. (0)
[7]
BARIK S, SAHOO G. On the distance spectra of coronas[J]. Linear and multilinear algebra, 2017, 65(8): 1617-1628. DOI:10.1080/03081087.2016.1249448 (0)
[8]
GOPALAPILLAI I. Distance spectrum of graph compositions[J]. ARS mathematica contemporanea, 2009, 2(1): 93-100. DOI:10.26493/1855-3974.103.e09 (0)
[9]
ALHEVAZ A, BAGHIPUR M, HASHEMI E, et al. On the distance Signless Laplacian spectrum of graphs[J]. Bulletin of the Malaysian mathematical sciences society, 2019, 42(5): 2603-2621. DOI:10.1007/s40840-018-0619-8 (0)
[10]
SCARIA D C, INDULAL G. The distance Laplacian and distance signless Laplacian spectrum of the subdivision-vertex join and subdivision-edge join of two regular graphs[J]. Discrete mathematics, algorithms and applications, 2019, 11(5): 1950053. DOI:10.1142/S1793830919500538 (0)
[11]
AOUCHICHE M, HANSEN P. On the distance signless Laplacian of a graph[J]. Linear and multilinear algebra, 2016, 64(6): 1113-1123. DOI:10.1080/03081087.2015.1073215 (0)
[12]
WANG Ligong. Integral graphs and integral trees[D]. Enshart: University of Twente, 2005. (0)
[13]
INDULAL G, BALAKRISHNAN R. Distance spectrum of Indu Bala product of graphs[J]. AKCE International journal of graphs and combinatorics, 2016, 13(3): 230-234. DOI:10.1016/j.akcej.2016.06.012 (0)
[14]
INDULAL G, GUTMAN I, VIJAYAKUMAR A. On distance energy of graphs[J]. MATCH communications in mathematical and in computer chemistry, 2008, 60(2): 461-472. (0)
[15]
YANG Jieshan, YOU Lihua, GUTMAN I. Bounds on the distance Laplacian energy of graphs[J]. Kragujevac journal of mathematics, 2013, 37(2): 245-255. (0)
[16]
CUI Shuyu, HE Jingxiang, TIAN Guixian. The generalized distance matrix[J]. Linear algebra and its applications, 2019, 563: 1-23. DOI:10.1016/j.laa.2018.10.014 (0)