本文只讨论无向简单图。图G=V(G),E(G)，其中顶点集和边集分别为

$V\left( G \right)=\{{{v}_{1}},{{v}_{2}},\ldots ,{{v}_{n}}\},\text{ }E\left( G \right)=\{{{e}_{1}},{{e}_{2}},\ldots ,{{e}_{m}}\}$

图G的邻接矩阵记为A(G)，由元素a_ij组成，当顶点v_i与v_j相邻时为1，否则为0。图G的关联矩阵记为R(G)，是由元素b_ij组成，当顶点v_i与边e_j相邻时为1，否则为0。顶点v_i的度记为d_G(i)。图G的度矩阵记为D(G)，是对角线上元素为d_G(i)的n×n对角矩阵。并且有R(G)R(G)^T=A(G)+D(G)。图G的邻接特征多项式记为

${{f}_{A(G)}}\left( \lambda \right)=det\lambda {{I}_{n}}-A\left( G \right)$

式中：I_n表示大小为n的单位矩阵。由邻接特征多项式得到的特征值称为邻接特征值,从大到小排序为λ_n≥λ_n-1≥…≥λ₂≥λ₁。拥有相同邻接特征多项式的图叫做A-同谱图^[1-3]。

冠图是由两个图,图G与图H经过图操作得到的复杂图。已经有一些类的冠图被定义和研究，如冠边图、冠点图、邻居冠图等。冠图的谱难以计算，对于冠图的研究主要是将其表示为原图的谱并用于实际的计算中。本文扩大了冠点图的范围，定义了广义剖分冠点图并确定了其特征多项式，给出了构造无穷邻接同谱图类的方法及示例。

1 主要引理

计算邻接特征多项式的时候采用了舒尔补定理和矩阵的冠,下面给出相关引理。

引理1(舒尔补定理)^[4]：设矩阵A为n×n分块矩阵:

$A=\left[ \begin{align} & {{A}_{11}}\text{ }{{A}_{12}} \\ & {{A}_{21}}\text{ }{{A}_{22}} \\ \end{align} \right]$

式中:A₁₁与A₂₂为可逆方阵。则

$\eqalign{ & det\left[ \matrix{ {A_{11}}{\rm{ }}{A_{12}} \hfill \cr {A_{21}}{\rm{ }}{A_{22}} \hfill \cr} \right] = det({A_{22}})det({A_{11}}{A_{12}}{A^{1}}_{22}{A_{21}}) = \cr & det({A_{11}})det({A_{22}}{A_{21}}{A^{1}}_{11}{A_{12}}) \cr} $

引理2^[5-6]：设矩阵M为n×n实对称矩阵，j_n是长度为n的全1列向量。则矩阵M的冠，记为Γ_M(x)，是矩阵xI_n-M^-1的所有元素之和，即

特别地，当矩阵M的每一行元素之和都等于t时：

${{\Gamma }_{M}}\left( x \right)=j_{n}^{T}{{\left( x{{I}_{n}}M \right)}^{-1}}{{j}_{n}}$

对于n个顶点的r-正则图G，邻接矩阵A(G)的每一行之和都为度r，因此

${{\Gamma }_{M}}\left( x \right)=\frac{n}{x-t}$

2 广义剖分冠点图的邻接矩阵

冠图是由两个图经过图操作得到的组合图。图G与图H的冠图^[7]定义为: 将图H复制V(G)次，然后将第i个H的所有顶点与V(G)第i个顶点连接，这样由G和|V(G)|个H构造的图，称之为图G与图H的冠图。文献^[8-12]中定义了各类冠图，如边冠图、邻居冠图、剖分邻居冠图等。但是都是将图H进行n次拷贝，得到的图G与图H的组合图。

本文将冠图的定义推广为一般化的情形，即将原来n个相同的图H一般化为任意图H₁,H₂,…,H_n，定义了广义剖分冠点图。首先在图G的每条边上添加一个新的顶点得到其剖分图S(G)；将H_i中的所有顶点与V(G)中的第i个顶点连接；这样由剖分图S(G)和图H₁,H₂,…,H_n构造的图称为广义剖分冠点图，记为图S(G)⊙$\underset{i}{\overset{n}{\mathop{\wedge }}}\,$H_i。

设上述S(G)⊙$\underset{i}{\overset{n}{\mathop{\wedge }}}\,$H_i中图H₁,H₂,…,H_n顶点个数分别为t₁,t₂,…,t_n，且设N=m+n M=t₁+t₂+…+t_n。将V(G)中的顶点标记为1,2，...,n，S(G)中新加入的顶点标记为n+1,n+2,…,n+m。将H₁中的顶点标记为n+m+1,n+m+2,…,n+m+t₁，类似地当i≥2时，H_i中的顶点标记为n+m+ $\mathop {\mathop \sum \limits^{i - 1} }\limits_{k = 1} {\mkern 1mu} $ t_k+1,n+m+ $\mathop {\mathop \sum \limits^{i - 1} }\limits_{k = 1} {\mkern 1mu} $ t_k+2,…,n+m+ $\underset{k=1}{\overset{i}{\mathop{\sum }}}\,$ t_k。0_m×n为m×n的零矩阵，特别地当矩阵的大小可知时，零矩阵可以简写为0。那么S(G)⊙ $\underset{i}{\overset{n}{\mathop{\wedge }}}\,$ H_i的邻接矩阵就可以写为

$AS\left( G \right)\odot \underset{i}{\overset{n}{\mathop{\wedge }}}\,{{H}_{i}}=\left[ \begin{align} & AS\left( G \right)\text{ }C \\ & {{C}^{T}}\text{ }B \\ \end{align} \right]$

(1)

其中，

$\begin{array}{l} C = {\left[ {\begin{array}{*{20}{c}} {j_{{t_1}}^T}&0&0&0\\ 0&{j_{{t_2}}^T}&0&0\\ 0&0& \ddots &0\\ 0&0&0&{j_{{t_N}}^T}\\ 0&0&0&0 \end{array}} \right]_{N \times M}}\\ AS\left( G \right) = \left[ \begin{array}{l} 0{\rm{ }}R\left( G \right)\\ R{\left( G \right)^T}{\rm{ }}0 \end{array} \right]\\ B = \left[ {\begin{array}{*{20}{c}} {A({H_1})}&0&0\\ 0&0&0\\ 0&0&{A({H_n})} \end{array}} \right] \end{array}$

3 图S(G)⊙$\underset{i}{\overset{n}{\mathop{\wedge }}}\,$H_i的邻接特征多项式

定理1 设图G有n个顶点m条边。H_i为任意图，i=1,2，…,n。那么

$\begin{array}{l} det\left[ {\left[ {\begin{array}{*{20}{c}} {\lambda - {\Gamma _{A({H_1})}}\left( \lambda \right)}&0&0&0\\ 0& \ddots &0&0\\ 0&0&{\lambda - {\Gamma _{A({H_n})}}\left( \lambda \right)}&0\\ 0&0&0&{\lambda {I_m}} \end{array}} \right] - A\left( {S\left( G \right)} \right)} \right]\cdot\\ \mathop \prod \limits_i^n {f_{A({H_i})}}\left( \lambda \right) \end{array}$

证明：设图H_i有t_i个顶点，由式(1)及邻接特征多项式的定义并运用舒尔补定理可知:

$\matrix{ {{f_{AS\left( G \right) \odot \mathop \wedge \limits_i^n {H_i}}}\left( \lambda \right) = det\left[ {\matrix{ {\lambda {I_N} - A\left( {S\left( G \right)} \right) - C} \hfill \cr { - {C^T}\lambda {I_M} - B} \hfill \cr } } \right] = } \hfill \cr {det\left( {\lambda {I_N}A\left( {S\left( G \right)} \right)} \right)C{{\left( {\lambda {I_M}B} \right)}^{ - 1}}{C^T} \bullet (\lambda {I_M} - B)} \hfill \cr } $

记

$det\left( {\lambda {I_M} - B} \right) = det\left[ \begin{array}{l} \lambda {I_{{t_1}}} - A{H_1}{\rm{ }}0{\rm{ }}0\\ 0{\rm{ }} \ddots {\rm{ }}0\\ 0{\rm{ }}0{\rm{ }}\lambda {I_{{t_n}}} - A{H_n} \end{array} \right] = \mathop \prod \limits_i^n {f_{A({H_i})}}\left( \lambda \right)$

又因为

$\begin{array}{l} C\lambda {I_M}{B^{1}}{C^T} = C\left[ {\begin{array}{*{20}{c}} {\lambda {I_{{t_1}}} - A{{\left( {\left( {{H_1}} \right)} \right)}^{ - 1}}}&0&0\\ 0& \ddots &0\\ 0&0&{\lambda {I_{{t_n}}} - A{H_n}^{ - 1}} \end{array}} \right]{C^T} = \\ \left[ {\begin{array}{*{20}{c}} {{j^T}_{{t_1}}\lambda {I_{{t_1}}} - A{H_1}^{ - 1}}&0&0\\ 0&{{j^T}_{{t_1}}\lambda {I_{{t_1}}} - A{H_1}^{ - 1}}&0\\ 0&0&0 \end{array}} \right]{C^T} = \\ \left[ {\begin{array}{*{20}{c}} {{j^T}_{{t_1}}{{\left( {\lambda {I_{{t_1}}}A\left( {{H_1}} \right)} \right)}^{1}}{j_{{t_1}}}}&0&0&0\\ 0& \ddots &0&0\\ 0&0&{{j^T}_{{t_n}}\lambda {I_{{t_n}}} - A{H_n}^{ - 1}{j_{{t_n}}}}&0\\ 0&0&0&0 \end{array}} \right] = \\ {\left[ {\begin{array}{*{20}{c}} {{\Gamma _{A{H_1}}}\left( \lambda \right)}&0&0&0\\ 0& \ddots &0&0\\ 0&0&{{\Gamma _{A{H_n}}}\left( \lambda \right)}&0\\ 0&0&0&0 \end{array}} \right]_{N \times N}} \end{array}$

所以

$\begin{array}{l} {f_{AS\left( G \right) \odot \mathop \wedge \limits_I^n {H_i}}}\left( \lambda \right) = \\ det\left[ {\lambda {I_N}A\left( {S\left( G \right)} \right)} \right] - \left[ {\begin{array}{*{20}{c}} {{\Gamma _{A{H_1}}}\left( \lambda \right)}&0&0&0\\ 0& \ddots &0&0\\ 0&0&{{\Gamma _{A{H_n}}}\left( \lambda \right)}&0\\ 0&0&0&0 \end{array}} \right]\cdot\\ \mathop \prod \limits_i^n {f_{A{H_i}}}\left( \lambda \right) = det\left[ {\begin{array}{*{20}{c}} {\lambda - {\Gamma _{A{H_1}}}\left( \lambda \right)}&0&0&0\\ 0& \ddots &0&0\\ 0&0&{\lambda - {\Gamma _{A{H_n}}}\left( \lambda \right)}&0\\ 0&0&0&{\lambda {I_m}} \end{array}} \right]\\ - AS\left( G \right)\cdot\mathop \prod \limits_i^n {f_{A{H_i}}}\left( \lambda \right) \end{array}$

因此，得证。

推论1 图G有n个顶点，m条边。若对于图H_i(i=1,2，…,n)，有Γ_AHi(λ)=Γ_AH(λ)，那么

$\begin{array}{l} {f_{AS\left( G \right) \odot \mathop \wedge \limits_I^n {H_i}}}\left( \lambda \right) = det\left( {{\lambda ^2}\lambda {\Gamma _{AH}}\left( \lambda \right)} \right){I_n} - AS\left( G \right) - D\left( G \right)\cdot\\ {\lambda ^{m - n}}\cdot\mathop \prod \limits_i^n {f_{A{H_i}}}\left( \lambda \right) \end{array}$

(42)

特别地,若对于i=1,2，…,n，有H_iH那么

$\begin{array}{l} {f_{AS\left( G \right) \odot \mathop \wedge \limits_I^n {H_i}}}\left( \lambda \right) = det\left( {{\lambda ^2} - \lambda {\Gamma _{AH}}\left( \lambda \right){I_n} - A\left( G \right)D\left( G \right)} \right)\cdot{\lambda ^{m - n}}\cdot\\ {\left( {{f_{AH}}\left( \lambda \right)} \right)^n} \end{array}$

(32)

f_{AS(G)⊙$\underset{i}{\overset{n}{\mathop{\wedge }}}\,$Hi}(λ)=detλ²-λΓ_AH(λ)I_n-A(G)-D(G)·λ^m-n·f_AH(λ)ⁿ

证明：若对于i=1,2，…,n，有Γ_AHi(λ)=Γ_AH(λ)，那么设

$\begin{array}{l} \Delta = \left[ {\begin{array}{*{20}{c}} {\lambda - {\Gamma _{A({H_1})}}\left( \lambda \right)}&0&0&0\\ 0& \ddots &0&0\\ 0&0&{\lambda - {\Gamma _{A({H_n})}}\left( \lambda \right)}&0\\ 0&0&0&{\lambda {I_m}} \end{array}} \right] = \\ \left[ {\begin{array}{*{20}{c}} {\lambda - {\Gamma _{A(H)}}\left( \lambda \right)}&0&0&0\\ 0& \ddots &0&0\\ 0&0&{\lambda - {\Gamma _{A(H)}}\left( \lambda \right)}&0\\ 0&0&0&{\lambda {I_m}} \end{array}} \right] = \\ \left[ {\begin{array}{*{20}{c}} {\lambda - {\Gamma _{A(H)}}\left( \lambda \right){I_n}}&0\\ 0&{\lambda {I_m}} \end{array}} \right] \end{array}$

并且根据对图S(G)⊙$\underset{i}{\overset{n}{\mathop{\wedge }}}\,$H_i中顶点的标号可知S(G)的邻接矩阵为

$AS\left( G \right) = \left[ \begin{array}{l} 0{\rm{ }}R\left( G \right)\\ R{\left( G \right)^T}{\rm{ }}0 \end{array} \right]$

所以

$\begin{array}{l} {\lambda ^m}det\left[ {\left( {\lambda - {\Gamma _{A(H)}}\left( \lambda \right)} \right){I_n} - \frac{1}{\lambda }R\left( G \right)R{{\left( G \right)}^T}} \right] = \\ {\lambda ^{mn}}det{\lambda ^2} - \left[ {\lambda {\Gamma _{A(H)}}\left( \lambda \right)} \right]{I_n} - A\left( G \right) - D\left( G \right) \end{array}$

由此，此推论的结果已证得。

由引理2及推论1可以得到下面的推论。

推论2 图G有n个顶点，m条边。图H₁,H₂,…,H_n均为t个顶点的r-正则图，那么

${f_{AS\left( G \right) \odot \mathop \wedge \limits_I^n {H_i}}}\left( \lambda \right) = det\left[ {{\lambda ^2} - \frac{{\lambda t}}{{\lambda - r}}{I_n} - A\left( G \right) - D\left( G \right)} \right]\cdot{\lambda ^{m - n}}\cdot\mathop \prod \limits_i^n {f_{A{H_i}}}\left( \lambda \right)$

由推论1可得下面的推论。

推论3 r-正则图G有n个顶点，m条边，H为一个任意图。设图G的第i个邻接特征值为λ_i(G)，那么图G与n个图H构成的剖分冠点图的邻接特征多项式如下:

$\begin{array}{l} {f_{AS\left( G \right) \odot \mathop \wedge \limits_I^n {H_i}}}\left( \lambda \right) = {\lambda ^{mn}}\cdot{f_{AH}}{\left( \lambda \right)^n}\cdot\\ \mathop \prod \limits_i^n \left( {{\lambda ^2} - \lambda {\Gamma _{A(H)}}\left( \lambda \right) - {\lambda _i}\left( G \right) - r} \right) \end{array}$

4 广义剖分冠点图的邻接同谱图

推论4 G₁和G₂是两个邻接同谱的r-正则图，若图H₁,H₂,…,H_n的邻接矩阵的冠相等，即

${\Gamma _{A{H_1}}}\left( \lambda \right) = \cdots = {\Gamma _{A{H_n}}}\left( \lambda \right)$

那么S(G₁)⊙$\underset{i}{\overset{n}{\mathop{\wedge }}}\,$H_i 和S(G₂)⊙$\underset{i}{\overset{n}{\mathop{\wedge }}}\,$H_i是邻接同谱的。

推论5 图G有n个顶点。取{H_i|i=1,2，…}为一簇邻接同谱图族(其中H_i可有相同的)，且Γ_AHi(λ)=Γ_A(H)(λ)。那么任取这个邻接同谱图族中大小为n的子集{H_i1,H_i2,…,H_in}与图G所构成的广义剖分冠点图S(G)⊙∧nk=1H_ik之间是彼此邻接同谱的。

对于推论5，我们给出如下例子:如图 1所示，图G₂和图G₃是邻接同谱图，其邻接特征多项式均为λ⁷-11λ⁵-10λ⁴+16λ³+16λ²，且它们邻接矩阵的冠值也相等，即

${\Gamma _{A({G_2})}}\left( \lambda \right) = {\Gamma _{A({G_3})}}\left( \lambda \right) = - \frac{{7{x^3} + {x^2}18x + 4}}{{x{x^3} + 3{x^2} + 4x8}}$

那么取邻接同谱图族{H_i|H₁=G₂,H₂=G₃,H₃=G₂,H₄=G₃,H₅=G₂,H₆=G₃}。任取这个邻接同谱图族中大小为3的子集，即{H₁,H₃,H₅}、{H₂,H₄,H₆}、{H₁,H₂,H₃}、{H₂,H₃,H₄,}，与图G所构成的广义剖分冠点图(如图 2就是图G与{H₁,H₂,H₃}构成的广义剖分冠点图S(G)⊙∧3i=1H_i)的邻接特征多项式均相等，为

$\begin{array}{l} {\lambda ^{26}}58{\lambda ^{24}}96{\lambda ^{23}} + 1214{\lambda ^{22}} + 3{\rm{ }}944{\lambda ^{21}}\\ 7{\rm{ }}724{\lambda ^{20}}50{\rm{ }}900{\lambda ^{19}}37{\rm{ }}431{\lambda ^{18}} + 185{\rm{ }}788{\lambda ^{17}} + \\ 360{\rm{ }}562{\lambda ^{16}}140{\rm{ }}748{\lambda ^{15}}907{\rm{ }}792{\lambda ^{14}}458{\rm{ }}196{\lambda ^{13}} + \\ 895{\rm{ }}676{\lambda ^{12}} + 967{\rm{ }}184{\lambda ^{11}}228{\rm{ }}480{\lambda ^{10}}627{\rm{ }}680{\lambda ^9}\\ 96{\rm{ }}832{\lambda ^8} + 141{\rm{ }}824{\lambda ^7} + 31{\rm{ }}232{\lambda ^6}10{\rm{ }}752{\lambda ^5} \end{array}$

即这些广义剖分冠点图之间也是邻接同谱的。

5 结论

本文推广了剖分冠点图的定义，得到了可以冠任意图的广义剖分冠点图。可以对其他冠图作进一步的研究，尝试得到其广义定义下的图谱。巧妙地得到了无穷的邻接同谱图类，这一结论对研究化学图论有益。