單位凱萊圖及其補圖的(無符號)拉普拉斯能量

袁雨晴

(蘭州交通大學數(shù)理學院 甘肅 蘭州 730070)

0 引言與預備知識

本文所考慮的圖均為簡單圖。設圖G的頂點集V(G)={v1,v2,…vn}，邊集E(G)={e1,e2,…,em}。圖G的補圖G定義如下：G的頂點集與G的頂點集相同，G中任意兩個頂點相鄰當且僅當它們在G中不相鄰。圖G的度對角矩陣[1]D(G)=diag(d1,d2,…,dn)，其中di(1≤i≤n)為頂點vi的度。圖G的鄰接矩陣[1]A(G)=(aij)n×n定義如下：若頂點vi與頂點vj相鄰，則aij=1；否則aij=0。圖G的特征值[2]是指鄰接矩陣A(G)的特征值。

定義1[6]設Γ是具有單位元1的乘群，對任意S?Γ，1?S，S-1={s-1|s∈S}=S，凱萊圖X=Cay(Γ,S)是一個無向圖。它的頂點集是V(X)=Γ，邊集是E(X)={(a,b):a,b∈Zn,ab-1∈S}。

定義2[10]對任意正整數(shù)n>1，單位凱萊圖Xn=Cay(Zn,Un)定義如下：頂點集V(Xn)=Zn，邊集E(Xn)={(a,b):a,b∈Zn,a-b∈Un}。其中Zn是模n的剩余類加群{[0],[1],…,[n-1]}，Un={a∈Zn:gcd(a,n)=1}。

注2：單位凱萊圖Xn是一個正則度為|Un|=φ(n)的正則圖，其中φ(n)為歐拉函數(shù)[11]。

定義3[12]對任意正整數(shù)n>1，單位圖Gn=Cay+(Zn,Un)是指以V(Gn)=Zn為頂點集，以E(Gn)={(a,b):a,b∈Zn,a+b∈Un}為邊集的簡單無向圖。其中Zn是指模n的剩余類加群{[0],[1],…,[n-1]}，Un={a∈Zn:gcd(a,n)=1}。

注3：當n為偶數(shù)時,單位圖Gn是|Un|=φ(n)-正則的；當n為奇數(shù)時，Gn是(φ(n),φ(n)-1)-半正則的[12]。

1 單位凱萊圖及其補圖的拉普拉斯能量

引理1[12]單位凱萊圖Xn與單位圖Gn同構當且僅當n為偶數(shù)。

引理3[14]當n為偶數(shù)時，單位圖Gn=Cay+(Zn,Un)的拉普拉斯能量LE(Gn)=2rφ(n)，其中r是整除n的不同素因子的個數(shù)。

首先考慮單位凱萊圖Xn的拉普拉斯能量。

證明 情形1當n為偶數(shù)時，結合引理1、3，容易看出，此時單位凱萊圖Xn的拉普拉斯能量LE(Xn)=2rφ(n)，其中r是整除n的不同素因子的個數(shù)。

綜上所述，單位凱萊圖Xn的拉普拉斯能量LE(Xn)=2rφ(n)，其中r是整除n的不同素因子的個數(shù)。

(2) 若p1≠2，即n為奇數(shù)，分成下面四種情形：

情形3：若n=s=p1p2…pr，則

所以，

=(2r-2)φ(n)+2n-s-1+

因為每個tk分解式中包含的不同素數(shù)的個數(shù)是不一樣的，下面分4種情形進行討論。

情形2若n=pm且p≥3,m>1，有(n-s)=(n-p)個μ(tk)=0和(p-1)=(s-1)個μ(tk)=-1。其中k=tpm-1且t=1,2,3,…,p-1時，

則

=(2r-2)φ(n)+2n-2s

情形3若n=s=p1p2…pr，有φ(n)個(k,n)=1，此時tk=n，μ(tr)=(-1)r。其余的n-1-φ(n)個k中不會出現(xiàn)μ(tk)=0的情況，但是無法確定μ(tk)=1或μ(tk)=-1的具體個數(shù)。因此有

情形3.1當r為奇數(shù)時，有

其余的n-1-φ(n)-(2r-1-1)-(2r-1-1)=n-φ(n)-2r+1個k中能使μ(tk)=1或μ(tk)=-1的個數(shù)不確定。因此有

=(2r-2)φ(n)+2n-n-1+φ(n)×

(-1)+(n-φ(n)-2r+1)×(-1)

=(2r-2)φ(n)+2r-2

=(2r-2)φ(n)+2n-n-1+φ(n)×

(-1)+(n-φ(n)-2r+1)×1

=(2r-4)φ(n)+2n-2r

情形3.2當r為偶數(shù)時，有

其余的n-1-φ(n)-2r-1-(2r-1-2)=n-φ(n)-2r+1個k中能使μ(tk)=1或μ(tk)=-1的個數(shù)不確定。因此有

=(2r-2)φ(n)+2n-n-1+φ(n)×1+

(-1)×2+(n-φ(n)-2r+1)×(-1)

=2rφ(n)+2r-4

=(2r-2)φ(n)+2n-n-1+φ(n)×1-

2+(n-φ(n)-2r+1)×1

=(2r-2)φ(n)+2n-2r-2

也即：當r為奇數(shù)時，有

≤(2r-4)φ(n)+2n-2r

當r為偶數(shù)時，有

≤(2r-2)φ(n)+2n-2r-2

情形4.1當r為奇數(shù)時，有

其余的s-1-2r-1-(2r-1-1)=s-2r個k中能使μ(tk)=1或μ(tk)=-1的個數(shù)不確定。因此有

=(2r-2)φ(n)+2n-s-

1+1+(-1)×(s-2r)

=(2r-2)φ(n)+2n+2r-2s

=(2r-2)φ(n)+2n-s+1+

(s-2r)×1

=(2r-2)φ(n)+2n-2r+1

情形4.2當r為偶數(shù)時，有

其余的s-1-2r-1-(2r-1-1)=s-2r個k中能使μ(tk)=1或μ(tk)=-1的個數(shù)不確定。因此有

=(2r-2)φ(n)+2n-s-1+

(-1)+(s-2r)×(-1)

=(2r-2)φ(n)+2n+2r-2s-2

=(2r-2)φ(n)+2n-

s-1+(-1)+(s-2r)×1

=(2r-2)φ(n)+2n-2r-2

也即：當r為奇數(shù)時，有

≤(2r-2)φ(n)+2n-2r+1

當r為偶數(shù)時，有

≤(2r-2)φ(n)+2n-2r-2

2 單位凱萊圖及其補圖的無符號拉普拉斯能量

3 結語