设G是一个有n个顶点和m 条边的图,令A(G),D(G),B(G)和L(G)分别表示它的邻接矩阵、度对角矩阵、关联矩阵和线图,则众所周知^[9]:

B(G)^TB(G)=A(L(G))+2I_m,

这里B(G)^T是B(G)的转置,I_m是m 阶单位矩阵.进一步地如果G 是 r-正则图,那么

B(G)B(G)^T=A(G)+rI_n.

Cvetkovic^'等^[10]引进了图G的含有两个变量的广义特征多项式:

F_G(λ,μ)=det(λI_n-(A(G)-μD(G))),

则图G的Bartholdi Zeta函数与广义特征多项式之间的关系是本文中计算的出发点.

引理1^[11-12] 设 G 是 n个顶点和 m 条边的连通图,则

Z_G(u,t)^-1=[1-(1-u)²t²]^m-ntⁿF_G[1/t-

(1-u)²t,(1-u)t],

F_G(λ,μ)=

(λⁿ)/((1-μ²)^m)Z_G(1-(λμ)/(1-μ²),(1-μ²)/λ)^-1.

此外还需要下面关于矩阵的两个结论:

引理2^[12] 令M₁,M₂,M₃ 和 M₄ 分别是 p×p,p×q,q×p和 q×q 阶矩阵,其中 M₁,M₄ 可逆,则

det[M₁ M₂

M₃ M₄]=

det(M₄)·det(M₁-M₂M^-1₄ M₃)=

det(M₁)·det(M₄-M₃M^-1₁ M₂).

本节中给出本研究主要结论及其证明.首先先引入一些符号.

设J_m×n表示m行n列的全一矩阵.M是一个n阶矩阵,Γ_M(x)表示(xI_n-M)^-1所有的元素和,即

Γ_M(x)=J^T_1×n(xI_n-M)^-1J_1×n.

给定u,v,令:

(i)β=1-(1-u)²t²,

(ii)γ₁=1+(1-u²)t²,

(iii)γ₂=1+(1-u)(1+u+n₂)t²,

(iv)x=1/t-(1-u)²t,

(v)(～overt)=(1-u)t.

定理1 设图G₁是有 n₁ 个顶点和 m₁ 条边的r-正则图,G₂ 是有n₂ 个顶点和m₂条边的任意图.记r=λ₁≥λ₂≥…≥λ_n1 为A(G₁)的特征值,则

Z_G1∨G2(u,t)^-1=γ^m_1-n1₁ β^{2m_1+n1n_2-n1-n2}[(β+

(2r+n₂)(1-u)t²-αn₁t-rt)γ₁-2rt²]

[β+n1(1-u)t2]n2∏n1i=2[(β+(2r+

n₂)(1-u)t²-λ_it)γ₁-rt²-λ_it²]

Z_G2[u-(n₁(1-u)²t²)/β,(tβ)/(β+n₁(1-u)t²)]^-1.

其中α=Γ_{A(G2)-(1-u)tD(G2)}(1/tβ+n₁(1-u)t).

证明 首先由图G₁∨G₂的定义知道,它有n₁+m₁+n₂个顶点,3m₁+m₂+n₁n₂条边,所以由引理1,有

Z_G1∨G2(u,t)^-1=

β^{2m_1+m2+n_1n2-n_1-n2}t^n_1+m1+n₂F_G1∨G2(x,(～overt)).(1)

对G₁∨G₂的顶点做适当标号使得其邻接矩阵和度对角矩阵有如下形式:

A(G₁∨G₂)=[A(G₁)B(G₁)J_n1×n2

B(G₁)^T 0_{m1×m1 0m1×n2}

J_{n2×n10n2×m1 A(G2)],}

D(G₁∨G₂)=

[(2r+n_{2)In1 0n1×m1 0n1×n2}

0_{m1×n1 2Im1 0m1×n2}

0_{n2×n1 0n2×m1 D(G2)+n1In2].}

由引理2可得

F_G1∨G2(x;(～overt))=

det[P -B(G₁)-J_n1×n2

-B(G₁)^T(x+2(～overt))I_{m1 0m1×n2}

-J_{n2×n1 0n2×m1 Q]=}

det((x+n_{1(～overt))In2-A(G2)+(～overt)D(G2))·}

det(S)=F_G2(x+n_{1(～overt);(～overt))·det(S),}

其中:P=(x+(2r+n_{2)(～overt))In1-A(G1),Q=(x+n1(～overt))In2-A(G2)+(～overt)D(G2).}

S=[P -B(G₁)

-B(G₁)^T(x+2(～overt))I_{m1]-[-Jn1×n2}

0_m1×n2]

Q^-1[-J_{n2×n1 0n2×m1]=}

[P-Γ_{A(G2)-(～overt)D(G2)}(x+n_{1(～overt))Jn1×n1 -B(G1)}

-B(G₁)^T(x+2(～overt))I_m1].

因为G₁ 是r-正则图,所以B(G₁)B(G₁)^T=rI_{n1+A(G1).为简单起见,下面令 α=ΓA(G2)-(～overt)D(G2)(x+n1(～overt)),J=Jn1×n1.再次利用引理 2,并且J的特征值为n,0,0,G1为正则图,则化简得}

det(S)=(x+2(～overt))^m_1-n1det[((x+

2r(～overt)+n_{2(～overt))(x+2(～overt))-r)In1-α(x+2(～overt))J-}

(x+2(～overt)+1)A(G₁)]=(x+2(～overt))^m_1-n1

[(x+(2r+n_{2)(～overt)-αn1-r)(x+2(～overt))-}

2r]·∏n1i=2[(x+(2r+n2)(～overt)-λi)(x+2(～overt))-

r-λ_i],

从而得到下面的关系式:

F_G1∨G2(x;(～overt))=F_G2(x+n_{1(～overt);(～overt))(x+}

2(～overt))^m_1-n1[(x+(2r+n_{2)(～overt)-αn1-r)(x+2(～overt))-}

2r]·∏n1i=2[(x+(2r+n2)(～overt)-λi)(x+2(～overt))-

r-λ_i].(2)

再由引理1得

F_G2(x+n_{1(～overt);(～overt))=((x+n1(～overt))ⁿ²)/((1-(～overt)²)^m2)ZG2}

(1-((x+n_{1(～overt))(～overt))/(1-(～overt)²),(1-(～overt)²)/(x+n1(～overt)))^-1.(3)}

由式(1)～(3)和x=1/t-(1-u)²t以及(～overt)=

(1-u)t,整理可得结果.

定理2 假设图G₁ 是有n₁个顶点和m_{1条边的r-正则图,G2是有n2个顶点和m2条边的任意图.记r=λ1≥λ2≥…≥λn1为A(G1)的特征值,从而}

ZG1∨·G2(u,t)-1=γm1-n11 βm1+n1n2-n1-n2[(β+

(r+n_{2)(1-u)t²-αn1t)γ1-2rt²]·[β+}

n1(1-u)t2]n2∏n1i=2[(β+(r+n2)(1-

u)t²)γ₁-rt²-λ_it²]Z_G2[u-(n_{1(1-u)²t²)/β,}

(tβ)/(β+n_{1(1-u)t²)]^-1,}

这里 α=Γ_{A(G2)-(1-u)tD(G2)}(1/tβ+n_1(1-u)t).

证明 由图G₁∨^·G₂的定义知,它有n_{1+m1+n2个顶点,2m1+n1n2+m2条边,所以由引理1,有}

Z_G1∨^·G2(u,t)^-1=

β^{m_{1+m2+n1n2-n1-n2}}t^n_1+m1+n2F_G1∨^·G2(x,(～overt)).

对顶点进行合适的标号后,可以得到G₁∨^·G₂的邻接矩阵和度对角矩阵分别如下:

A(G₁∨^·G₂)=[0_{n1×n1 B(G1)Jn1×n2}

B^T(G₁)0_{m1×m1 0m1×n2}

J_{n2×n1 0n2×m1 A(G2)],}

D(G₁∨^·G₂)=

[(r+n_{2)In1 0n1×m1 0n1×n2}

0_{m1×n1 2Im1 0m1×n2}

0_{n2×n1 0n2×m1 D(G2)+n1In2].}

采用与定理1相同的方法计算可得下面的结论.

下面要讨论边剖分边联图G₁和G₂的Bartholdi Zeta函数.

定理 3 假设图G₁是有n₁个顶点和m_{1条边的r-正则图,G2是n2个顶点和m2条边的任意图.记r=λ1≥λ2≥…≥λn1 为A(G1)的特征值,从而}

ZG1G2(u,t)-1=γm1-n12 βm1+m1n2-n1-n2

[(γ₂-αm_{1t)(β+r(1-u)t²)-2rt²]}

[β+m_{1(1-u)t²]ⁿ²∏ⁿ¹i=2[(β+r(1-u)t²)γ2-}

rt²-λ_it²]·Z_G2[u-(m_{1(1-u)²t²)/β,}

(tβ)/(β+m_{1(1-u)t²)]^-1,}

其中α=Γ_{A(G2)-(1-u)tD(G2)}[1/tβ+m₁(1-u)t].

证明 由图G₁G₂的定义知,它有n_{1+m1+n2个顶点,2m1+m1n2+m2条边,所以由引理1,有}

Z_G1∨G2(u,t)^-1=

β^{m_{1+m1n2+m2-n1-n2}}t^n_1+m1+n2F_G1G2(x,(～overt)).

对顶点进行合适的标号,可以得到G₁∨G₂ 的邻接矩阵和度对角矩阵分别如下:

A(G₁G₂)=[0_{n1×n1 B(G1)0n1×n2}

B^T(G₁)0_{m1×m1 Jm1×n2}

0_{n2×n1 Jn2×m1 A(G2)],}

D(G₁G₂)=

[rI_{n1 0n1×m1 0n1×n2}

0_{m1×n1(n2+2)Im1 0m1×n2}

0_{n2×n1 0n2×m1 D(G2)+m1In2].}

从而det(xI_{n1+m1+n2-AG1G2+(～overt)D(G1∨G2))的展开式如下:}

F_G1∨G2(x;(～overt))=

det[(x+r(～overt))I_{n1 -B(G1)0n1×n2}

-B^T(G₁)(x+(n_{2+2)(～overt))Im1 -Jm1×n2}

0_{n2×n1 -Jn2×m1 E]=}

det((x+m_{1(～overt))In2-A(G2)+(～overt)D(G2))·}

det(S)=F_G2(x+m_{1(～overt);(～overt))·det(S),}

S=[(x+r(～overt))I_{n1 -B(G1)}

-B^T(G₁)(x+(n_{2+2)(～overt))Im1]-}

[0_n1×n2

J_{m1×n2][(x+m1(～overt))In2-A(G2)+}

(～overt)D(G₂)]^-1[0_{n2×n1 Jn2×m1]=}

[(x+r(～overt))I_{n1 -B(G1)}

-B^T(G₁)F].

其中:E=(x+m_{1(～overt))In2-A(G2)+(～overt)D(G2); F=(x+(n2+2)(～overt))Im1-ΓA(G2)-(～overt)D(G2)(x+m1(～overt))Jm1×m1.}

因为B^T(G₁)B(G₁)=2I_{m1+A(L(G1)).同时记 ΓA(G2)-(～overt)D(G2)(x+m1(～overt))为α,利用引理2可得}

det(S)=(x+r(～overt))^n₁·det[(x+(n_{2+2)(～overt))Im1-}

αJ-1/(x+r(～overt))B^T(G₁)B(G₁)]=(x+r(～overt))^n_1-m1·

det[(x+(n_{2+2)(～overt))(x+r(～overt))-2)Im1-}

α(x+r(～overt))J-A(L(G₁))].

现在回顾两个结论

(i)J_{m1×m1 的特征值分别为 m1,0,…,0;}

(ii)因为G₁ 是r-正则,所以它的线图 L(G₁)是2r-2-正则.进一步得到A(L(G₁))的特征值为λ_i+r-2,i=1,…,n₁,并且特征值-2的重数为m_1-n1.

所以本文中可以得到:

det(S)=[x+(n₂+2)(～overt)]^m_1-n1[(x+(n₂+

2)(～overt)-αm_{1)(x+r(～overt))-2r]∏ⁿ¹i=2[(x+}

(n₂+2)(～overt))(x+r(～overt))-r-λ_i].

后面的证明过程与定理1相似,易得定理3.

证毕.