上海理工大学学报  2019, Vol. 41 Issue (5): 417-421   PDF    
一类图的谱
曾建宇, 何常香     
上海理工大学 理学院,上海 200093
摘要: 设Kmm阶完全图,将n+1个m阶完全图通过固定的方式连结,得到 $\left( {mn + m} \right)$ 阶完全关联图 ${H_{n,{{K_m}}}}$ 。在利用商矩阵及秩的相关结论后,给出了完全关联图 ${H_{n,{{K_m}}}}$ 的邻接矩阵、拉普拉斯矩阵和无符号拉普拉斯矩阵的特征值,从而确定了完全关联图 ${H_{n,{{K_m}}}}$ 的邻接谱、拉普拉斯谱和无符号拉普拉斯谱。同时,基于对Brualdi-Solheid谱半径问题的研究,并将这类谱半径问题推广到图的拉普拉斯谱半径和无符号拉普拉斯谱半径的研究中,给出了 ${{\rm{{\cal H}}}_{n,{K_m}}}$ (所有点数为N的完全关联图构成的集合,其中 $N = m(n + 1)$ )中邻接谱半径的上界,拉普拉斯谱和无符号拉普拉斯谱半径的上、下界;并刻画了 ${{\rm{{\cal H}}}_{n,{K_m}}}$ 中邻接谱半径达到上界的极图,以及拉普拉斯谱和无符号拉普拉斯谱半径达到上、下界时的极图。
关键词:      商矩阵     极图    
Spectra of a Class of Graphs
ZENG Jianyu, HE Changxiang     
College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: Let Km is a complete graph of order m. By linking n+1 complete graphs of order m in a fixed way, a complete associated graph ${H_{n,{{K_m}}}}$ of order $\left( {mn + m} \right)$ was obtained. The adjacency eigenvalues, Laplacian eigenvalues and signless Laplacian eigenvalues of ${H_{n,{{K_m}}}}$ were provided according to the relevant conclusions about quotient matrix and rank. So the adjacency spectrum, Laplacian spectrum and signless Laplacian spectrum of ${H_{n,{{K_m}}}}$ were determined. At the same time, based on the study of Brualdi-Solheid spectral radius, the research of this kind of spectral radius problem was extended to the study of Laplacian spectral radius and signless Laplacian spectral radius of graphs. The upper and lower bounds of the radius of adjacency spectrum, Laplacian spectrum and signless Laplacian spectrum of ${{\rm{{\cal H}}}_{n,{K_m}}}$ (the set of complete correlated graphs with points N where $N = m(n + 1)$ ) were provided. And the extremal graphs were described where the radius of adjacency spectrum attained the upper bound and Laplacian spectrum and signless Laplacian spectrum attained the upper or lower bounds.
Key words: spectra     quotient matrix     extremal graph    
1 基本概念及背景介绍

$G$ $n$ 阶图,顶点集为 $V\left( G \right) = \left\{ {{v_1},{v_2}, \cdots ,{v_n}} \right\}$ ,边集为 $E\left( G \right)$ ${{A}}\left( G \right)$ 为邻接矩阵,若 ${v_i}$ ${v_j}$ 之间有边相连,则 ${a_{ij}} = 1$ ;否则, ${a_{ij}} = 0$ ${{D}}\left( G \right) = {\rm{diag}} ( d\left( {{v_1}} \right),$ $d\left( {{v_2}} \right), \cdots ,d\left( {{v_n}} \right) )$ 为度对角矩阵, $d\left( {{v_i}} \right)$ 表示顶点 ${v_i}$ 的度。矩阵 ${{L}}\left( G \right) = {{D}}\left( G \right) - {{A}}\left( G \right)$ ${{Q}}\left( G \right) = {{D}}\left( G \right)+ {{A}}\left( G \right)$ 分别称为 $G$ 的拉普拉斯和无符号拉普拉斯矩阵。图 $G$ 的邻接矩阵、拉普拉斯矩阵和无符号拉普拉斯矩阵的特征多项式分别记为 ${\varphi _{{A}}}\left( {G,\lambda } \right)$ , ${\varphi _{{L}}}\left( {G,\mu } \right)$ ${\varphi _{{Q}}}\left( {G,q} \right)$ 。图 $G$ 的邻接矩阵、拉普拉斯矩阵和无符号拉普拉斯矩阵的特征值即分别为 ${\varphi _{{A}}}\left( {G,\lambda } \right)$ , ${\varphi _{{L}}}\left( {G,\mu } \right)$ ${\varphi _{{Q}}}\left( {G,q} \right)$ 的根,分别记为 ${\lambda _i}\left( G \right),\;{\mu _i}\left( G \right)$ ${q_i}\left( G \right)$ $\left( {i = 1,2, \cdots ,n} \right)$ ,它们所构成的多重集合 $\left\{ {{\lambda _1}\left( G \right),} {{\lambda _2}\left( G \right), \cdots ,{\lambda _n}\left( G \right)} \right\}$ , $\left\{ {{\mu _1}\left( G \right),{\mu _2}\left( G \right), \cdots ,{\mu _n}\left( G \right)} \right\}$ $\left\{ {{q_1}\left( G \right),{q_2}\left( G \right), \cdots ,{q_n}\left( G \right)} \right\}$ 分别称为图 $G$ 的邻接谱、拉普拉斯谱和无符号拉普拉斯谱。 $\lambda \left( G \right)$ $\mu \left( G \right)$ $q\left( G \right)$ 分别为邻接、拉普拉斯和无符号拉普拉斯谱的谱半径。

图的谱可以反映出图的许多性质,图以上3种特征值都是图的同构不变量。完全图又是图论中一类基础而重要的图,其结构的特殊性导致了它的研究方法的差异性及其结果的简洁性。Bergstrand等[1]和Hartsfield等[2]分别在1986年和1992年对完全图和完全二部图进行研究并得到一些结论[1-2]。同时文献[3]也得到一些关于连通图谱半径的结论。本文主要研究特殊图类 ${H_{n,{{K_m}}}}$ 的各种谱, ${H_{n,{{K_m}}}}$ 是对书图的一个推广。对于一个给定的图类,确定该图类中图的邻接谱半径的上界并刻画达到该上界的图,这是Brualdi和Solheid在1986年提出的关于图的谱半径的一个问题[4]。此后,这些问题得到广泛研究,被称为Brualdi-Solheid问题。关于图的Brualdi-Solheid问题的研究对于研究图的特性有着重要意义,文献[5-7]按照邻接谱半径对某些图类进行了排序,其中文献[7]首先找到了具有给定匹配数的双圈图的最大邻接谱半径。

同时,Brualdi-Solheid问题也被移植到图的拉普拉斯谱半径和无符号拉普拉斯谱半径研究中。文献[8]利用树的阶数给出了树的Laplacian矩阵的最大特征值的分布;文献[9]利用阶数给出了 $n$ 阶单圈图的Laplacian矩阵的最大特征值的第一、第二、第三、第四大值及最小值。此外,对具有固定不变量的图的谱半径也有一些研究结果。特别是在文献[10-11]中,分别讨论了具有固定最大度的 $n$ 个顶点上的树和单圈图的谱半径。

本文计算邻接矩阵、拉普拉斯矩阵和无符号拉普拉斯矩阵的特征值,考虑在顶点数 $N = m(n + 1)$ 固定的情况下,给出了邻接谱半径的上界和拉普拉斯、无符号拉普拉斯谱半径的上下界,并刻画了达到上下界的极图。

定义1 设 ${K_m}$ $m$ 阶完全图,取 $n + 1$ ${K_m}$ ,将其中一个 ${K_m}$ (主图)的第 $i$ 个顶点分别和其余的 $n$ ${K_m}$ (辅图)的第 $i$ 个顶点相连( $i = 1,2, \cdots ,n$ ),所得到的 $\left( {mn + m} \right)$ 阶完全关联图记为 ${H_{n,{{K_m}}}}$ ,其中 $n \geqslant 2$ $m \geqslant 2 $

例如,书图 ${H_{4,{{K_2}}}}$ 和12阶完全关联图 ${H_{3,{{K_3}}}}$ 分别如图1图2所示。


图 1 书图 ${H_{4,{{K_2}}}}$ Fig. 1 Book graph ${H_{4,{{K_2}}}}$

图 2 完全关联图 ${H_{3,{{K_3}}}}$ Fig. 2 Complete associated graph ${H_{3,{{K_3}}}}$

从定义不难看出 ${H_{n,{{K_m}}}}$ 邻接矩阵和度对角矩阵分别为

${{A}}({H_{n,}}_{{K_m}}) \!=\! {\left( \!\!\!\!{\begin{array}{*{20}{c}} {{{A}}\left( {{K_m}} \right)}\!\!&\!\!{{{{E}}_m}}& \cdots &{{{{E}}_m}} \\ {{{{E}}_m}}\!\!&\!\!{{{A}}\left( {{K_m}} \right)}&{}&{} \\ \vdots \!\!&\!\!{}& \ddots &{} \\ {{{{E}}_m}}\!\!&\!\!{}&{}&{{{A}}\left( {{K_m}} \right)} \end{array}} \!\!\!\!\right)_{\left( {mn + m} \right) \times \left( {mn + m} \right)}}$
${{D}}\left( {{H_{n,}}_{{K_m}}} \right) \!=\! {\left( \!\!\!\!{\begin{array}{*{20}{c}} {\left({n \!+\! m \!- \!1} \right){{{E}}_m}}\!\!&\!\!{}\!\!&\!\!{}\!\!&{} \\ {}\!\!&\!\!{m{{{E}}_m}}\!\!&\!\!{}&\!\!{} \\ {}\!\!&\!\!{}\!\!&\!\! \ddots &\!\!{} \\ {}\!\!&\!\!{}\!\!&\!\!{}&\!\!{m{{{E}}_m}} \end{array}}\!\!\!\! \right)_{\left( {mn \!+\! m} \right) \times \left( {mn \!+ \!m} \right)}}$

式中, ${{{E}}_m}$ 表示 $m$ 阶单位矩阵。

${H_{n,{{K_m}}}}$ 的拉普拉斯和无符号拉普拉斯矩阵分别为

${{L}}\left( {H_{n,{{K_m}}}} \right) = {\left( {\begin{array}{*{20}{c}} {\left( {n + m - 1} \right){{{E}}_m} - {{A}}\left( {{K_m}} \right)}&{ - {{{E}}_m}}& \cdots &{ - {{{E}}_m}} \\ { - {{{E}}_m}}&{m{{{E}}_m} - {{A}}\left( {{K_m}} \right)}&{}&{} \\ \vdots &{}& \ddots &{} \\ { - {{{E}}_m}}&{}&{}&{m{{{E}}_m} - {{A}}\left( {{K_m}} \right)} \end{array}} \right)_{\left( {mn + m} \right) \times \left( {mn + m} \right)}}$
${{Q}}\left( {H_{n,{{K_m}}}} \right) = {\left( {\begin{array}{*{20}{c}} {\left( {n + m - 1} \right){{{E}}_m} + {{A}}\left( {{K_m}} \right)}&{{{{E}}_m}}& \cdots &{{{{E}}_m}} \\ {{{{E}}_m}}&{m{{{E}}_m} + {{A}}\left( {{K_m}} \right)}&{}&{} \\ \vdots &{}& \ddots &{} \\ {{{{E}}_m}}&{}&{}&{m{{{E}}_m} + {{A}}\left( {{K_m}} \right)} \end{array}} \right)_{\left( {mn + m} \right) \times \left( {mn + m} \right)}}$

定义2[12]  设 ${{M}}$ 为实对称矩阵,将其行列作相同的划分,其每一子块的平均行和作为元素按其子块的位置顺序构成的矩阵称为 ${{M}}$ 的商矩阵。

定义3[12]  给定图 $G$ ,设 ${V_1},{V_2}, \cdots ,{V_k}$ $V\left( G \right)$ 的一个划分,若对任意 $i,j \in \left\{ {1,2, \cdots ,k} \right\}$ ${V_i}$ 中的每一个点在 ${V_j}$ 中都有相同个数的邻点,则称 ${V_1},{V_2}, \cdots , $ ${V_k}$ 为均匀划分。

引理1[12]  对于一个均匀划分,若 ${{v}}$ 是商矩阵B对应特征值 $\lambda $ 的一个特征向量,则 ${{S}}{{v}}$ 是实对称矩阵 ${{M}}$ 的对应特征值 $\lambda $ 的一个特征向量,其中 ${{S}}$ ${{M}}$ 的特征矩阵。

由引理1显然可知,对于实对称矩阵 ${{M}}$ ,其商矩阵B的特征值都是 ${{M}}$ 的特征值。

推论1 对于图 $G$ 的邻接矩阵 ${{A}}\left( G \right)$ ,其任何商矩阵的特征值都是 ${{A}}\left( G \right)$ 的特征值。

证明 设 ${{A}}\left( G \right)$ 是图 $G$ 的邻接矩阵, ${{{S}}_{{A}}}$ 是图 $G$ 的一个商矩阵, ${{{S}}'_{{A}}}$ ${{{S}}_{{A}}}$ 的一个商矩阵。由引理1可知, ${{{S}}_{{A}}}$ 的特征值一定是 ${{A}}\left( G \right)$ 的特征值,同理 ${{{S}}'_{{A}}}$ 的特征值一定是 ${{{S}}_{{A}}}$ 的特征值。所以, ${{{S}}'_{{A}}}$ 的特征值都是 ${{A}}\left( G \right)$ 的特征值。

与推论1同理,可得到推论2。

推论2 对于图 $G$ 的拉普拉斯矩阵 ${{L}}\left( G \right)$ 和无符号拉普拉斯矩阵 ${{Q}}\left( G \right)$ ,它们任何商矩阵的特征值都是 ${{L}}\left( G \right)$ ${{Q}}\left( G \right)$ 的特征值。

商矩阵和均匀划分都是计算证明谱的关键工具。在推论3中,定义均匀划分并进行证明。

推论3 设 ${H_{n,{{K_m}}}}$ 的顶点集合为 $ V\left( {{H_{n,{{K_m}}}}} \right) = \{ {v_1}, \cdots ,$ ${v_m},{v_{11}}, \cdots ,{v_{1m}}, \cdots ,{v_{n1}}, \cdots ,{v_{nm}} \}$ ,其中 ${v_1}, \cdots ,{v_m}$ 是主图的顶点, ${v_{k1}},{v_{k2}}, \cdots ,{v_{km}}$ 是第 $k$ 个辅图顶点 $ ( k = 1,2, \cdots ,$ $n) $ 。则 ${V_1} = \left\{ {{v_1}} \right\}, \cdots ,{V_m}= \left\{ {{v_m}} \right\},$ ${V_{m + 1}}= \left\{ {{v_{11}},{v_{21}}, \cdots ,{v_{n1}}} \right\},$ ${V_{m + 2}} =\left\{ {{v_{12}},{v_{22}}, \;\cdots ,{v_{n2}}} \right\}, \cdots ,\;{V_{2m}} =$ $\left\{ {{v_{1m}},{v_{2m}},} \; { \cdots ,\;{v_{nm}}} \right\}$ ${H_{n,{{K_m}}}}$ 的一个均匀划分。

证明 显然, ${V_1} \cup \cdots \cup {V_m} \cup {V_{m + 1}} \cup \cdots \cup {V_{2m}} =$ $ V \left( {{H_{n,{{K_m}}}}} \right) $ ,对于任意的 $i \ne j$ ${V_i} \cap {V_j}{\rm{ = }}\emptyset $ ,即 $ {V_1}, \cdots ,{V_m},$ ${V_{m + 1}}, \cdots ,{V_{2m}}$ 是一个划分。下面证明它是一个均匀划分。

从图 ${H_{n,{{K_m}}}}$ 的结构可知:当 ${v_i} \in {V_i}$ ,其中 $i \in \{ 1, $ $2, \cdots ,m \}$ 时, ${v_i}$ 在其所在的顶点集 ${V_i}$ 中没有邻点;在顶点集 ${V_k}$ 中有且仅有1个邻点,其中 $k \in \left\{ {1,2, \cdots ,m} \right\}$ $k \ne i$ ;在顶点集 ${V_{m + l}}$ 中没有邻点,其中 $l \in \{ 1, $ $2, \cdots ,m \}$ $l \ne i$ ;在顶点集 ${V_{m + l}}$ 中有 $n$ 个邻点,其中 $l \in \left\{ {1,2, \cdots ,m} \right\}$ $l = i$

${v_{ik}} \in {V_{m + k}}$ ,其中 $i \in \left\{ {1,2, \cdots ,n} \right\}$ $k \in \left\{ {1,2, \cdots ,m} \right\}$ 时, ${v_{ik}}$ 在顶点集 ${V_l}$ 中有且仅有1个邻点,其中 $l = k$ ${v_{ik}}$ 在其他剩余的所有顶点集中都没有邻点。

综上,均匀划分得证。

2 ${H_{n,{{K_m}}}}$ 的各种谱

定理1主要计算 ${H_{n,{{K_m}}}}$ 的邻接谱。在证明过程中,主要利用了商矩阵和矩阵秩的相关结论。

定理1 图 ${H_{n,{{K_m}}}}$ 的邻接谱为 $S({{A}}) = \{ {{( - 1)}^{(m - 1)(n - 1)}}, $ ${{\left( {m \!-\! 1} \right)}^{(n \!-\! 1)}},\left( {m\! -\! 1} \right) \!\pm \!\sqrt n ,{{( -\! 1 \!\pm \!\sqrt n )}^{\left( {m\! -\! 1} \right)}} \}$ ,其中 $n \!\geqslant\! 2, m \!\geqslant \!2$

证明 根据推论2中的均匀划分, $ {{{S}}_{{{{A}}_m}}} = $ $\left( {\begin{array}{*{20}{c}} {{{A}}({K_m})}&{n{{{E}}_m}} \\ {{{{E}}_m}}&{{{A}}({K_m})} \end{array}} \right)$ ${H_{n,{{K_m}}}}$ 的商矩阵,又因为 ${{{S}}'_{{{{A}}_m}}} = $ $\left( {\begin{array}{*{20}{c}} {m - 1}&n \\ 1&{m - 1} \end{array}} \right)$ ${{{S}}_{{{{A}}_m}}}$ 的商矩阵,且 ${{{S}}'_{{{{A}}_m}}}$ 的特征多项式为 ${\lambda ^{2}} + (2 - {\rm{2}}m)\lambda + {m^2} - {2}m - n + 1$ ,可得其特征值为 $\left( {m - 1} \right) \pm \sqrt n $ ,故由推论1可知 $\left( {m - 1} \right) \pm \sqrt n $ ${{A}}({H_{n,{{K_m}}}})$ 的一重特征值。

${{{B}}_1} = - {{E}} - {{A}}\left( {{H_{n,{{K_m}}}}} \right)$ ,则

$ \begin{aligned} & R\left( {{{{B}}_1}} \right) = R\left( {\begin{array}{*{20}{c}} {{{{J}}_m}}&{{{{E}}_m}}&{{{{E}}_m}}& \cdots &{{{{E}}_m}} \\ {{{{E}}_m}}&{{{{J}}_m}}&{}&{}&{} \\ {{{{E}}_m}}&{}&{{{{J}}_m}}&{}&{} \\ \vdots &{}&{}& \ddots &{} \\ {{{{E}}_m}}&{}&{}&{}&{{{{J}}_m}} \end{array}} \right) = R\left( {\begin{array}{*{20}{c}} {{{{J}}_m}}&{{{{E}}_m}}&{{{{E}}_m}}& \cdots &{{{{E}}_m}} \\ {{{{E}}_m}}&{{{{J}}_m}}&{}&{}&{} \\ {{O}} &{ - {{{J}}_m}}&{{{{J}}_m}}&{}&{} \\ \vdots & \vdots &{}& \ddots &{} \\ {{O}} &{ - {{{J}}_m}}&{}&{}&{{{{J}}_m}} \end{array}} \right) = \end{aligned} $
$\begin{array}{l} \! R\left( {\begin{array}{*{20}{c}} {{{{J}}_m}}&{{{{E}}_m}}&{{{{E}}_m}}& \cdots &{{{{E}}_m}} \\ {{{{E}}_m}}&{{{{J}}_m}}&{}&{}&{} \\ {\begin{array}{*{20}{c}} {{O}} \\ {{O}} \end{array}}&{\begin{array}{*{20}{c}} { - {{1}}_m^{\rm{T}}} \\ { - {{1}}_{\left( {m - 1} \right) \times m}^{}} \end{array}}&{\begin{array}{*{20}{c}} {{{1}}_m^{\rm{T}}} \\ {{{1}}_{\left( {m - 1} \right) \times m}^{}} \end{array}}&{}&{} \\ \vdots & \vdots &{}& \ddots &{} \\ {\begin{array}{*{20}{c}} {{O}} \\ {{O}} \end{array}}&{\begin{array}{*{20}{c}} { - {{1}}_m^{\rm{T}}} \\ { - {{1}}_{\left( {m - 1} \right) \times m}^{}} \end{array}}&{}&{}&{\begin{array}{*{20}{c}} {{{1}}_m^{\rm{T}}} \\ {{{1}}_{\left( {m - 1} \right) \times m}^{}} \end{array}} \end{array}}\! \!\!\right) \!=\! R\left(\!\!\! {\begin{array}{*{20}{c}} {{{{J}}_m}}&{{{{E}}_m}}&{{{{E}}_m}}& \cdots &{{{{E}}_m}} \\ {{{{E}}_m}}&{{{{J}}_m}}&{}&{}&{} \\ {\begin{array}{*{20}{c}} {{O}} \\ {{O}} \end{array}}&{\begin{array}{*{20}{c}} { - {{1}}_m^{\rm{T}}} \\ {{{{O}}_{\left( {m - 1} \right) \times m}}} \end{array}}&{\begin{array}{*{20}{c}} {{{1}}_m^{\rm{T}}} \\ {{{{O}}_{\left( {m - 1} \right) \times m}}} \end{array}}&{}&{} \\ \vdots & \vdots &{}& \ddots &{} \\ {\begin{array}{*{20}{c}} {{O}} \\ {{O}} \end{array}}&{\begin{array}{*{20}{c}} { - {{1}}_m^{\rm{T}}} \\ {{{{O}}_{\left( {m - 1} \right) \times m}}} \end{array}}&{}&{}&{\begin{array}{*{20}{c}} {{{1}}_m^{\rm{T}}} \\ {{{{O}}_{\left( {m - 1} \right) \times m}}} \end{array}} \end{array}} \right) =\\ \qquad \left( {n + 1} \right)m - (m - 1)(n - 1) \\ \end{array} $

式中: ${{{J}}_m}$ 为元素全为1的 $m$ 阶矩阵; ${{1}}_m^{\rm{T}}$ 为全1的 $m$ 重向量; ${{{1}}_{\left( {m - 1} \right) \times m}}$ ${{{O}}_{\left( {m - 1} \right) \times m}}$ 分别为 $\left( {m - 1} \right) \times m$ 阶全1和全0矩阵。综上可知 $\lambda = - 1$ ${{A}}({H_{n,{{K_m}}}})$ $(m - 1)(n - 1)$ 重特征值。

${{{B}}_2} = \left( {m - 1} \right){{E}} - {{A}}\left( {{H_{n,{{K_m}}}}} \right)$ ,则

$\begin{aligned} &\quad R\left( {{{{B}}_2}} \right) = R\left( {\begin{array}{*{20}{c}} {\left( {1 - m} \right){{{E}}_m} + {{A}}\left( {{K_m}} \right)}&{{{{E}}_m}}&{{{{E}}_m}}& \cdots &{{{{E}}_m}} \\ {{{{E}}_m}}&{\left( {1 - m} \right){{{E}}_m} + {{A}}\left( {{K_m}} \right)}&{}&{}&{} \\ {{{{E}}_m}}&{}&{\left( {1 - m} \right){{{E}}_m} + {{A}}\left( {{K_m}} \right)}&{}&{} \\ \vdots &{}&{}& \ddots &{} \\ {{{{E}}_m}}&{}&{}&{}&{\left( {1 - m} \right){{{E}}_m} + {{A}}\left( {{K_m}} \right)} \end{array}} \right) =\\ &\qquad R\left( {\begin{array}{*{20}{c}} {\left( {1 - m} \right){{{E}}_m} + {{A}}\left( {{K_m}} \right)}&{{{{E}}_m}}&{{{{E}}_m}}& \cdots &{{{{E}}_m}} \\ {{{{E}}_m}}&{\left( {1 - m} \right){{{E}}_m} + {{A}}\left( {{K_m}} \right)}&{}&{}&{} \\ {{O}} &{\left( {m - 1} \right){{{E}}_m} - {{A}}\left( {{K_m}} \right)}&{\left( {1 - m} \right){{{E}}_m} + {{A}}\left( {{K_m}} \right)}&{}&{} \\ \vdots & \vdots &{}& \ddots &{} \\ {{O}} &{\left( {m - 1} \right){{{E}}_m} - {{A}}\left( {{K_m}} \right)}&{}&{}&{\left( {1 - m} \right){{{E}}_m} + {{A}}\left( {{K_m}} \right)} \end{array}} \right) \end{aligned} $

${{C}} = \left( {1 - m} \right){{{E}}_m} + {{A}}\left( {{K_m}} \right)$ ,因为

$\begin{aligned} & R\left( {{C}} \right)\! =\! R\left( \!\!\!{\begin{array}{*{20}{c}} {1 \!-\! m}&1& \cdots &1 \\ 1&{1 \!-\! m}& \cdots &1 \\ \vdots & \vdots &{}& \vdots \\ 1&1& \cdots &{1 - m} \end{array}} \!\!\!\right) = R\left( \!\!\!\!{\begin{array}{*{20}{c}} {1 \!-\! m}&1& \cdots &1 \\ m&{ - m}& \cdots &0 \\ \vdots & \vdots &{}& \vdots \\ m&0& \cdots &{ - m} \end{array}}\!\!\! \right) = R\left( \!\!\!{\begin{array}{*{20}{c}} {1 \!-\! m}&1& \cdots &1 \\ 1&{ - 1}& \cdots &0 \\ \vdots & \vdots &{}& \vdots \\ 1&0& \cdots &{ - 1} \end{array}}\!\!\! \right) = R\left( \!\!\!{\begin{array}{*{20}{c}} 0&0& \cdots &0 \\ 1&{ - 1}& \cdots &0 \\ \vdots & \vdots &{}& \vdots \\ 1&0& \cdots &{ - 1} \end{array}} \!\!\!\right) =\\ & \quad m - 1 \end{aligned} $

所以 $R\left( {{{{B}}_2}} \right){\rm{ = }}\left( {n + 1} \right)m - \left( {n - 1} \right)$ 。综上可知 $\lambda {\rm{ = }}m - 1$ ${{A}}({H_{n,{{K_m}}}})$ $n - 1$ 重特征值。

由引理1可知,商矩阵 ${{{S}}_{{{{A}}_m}}}$ 的特征值即为 ${{A}}({H_{n,{{K_m}}}})$ 的特征值。

${{{B}}_3} = \left( { - {\rm{1 + }}\sqrt n } \right){{E}} - {{{S}}_{{{{A}}_m}}}$ ,则

$\begin{aligned} &\quad R\left( {{B}} \right) \!= \!R\left(\!\!\!\! {\begin{array}{*{20}{c}} {(1 \!-\! \sqrt n ){{{E}}_m} + {{A}}({K_m})}&{n{{{E}}_m}}\\ {{{{E}}_m}}&{(1 \!-\! \sqrt n ){{{E}}_m} + {{A}}({K_m})} \end{array}} \!\!\!\!\right)=\\ &\qquad R\left( \!\!\!\!{\begin{array}{*{20}{c}} {1 - \sqrt n }\!\!\!&\!\!\!1\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!1\!\!\!&\!\!\!n\!\!\!&\!\!\!0\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!0\\ 1\!\!\!&\!\!\!{1 \!-\! \sqrt n }\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!1\!\!\!&\!\!\!0\!\!\!&\!\!\!n\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!0\\ \vdots \!\!\!&\!\!\! \vdots \!\!\!&\!\!\!{}\!\!\!&\!\!\! \vdots \!\!\!&\!\!\! \vdots \!\!\!&\!\!\! \vdots \!\!\!&\!\!\!{}\!\!\!&\!\!\! \vdots \\ 1\!\!\!&\!\!\!1\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!{1 \!-\! \sqrt n }\!\!\!&\!\!\!0\!\!\!&\!\!\!0\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!n\\ 1\!\!\!&\!\!\!0\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!0\!\!\!&\!\!\!{1 - \sqrt n }\!\!\!&\!\!\!0\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!0\\ 0\!\!\!&\!\!\!1\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!0\!\!\!&\!\!\!0\!\!\!&\!\!\!{1 - \sqrt n }\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!0\\ \vdots \!\!\!&\!\!\! \vdots \!\!\!&\!\!\!{}\!\!\!&\!\!\! \vdots \!\!\!&\!\!\! \vdots \!\!\!&\!\!\! \vdots \!\!\!&\!\!\!{}\!\!\!&\!\!\! \vdots \\ 0\!\!\!&\!\!\!0\!\!\!&\!\!\!0\!\!\!&\!\!\!1\!\!\!&\!\!\!0\!\!\!&\!\!\!0\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!{1 \!- \!\sqrt n } \end{array}} \right) \!=\! R\left( {\begin{array}{*{20}{c}} {1 - \sqrt n }\!\!\!&\!\!\!1\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!1\!\!\!&\!\!\!n\!\!\!&\!\!\!0\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!0\\ {\sqrt n }\!\!\!&\!\!\!{ - \sqrt n }\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!0\!\!\!&\!\!\!{ - n}\!\!\!&\!\!\!n\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!0\\ \vdots \!\!\!&\!\!\! \vdots \!\!\!&\!\!\!{}\!\!\!&\!\!\! \vdots \!\!\!&\!\!\! \vdots \!\!\!&\!\!\! \vdots \!\!\!&\!\!\!{}\!\!\!&\!\!\! \vdots \\ {\sqrt n }\!\!\!&\!\!\!0\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!{ - \sqrt n }\!\!\!&\!\!\!{ - n}\!\!\!&\!\!\!0\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!n\\ 1\!\!\!&\!\!\!0\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!0\!\!\!&\!\!\!{1 - \sqrt n }\!\!\!&\!\!\!0\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!0\\ { - 1}\!\!\!&\!\!\!1\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!0\!\!\!&\!\!\!{\sqrt n }\!\!\!&\!\!\!{ - \sqrt n }\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!0\\ \vdots \!\!\!&\!\!\! \vdots \!\!\!&\!\!\!{}\!\!\!&\!\!\! \vdots \!\!\!&\!\!\! \vdots \!\!\!&\!\!\! \vdots \!\!\!&\!\!\!{}\!\!\!&\!\!\! \vdots \\ { - 1}\!\!\!&\!\!\!0\!\!\!&\!\!\!0\!\!\!&\!\!\!1\!\!\!&\!\!\!{\sqrt n }\!\!\!&\!\!\!0\!\!\!&\!\!\! \cdots \!\!\!&\!\!\!{ - \sqrt n } \end{array}}\!\!\!\! \right)= \end{aligned}$
$ \begin{array}{l} R\left( {\begin{array}{*{20}{c}} {1 \!-\! \sqrt n }&1& \cdots &1&n&0& \cdots &0\\ {\sqrt n }&{ - \sqrt n }& \cdots &0&{ - n}&n& \cdots &0\\ \vdots & \vdots &{}& \vdots & \vdots & \vdots &{}& \vdots \\ {\sqrt n }&0& \cdots &{ - \sqrt n }&{ - n}&0& \cdots &n\\ 1&0& \cdots &0&{1 \!-\! \sqrt n }&1& \cdots &1\\ {\sqrt n }&{ - \sqrt n }& \cdots &0&{ - n}&n& \cdots &0\\ \vdots & \vdots &{}& \vdots & \vdots & \vdots &{}& \vdots \\ {\sqrt n }&0&0&{ - \sqrt n }&{ - n}&0& \cdots &n \end{array}} \right) \!=\! R\left( {\begin{array}{*{20}{c}} {1 \!-\! \sqrt n }&1& \cdots &1&n&0& \cdots &0\\ {\sqrt n }&{ - \sqrt n }& \cdots &0&{ - n}&n& \cdots &0\\ \vdots & \vdots &{}& \vdots & \vdots & \vdots &{}& \vdots \\ {\sqrt n }&0& \cdots &{ - \sqrt n }&{ - n}&0& \cdots &n\\ 1&0& \cdots &0&{1 \!-\! \sqrt n }&1& \cdots &1\\ 0&0& \cdots &0&0&0& \cdots &0\\ \vdots & \vdots &{}& \vdots & \vdots & \vdots &{}& \vdots \\ 0&0&0&0&0&0& \cdots &0 \end{array}} \right)\!=\\ \left( {n + 1} \right)m - \left( {m - 1} \right) \end{array}$

综上所述,可知 $\lambda {\rm{ = }} - {\rm{1 + }}\sqrt n $ ${{{S}}_{{{{A}}_m}}}$ ${{A}}({H_{n,{{K_m}}}})$ $m - 1$ 重特征值。同理可证得 $\lambda {\rm{ = }} - {\rm{1}} - \sqrt n $ ${{{S}}_{{{{A}}_m}}}$ ${{A}}({H_{n,{{K_m}}}})$ $m - 1$ 重特征值。

故有 $S({{A}}) \!= \! \{ {{( - \!1)}^{(m - 1)(n - 1)}},{{\left( {m - 1} \right)}^{(n - 1)}},\left( {m\! - \!1} \right) \pm \sqrt n ,$ ${{( - 1 \pm \sqrt n )}^{\left( {m - 1} \right)}} \}$ ,其中, $n \geqslant 2$ $m \geqslant 2$

利用定理1同样的计算证明方法,可得到 ${H_{n,{{K_m}}}}$ 的拉普拉斯和无符号拉普拉斯谱。

定理2  ${H_{n,{{K_m}}}}$ 的拉普拉斯和无符号拉普拉斯谱分别为

$ \begin{split} &\quad S({{L}}) = \left\{ {0,{1^{(n - 1)}},{m^{(m - 1)}},{{(m + 1)}^{[(m - 1)(n - 1)]}},}\right.\\ &\qquad \left.{ n + 1,{{[n + (m + 1)]}^{(m - 1)}}} \right\} \end{split} $
$ \begin{split} & \!\!\!\!\!\!S({{Q}}) = \left\{ {{{(m - 2)}^{(m - 1)}},{{(m - 1)}^{(m - 1)(n - 1)}},}\right.\\ & \!\!\!\!\!\!\quad{2(m - 1),{{(2m - 1)}^{(n - 1)}},}\\ &\!\!\!\!\!\!\quad \left.{n + (2m - 1),{{[n + (m - 1)]}^{(m - 1)}}} \right\} \end{split} $

其中, $n \geqslant 2,m \geqslant 2$

3 ${H_{n,{{K_m}}}}$ 的谱半径

对于图 ${H_{n,{{K_m}}}}$ 可知其顶点数为 $N = m(n + 1)$ ,定义 ${{\rm{\mathcal{H}}}_{n,{K_m}}}$ 表示所有点数为 $N$ 的图构成的集合。本文考虑当 $N$ 固定时,对图邻接谱半径的最大值和拉普拉斯和无符号拉普拉斯谱半径的最大和最小值分别进行计算证明。

定理3 设 $N = m(n + 1)$ 为固定值,且 $n \geqslant 2,$ $ m \geqslant 2$ 。则对于任意 $G \in {\mathcal{H}_{n,{{K_m}}}}$ $\lambda \left( G \right) \leqslant \dfrac{{N + 3\sqrt 2 - 3}}{3}$ ,等号成立当且仅当 $G{\rm{ = }}{H_{2,{{K_{\left[ {N/3} \right]}}}}}$

证明 令 ${f_1} = \lambda \left( G \right)$ ,由定理1中任一图的邻接谱可知 ${f_1} = \lambda \left( G \right) = \left| {\left( {m - 1} \right) + \sqrt n } \right| = m + $ $\sqrt n - 1$ ,其中 $n \geqslant 2,$ $m \geqslant 2 $ 。因为 $N = m(n + 1)$ ,所以可知 $n$ $m$ 成反比。假设 $m = n$ ,则 $m > \sqrt n $ ,所以可知当 $n{\rm{ = }}2$ 时, $\lambda \left( G \right)$ 达到上界 $\dfrac{{N + 3\sqrt 2 - 3}}{3}$ ,此时极图为 $G{\rm{ = }}{H_{2,{{K_{\left[ {N/3} \right]}}}}}$

与定理3类似,下面研究任意 $G \in $ ${{\rm{\mathcal{H}}}_{n,{K_m}}}$ 当其拉普拉斯谱半径达到上界时的极图。

定理4 设 $N = m(n + 1)$ 为固定值,且 $n \geqslant 2,$ $ m \geqslant 2$ ,则对于任意 $G \in $ ${{\rm{\mathcal{H}}}_{n,{K_m}}}$ $2\sqrt N \leqslant \mu \left( G \right) \leqslant \dfrac{{N + 9}}{3}$ ,右边等号成立当且仅当 $G = {H_{m,{K_m}}}$ ,左边等号成立当且仅当 $G = {H_{2,{{K_{\left[ {N/3} \right]}}}}}$ $G = {H_{\left[ {N/3} \right],{{K_2}}}}$

证明 由定理3的证明,同理可知 $\mu \left( G \right)$ 的上界为 $\dfrac{{N + 9}}{3}$ ,极图为 $G = {H_{m,{K_m}}}$

又因为 $\mu \left( G \right) \!=\! n \!+\! m \!+\! 1 \!= \!m \!+ \dfrac{N}{m} \geqslant 2\sqrt {m\dfrac{N}{m}} \!=\! 2\sqrt N $ ,当且仅当 $m = \dfrac{N}{m}$ ,即 $m = n + 1$ 时,等号成立。所以 $\,\mu \left( G \right)$ 的下界为 $2\sqrt N $ ,极图为 $G = {H_{2,{{K_{\left[ {N/3} \right]}}}}}$ $G = {H_{\left[ {N/3} \right],{{K_2}}}}$

与前两定理证明类似,下面研究对于任意 $G \in $ ${{\rm{\mathcal{H}}}_{n,{K_m}}}$ ,当其无符号拉普拉斯谱半径达到上界时的极图。

定理5 设 $N = m(n + 1)$ 为固定值,且 $n \geqslant 2, m \geqslant 2$ 。则对于任意 $G \in {\mathcal{H}_{n,{{K_m}}}}$ $2\sqrt {2N} - 2 \leqslant q\left( G \right) \leqslant \dfrac{{2N + 3}}{3}$ ,右边等号成立当且仅当 $G = {H_{2,{{K_{\left[ {N/3} \right]}}}}}$ ,左边等号成立当且仅当 $G = {H_{m,{K_{2m - 1}}}}$

证明 由定理3的证明,同理可知 $q\left( G \right)$ 的上界为 $\dfrac{{2N + 3}}{3}$ ,极图为 $G = {H_{2,{{K_{\left[ {N/3} \right]}}}}}$

又因为 $q\left( G \right) = 2m + n - 1 = 2m + n + 1 - 2 = 2m +$ $ \dfrac{N}{m} - 2 \geqslant 2\sqrt {2m\dfrac{N}{m}} - 2 = 2\sqrt {2N} - 2 $ ,当且仅当 $2m = \dfrac{N}{m}$ ,即 $2m = n + 1$ 时,等号成立。所以 $q\left( G \right)$ 的下界为 $2\sqrt {2N} - 2$ ,极图为 $G = {H_{m,{K_{2m - 1}}}}$

参考文献
[1]
BERGSTRAND D, HODGES K, JENNINGS G, et al. The sum number of a complete graph[J]. The Bulletin of the Malaysian Mathematical Society Series 2, 1989, 12(1): 25-28.
[2]
HARTSFIELD N, SMYTH W F. The sum number of complete bipartite graphs[M]//ROLF R. Graphs, Matrices, and Designs. New York: CRC Press, 1992.
[3]
BRUALDI R A, SOLHEID E S. On the spectral radius of connected graphs[J]. Publications De L’Institut Mathematique, 1986, 39(53): 45-54.
[4]
CVETKOVIĆ D, ROWLINSON P, SIMIĆ S. An introduction to the theory of graph spectra[M]. Cambridge: Cambridge University Press, 2009.
[5]
BROUWER A E, HAEMERS W H. Spectra of graphs[M]. New York: Springer, 2012.
[6]
CHANG A, TIAN F, YU A M. On the index of bicyclic graphs with perfect matchings[J]. Discrete Mathematics, 2004, 283(1/3): 51-59.
[7]
YU A M, TIAN F. On the spectral radius of bicyclic graphs[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2004(52): 91-101.
[8]
YU A M, TIAN F. On the spectral radius of unicyclic graphs[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2004(51): 97-109.
[9]
张晓东, 李炯生. 树的Laplace矩阵的最大和次大特征值[J]. 中国科学技术大学学报, 1998, 28(5): 513-518.
[10]
郭曙光. 单圈图的Laplace矩阵的最大特征值[J]. 高校应用数学学报A辑, 2001, 16(2): 131-135. DOI:10.3969/j.issn.1000-4424.2001.02.002
[11]
CHANG A, HUANG Q X. Ordering trees by their largest eigenvalues[J]. Linear Algebra and its Applications, 2003, 370: 175-184. DOI:10.1016/S0024-3795(03)00384-7
[12]
YUAN X Y, SHAN H Y, WU B F. On the spectral radius of unicyclic graphs with fixed maximum degree[J]. Ars Combinatoria-Waterloo then Winnipeg, 2011, 102: 21-31.