图谱理论是图论重要的研究领域之一，在计算机科学、通信网络、信息科学、量子化学以及统计力学中均有广泛应用.利用代数的非负矩阵理论, 借助组合数学的一些理论与技巧, 研究图谱与图的结构性质, 与图的有关不变量(譬如色数、度序列、直径、围长、连通度等)之间的关系.在图谱理论中, 为了研究图的性质, 常引入一些矩阵, 如图的邻接矩阵、Laplacian矩阵、距离矩阵等, 这些矩阵与图的结构密切相关.通过矩阵论, 特别是非负矩阵理论、对称矩阵理论以及组合矩阵论中的经典结论, 对图的拓扑结构进行研究; 通过图的邻接矩阵或Laplacian矩阵表示, 建立图的拓扑结构与图的矩阵表示的置换相似不变量之间的联系；同时，将图论中的一些经典结果用于非负矩阵理论和组合矩阵论, 从而推动这些理论的发展.

图的拉普拉斯矩阵及其特征值可用于多个领域的研究, 并且在物理和化学理论中也有其物理解释.早在19世纪中叶, KIRCHHOFF就利用Laplacian矩阵谱研究了电流网络，并给出了著名的矩阵-树定理.近几十年来, 学者们对图的Laplacian谱半径情有独钟, 得到了许多深刻的结果.正如MOHAR^[1]所说，Laplacian特征值比邻接矩阵特征值更能反映图的特质, 而且比图的邻接谱更加自然和重要.对图的邻接矩阵和Laplacian矩阵特征值而言, 最大特征值(也即图的谱半径)是所有特征值中最重要的一个量.

随着科学技术的进步，新的研究方法不断涌现, 借助计算机得到了许多更精确的结果.在网络设计中, 循环图网络结构性能好, 能长时间稳定运行; 实用性强, 且具有可靠性、安全性、拓展性等特点, 因而, 循环图是一类重要的网络拓扑图.借助卡氏积图, 可以将网络做大, 并且能保持原有的一些特征, 这种构造网络的方法行之有效.

在相关文献的基础上, 本文着重研究循环图的卡氏积图的Laplacian半径的上界.

1 图的拉普拉斯谱半径的上界

设G=(V, E)是一个简单图，顶点集为V=(v₁, v₂, …, v_n), 边集为E(G).用G表示G的补图, A(G)表示G的邻接矩阵, d_j表示顶点j的度数; Δ表示最大度，δ表示最小度, D(G)=(d_j)_n×n表示G的顶点度对角矩阵.定义G的拉普拉斯矩阵为L(G)=D(G)-A(G), 由于L(G)是一个对称的半正定矩阵，所以0是L(G)的最小特征值.不妨设L(G)的特征值为

$ {\mu _1}\left( G \right) \ge {\mu _2}\left( G \right) \ge \cdots \ge {\mu _{n - 1}}\left( G \right) \ge {\mu _n}\left( G \right) = 0. $

将μ₁(G)称作图G的Laplacian谱半径, 用μ(G)表示；将μ_n-1(G)称作G的代数连通度, 用a(G)表示.由于L(G)+L(G)=nI-J, 这里I表示单位矩阵, J表示所有元素全为1的矩阵.因此μ_i(G)=n-μ_n-i(G)(1≤i≤n-1);特别地，μ(G)=n-a(G).从而得到下列事实：

设G是一个具有n个顶点的简单图.那么, μ(G)≤n等式成立当且仅当G不连通.

关于图的Laplacian谱半径上界, 学者们研究了一般图, 并且讨论了树、单圈图、二部图等特殊图, 得到了许多深刻的结果.

(1) ANDERSON等^[2]利用相邻2个顶点度给出了其上界：

$ \mu \left( G \right) \le \max \left\{ {{d_\mathit{u}} + {d_\mathit{v}}:uv \in E} \right\}, $

等式成立当且仅当G是一个正则二部图或半正则二部图.

(2) MERRIS^[3]利用平均度改进了上述上界，得到

$ \mu \left( G \right) \le \max \left\{ {{d_\mathit{u}} + {m_\mathit{u}}:u \in V} \right\}, $

这里m_u表示G中与顶点u相邻的顶点的平均二次度，即$ {{m}_{u}}=\sum\limits_{v\sim u}{{{d}_{v}}/{{d}_{u}}} $.

(3) DAS^[4]在文献[2]的基础上做了改进, 证明了：

设G是一个具有n个顶点的连通图，则

$ \begin{array}{l} \mu \left( G \right) \le \max \left\{ {{d_\mathit{u}} + {d_\mathit{v}} - \left| {{N_G}\left( u \right) \cap {N_G}\left( v \right)} \right|:} \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\left. {uv \in E\left( G \right)} \right\}, \end{array} $

其中，N_G(u)表示顶点u在G中的邻点集, N_G(u)∩N_G(v)表示这2个邻点集中的公共顶点数.

(4) LI等^[5]在上述文献的基础上, 得到

$ \mu \left( G \right) \le \max \left\{ {\frac{{{d_\mathit{u}}\left( {{d_\mathit{u}} + {m_u}} \right) + {d_\mathit{v}}\left( {{d_\mathit{v}} + {m_v}} \right)}}{{{d_\mathit{u}} + {d_\mathit{v}}}}:uv \in E} \right\}, $

等式成立当且仅当G是一个正则二部图.

(5) SHI^[6]利用最大、最小、平均度证明了：

设G是一个具有n个顶点、直径为D、最大度为Δ、最小度为δ、平均度为d的非正则连通图.则

$ \mu \left( G \right) < 2\Delta - {\left[ {\left( {n - \delta } \right)D + \frac{1}{2}\frac{1}{{\left( {\Delta - d} \right)}} - \left( {\frac{D}{2}} \right)} \right]^{ - 1}}. $

(6) STEVANOVIC^[7]证明了具有顶点最大度的树的Laplacian谱半径的一个上界

$ \mu \left( G \right) < \Delta + 2\sqrt {\Delta - 1} . $

(7) GUO^[8]利用匹配数得到了下列结论：

设T_mⁿ(2m≤n+1)表示顶点为n的树，由星图K_{1, n-m}中的m-1个悬挂点吸附m-1条悬挂边而得到.T是一个具有n个顶点, 且匹配数为β的树，则μ(T)≤r等式成立当且仅当T≅T_βⁿ，其中r是方程x³-(n-β+4)x²+(3n-3β+4)x-n=0的最大根.

(8) FENG等^[9]讨论了具有给定独立数的单圈图的Laplacian谱半径问题, 得到下列结果：

设G是一个具有n(n≥k+4)个顶点、k(k≥1)个悬挂点的单圈图，则μ(G)≤μ(U_{4, k})等式成立当且仅当G≅U_{4, k}，这里，U_{g, k}表示顶点为n(n≥k+4)的单圈图，由圈图C_g的一个顶点吸附k条长度几乎相等的路(这些路长度最多相差1)而得到.

文献[9]还得到了下列结论：

若G是一个具有n个顶点，且有k个悬挂点、围长为3、独立数为α(α≥2)的单圈图.如果p≤α-1, 则μ(G)≤μ(U_{n, α}^*)等式成立当且仅当G≅U_{n, α}^*, 这里U_{n, α}^*是单圈图, 由圈图C₃的1个顶点吸附2α-n+1条悬挂边和n-α-2条长为2的路得到.

(9) GRONE等^[10]获得了以下二部图结果：

设G是一个连通图, 则μ(G)≤q(G)等式成立当且仅当G是一个二部图, 这里q(G)表示矩阵Q(G)=D(G)+A(G)的最大特征值.

设Β_{n, m}表示所有顶点为n, 边为m的二部图，G_m表示在Β_{n, m}中具有最大Laplacian谱半径的一个二部图.

(10) LI等^[11]证明了以下结果：

对固定的n, 令$ m<\left\lfloor \frac{n}{2} \right\rfloor \left\lceil \frac{n}{2} \right\rceil $.

(ⅰ) 对所有的$ t\in \left\{ 1, 2, \cdots, \left\lceil \frac{n}{2} \right\rceil-1 \right\} $, 若m≠t(n-t), 则μ(G_m) < μ(G_m+1);

(ⅱ) 对某些$ t\in \left\{ 1, 2, \cdots, \left\lceil \frac{n}{2} \right\rceil-1 \right\} $, 若m=t(n-t), 则μ(G_m+1) < μ(G_m)=n.

(11) PATRA等^[12]得到了以下结论：

设G是一个二部图, G′是由G中的一个顶点邻接另外一个新顶点所得，则μ(G)≤μ(G′).更一般地(见文献[1]), 在图G中插入一条新边e，得到另一个图G′, 即G′=G+e.则有μ(G)≤μ(G′).

(12) MOHAR^[1]证明了下列定理：

设G=G₁∪G₂是图G的因子分解, 则

$ \max \left( {\mu \left( {{G_1}} \right),\mu \left( {{G_2}} \right)} \right) \le \mu \left( G \right) \le \mu \left( {{G_1}} \right) + \mu \left( {{G_2}} \right). $

(13) 周后卿^[13]研究了图在二元运算下, Cartesian积图的最大Laplacian特征值的上界问题.

(14) 对于具有n个顶点的Halin图G, JIA等^[14]证明了其Laplacian谱半径满足不等式：

$ n - 1 < \mu \left( G \right) \le n, $

右边不等式成立当且仅当G=W_n，W_n表示有n个顶点的轮图.

(15) LIU等^[15]讨论了具有最大Laplacian谱半径的极图问题.

(16) XING等^[16]得到了具有固定控制数的Laplacian谱半径，并刻画了其极图.

2 引理、结论及其证明

循环图  具有n个顶点的循环图G(n, S)可以定义为循环群上的一个Cayley图, 其顶点是循环群Z_n上的元素, 顶点i, j相连当且仅当j-i是S中的元素, 这里S是Z_n{0}的一个子集.循环图的矩阵是一个循环矩阵, 循环图是一个正则图, 每个顶点的度相等.

卡氏积图  设G=(V(G), E(G)), H=(V(H), E(H))是2个简单的连通图, 那么G与H的卡氏积图G×H是这样的图：其顶点集为V(G×H)=V(H×E(H; G×H中任何2个顶点(u, v)与(s, t)相邻当且仅当u=s且v与t在H中相邻；或v=t且u与s在G中相邻，这里u, s∈V(G), v, t∈V(H).

为了证明本文结论，需要下列引理：

引理1^[17]  设图G与H的顶点分别为n, m, 图G与H的Laplacian特征值分别为

$ {\mu _1}\left( G \right) \ge {\mu _2}\left( G \right) \ge \cdots \ge {\mu _{n - 1}}\left( G \right) \ge {\mu _n}\left( G \right) = 0, $

$ {\mu _1}\left( H \right) \ge {\mu _2}\left( H \right) \ge \cdots \ge {\mu _{n - 1}}\left( H \right) \ge {\mu _n}\left( H \right) = 0, $

则G与H的笛卡尔乘积G×H的Laplacian矩阵的特征值为

$ {\mu _i}\left( G \right) + {\mu _j}\left( H \right),\;\;\;\;1 \le i \le n,1 \le j \le m. $

引理2^[18]  设G是一个顶点为n(n≥4)的连通、非完全图.则G的邻接矩阵的最小特征值λ_min(G)满足

$ - \frac{n}{2} \le {\lambda _{\min }}\left( G \right) \le \frac{1}{2}\left( {1 + \sqrt {1 + \frac{{4\left( {n - 3} \right)}}{{n - 1}}} } \right). $

引理3^[19]  设图G的顶点为n(n≥4), 若G的补图G是连通的.则

$ \begin{array}{l} {\lambda _{\min }}\left( G \right) \ge \\ - \sqrt {\frac{{\left\lfloor {\frac{n}{2}} \right\rfloor \left\lceil {\frac{n}{2}} \right\rceil - 1 + \sqrt {{{\left( {\left\lfloor {\frac{n}{2}} \right\rfloor \left\lceil {\frac{n}{2}} \right\rceil - 3} \right)}^2} + 4n - 13} }}{2}} , \end{array} $

等式成立当且仅当图$ G={{K}_{\left\lceil \frac{n}{2} \right\rceil, \left\lfloor \frac{n}{2} \right\rfloor }}-e $, e是$ {{K}_{\left\lceil \frac{n}{2} \right\rceil, \left\lfloor \frac{n}{2} \right\rfloor }} $中的任意一条边.

对于一个γ-正则图G, 其Laplacian特征值与其邻接矩阵特征值之间的关系为

$ {\mu _j} = \gamma - {\lambda _j},\;\;\;\;1 \le j \le n, $

其中, λ_j为G的邻接矩阵的特征值.

定理1  设G与H是2个顶点分别为n, m(n, m≥4), 度分别为s, t的循环图.则G与H的卡氏积图G×H的Laplacian谱半径满足不等式：

$ \mu \left( {G \times H} \right) \le \left\{ \begin{array}{l} s + t + \left( {m + n} \right)/2,\;\;\;\;n,m \in {\bf{N}},\\ s + t + {p_1} + {q_1},\;\;\;\;n,m \in {\bf{E}},\\ s + t + {p_2} + {q_2},\;\;\;n,m \in {\bf{O}},\\ s + t + {p_1} + {q_2},\;\;\;n \in {\bf{E}},m \in {\bf{O}},\\ s + t + {p_2} + {q_1},\;\;\;n \in {\bf{O}},m \in {\bf{E}}, \end{array} \right. $

其中, Ν, E, O分别表示正整数集、偶数集、奇数集.并且,

$ {p_1} = \sqrt {\left( {{n^2} - 4 + 4\sqrt {{{\left( {{n^2} - 12} \right)}^2} + 64n - 208} } \right)/8} , $

$ {p_2} = \sqrt {\left( {{n^2} - 5 + 4\sqrt {{{\left( {{n^2} - 13} \right)}^2} + 64n - 208} } \right)/8} , $

$ {q_1} = \sqrt {\left( {{m^2} - 4 + 4\sqrt {{{\left( {{m^2} - 12} \right)}^2} + 64m - 208} } \right)/8} , $

$ {q_2} = \sqrt {\left( {{m^2} - 5 + 4\sqrt {{{\left( {{m^2} - 13} \right)}^2} + 64m - 208} } \right)/8} . $

证明  不妨设Ν, Ε, Ο分别表示正整数集、偶数集、奇数集.

(1) 由引理2可知,

$ \frac{n}{2} \ge - {\lambda _{\min }}\left( G \right),\frac{m}{2} \ge - {\lambda _{\min }}\left( H \right), $

$ 所以,~~~~~~~~s + \frac{n}{2} \ge s - {\lambda _{\mathit{min}}}\left( G \right), $

$ t + \frac{m}{2} \ge t - {\lambda _{\min }}\left( H \right), $

$ 即~~~~\mu \left( G \right) \le s + \frac{n}{2},\;\;\;\;\mu \left( H \right) \le t + \frac{m}{2},\;\;\;\;m,n \in {\bf{N}}. $

由引理1, 结论得证.

(2) 由引理3, 当n∈Ε时,

$ {\lambda _{\min }}\left( G \right) \ge - \sqrt {\left( {{n^2}/4 - 1 + \sqrt {{{\left( {{n^2}/4 - 3} \right)}^2} + 4n - 13} } \right)/2} , $

即

$ - {\lambda _{\min }}\left( G \right) \le \sqrt {\left( {{n^2} - 4 + 4\sqrt {{{\left( {{n^2} - 12} \right)}^2} + 64n - 208} } \right)/8} , $

所以有

$ \mu \left( G \right) \le s + \sqrt {\left( {{n^2} - 4 + 4\sqrt {{{\left( {{n^2} - 12} \right)}^2} + 64n - 208} } \right)/8} . $

同理, 当m∈Ε时可得

$ \mu \left( H \right) \le t + \sqrt {\left( {{m^2} - 4 + 4\sqrt {{{\left( {{m^2} - 12} \right)}^2} + 64m - 208} } \right)/8} . $

$ 记~~{p_1} = \sqrt {\left( {{n^2} - 4 + 4\sqrt {{{\left( {{n^2} - 12} \right)}^2} + 64n - 208} } \right)/8} , $

$ {q_1} = \sqrt {\left( {{m^2} - 4 + 4\sqrt {{{\left( {{m^2} - 12} \right)}^2} + 64m - 208} } \right)/8} . $

由引理1得

$ \mu \left( {G \times H} \right) \le s + t + {p_1} + {q_1}. $

(3) 当n∈O时，

$ \begin{array}{l} {\lambda _{\min }}\left( G \right) \ge \\ - \sqrt {\left( {\left( {{n^2} - 1} \right)/4 - 1 + \sqrt {{{\left( {\left( {{n^2} - 1} \right)/4 - 3} \right)}^2} + 4n - 13} } \right)/2} , \end{array} $

即

$ \begin{array}{l} - {\lambda _{\min }}\left( G \right) \le \\ \;\;\;\;\;\;\;\;\sqrt {\left( {{n^2} - 5 + 4\sqrt {{{\left( {{n^2} - 13} \right)}^2} + 64n - 208} } \right)/8} , \end{array} $

所以有

$ \mu \left( G \right) \le s + \sqrt {\left( {{n^2} - 5 + 4\sqrt {{{\left( {{n^2} - 13} \right)}^2} + 64n - 208} } \right)/8} . $

同理, 当m∈Ο时可得

$ \mu \left( H \right) \le t + \sqrt {\left( {{m^2} - 5 + 4\sqrt {{{\left( {{m^2} - 13} \right)}^2} + 64m - 208} } \right)/8} . $

记

$ {p_2} = \sqrt {\left( {{n^2} - 5 + 4\sqrt {{{\left( {{n^2} - 13} \right)}^2} + 64n - 208} } \right)/8} , $

$ {q_2} = \sqrt {\left( {{m^2} - 5 + 4\sqrt {{{\left( {{m^2} - 13} \right)}^2} + 64m - 208} } \right)/8} . $

于是, 由引理1得

$ \mu \left( {G \times H} \right) \le s + t + {p_2} + {q_2}. $

(4) 当n∈E, m∈O时，

$ \mu \left( G \right) \le s + \sqrt {\left( {{n^2} - 4 + 4\sqrt {{{\left( {{n^2} - 12} \right)}^2} + 64n - 208} } \right)/8} , $

$ \mu \left( H \right) \le t + \sqrt {\left( {{m^2} - 5 + 4\sqrt {{{\left( {{m^2} - 13} \right)}^2} + 64m - 208} } \right)/8} . $

$ 即~~~~~~\mu \left( G \right) \le s + {p_1},\;\;\;\mu \left( H \right) \le t + {q_2}. $

根据引理1, 有

$ \mu \left( {G \times H} \right) \le s + t + {p_1} + {q_2}. $

(5) 当n∈Ο, m∈Ε时,

$ \mu \left( G \right) \le s + \sqrt {\left( {{n^2} - 5 + 4\sqrt {{{\left( {{n^2} - 13} \right)}^2} + 64n - 208} } \right)/8} , $

$ \mu \left( H \right) \le t + \sqrt {\left( {{m^2} - 4 + 4\sqrt {{{\left( {{m^2} - 12} \right)}^2} + 64m - 208} } \right)/8} . $

$ 即~~~~~~\mu \left( G \right) \le s + {p_2},\;\;\;\mu \left( H \right) \le t + {q_1}. $

由引理1，有

$ \mu \left( {G \times H} \right) \le s + t + {p_2} + {q_1}. $

定理得证.

定理2  设G与H是2个顶点分别为n, m, 度分别为s, t的循环图.则G与H的卡氏积图G×H的Laplacian谱半径

$ \mu \left( {G \times H} \right) \le 2\left( {s + t} \right) - k - l, $

等式成立当且仅当G, H是完全图, 其中，

$ k = \left| {{N_G}\left( u \right) \cap {N_G}\left( v \right)} \right|,\;\;\;uv \in E\left( G \right), $

$ l = \left| {{N_H}\left( {u'} \right) \cap {N_H}\left( {v'} \right)} \right|,\;\;\;u'v' \in E\left( H \right). $

证明  由

$ \begin{array}{l} \mu \left( G \right) \le \max \left\{ {{d_u} + {d_v} - \left| {{N_G}\left( u \right) \cap {N_G}\left( v \right)} \right|:} \right.\\ \;\;\;\;\;\;\;\;\;\;\;\left. {uv \in E\left( G \right)} \right\} \end{array} $

可知, 对于循环图G, 有

$ \begin{array}{l} \mu \left( G \right) \le 2{d_u} - \left| {{N_G}\left( u \right) \cap {N_G}\left( v \right)} \right| = \\ \;\;\;\;\;\;\;\;\;\;\;2s - \left| {{N_G}\left( u \right) \cap {N_G}\left( v \right)} \right| = 2s - k, \end{array} $

这里, |N_G(u)∩N_G(v)|=k, uv∈E(G).

同理, 对于循环图H, 有μ(H)≤2t-l, 其中,

$ l = \left| {{N_H}\left( {u'} \right) \cap {N_H}\left( {v'} \right)} \right|,\;\;\;u'v' \in E\left( H \right). $

由引理1, 便可推得上述结论.

特别地, 当G, H是完全图时，

$ s = n - 1,t = m - 1,k = n - 2,l = m - 2. $

$ 因而，有~~~~~~~\mu \left( {G \times H} \right) = n + m. $

例1  循环图G=G(15, S₁), H=H(20, S₂)，S₁={3, 5, 6, 9, 10, 12}, S₂={4, 5, 8, 10, 12, 15, 16}, 分别是度为6, 7的正则图.由定理1可得μ(G×H)≤30.5以及μ(G×H)≤40.2；由定理2得到μ(G×H)≤20.借助计算软件, 实际求得

$ \mu \left( G \right) = 8,\;\;\;\;\mu \left( H \right) = 9,\;\;\;\;\mu \left( {G \times H} \right) = 17. $

说明定理2的结果准确性更高.

 

衷心感谢审稿专家给予本文的宝贵意见！