李曉琳，王洪波，陳海燕

(集美大學理學院,福建 廈門 361021)

0 引言

Ik(G,XG)=({detM|M為L(G,XG)的k-階子矩陣})?Z[XG],

(1)

其中Z[XG]表示整數(shù)環(huán)上的多項式環(huán)，即一個圖G的k-階臨界理想就是由它的廣義拉普拉斯矩陣的所有k-階子式生成的理想。平凡理想記為式(1)。

臨界理想作為圖臨界群的推廣是由文獻[1]首先提出的,它也被看作是圖的鄰接特征多項式和拉普拉斯特征多項式的推廣。隨后人們發(fā)現(xiàn)，臨界理想與圖G的其他很多性質(zhì)密切相關(guān),如零迫數(shù)、團數(shù)等[2-4]。眾所周知,確定一類圖臨界群的結(jié)構(gòu)是比較困難的,作為臨界群的推廣,確定圖的臨界理想顯得更為困難。到目前為止,只有完全圖、路、圈、樹、完全多部圖等幾類非常特殊圖類的臨界理想得到了研究[1,5-6],研究的方法基本上是組合方法。本文將利用線性代數(shù)的方法研究完全分裂圖的臨界理想。下面首先給出它的定義。

文獻[7]研究了完全分裂圖上沙堆模型的所有常返構(gòu)型和其他各種組合對象之間的關(guān)系。本文首先用代數(shù)方法得到完全分裂圖臨界理想的一個具體表達式,然后應用此表達式完全確定了其臨界群的結(jié)構(gòu)。

1 完全分裂圖的臨界理想

設(shè)M是L(Sn,m;Y,X)的任意一個k-階子矩陣(1≤k≤n+m)。令R=R1∪R2、C=C1∪C2分別表示它的行指標和列指標集,其中，R1=R∩U,C1=C∩U,R2=R∩V,C2=C∩V。首先注意到,當|RiCi|≥2(i=1,2)時,M中至少有兩行元素相同,所以det(M)=0。因此，計算完全分裂圖Sn,m的k-臨界理想Ik(Sn,m;Y,X)=({detM|M為L(Sn,m;Y,X)的k-階子矩陣})=({detM≠0|M為L(Sn,m;Y,X)的k-階子矩陣}),只需考慮|RiCi|≤1、|CiRi|≤1(i=1,2)的情形。為清楚起見,令ri=|Ri|,ci=|Ci|,i=1,2,則M有如下的分塊形式：

(2)

注意到，式(2)中r1+r2=c1+c2=k且|ri-ci|≤1,i=1,2。所以只有3種可能：1)r1=c1(r2=c2);2)r1=c1+1(r2=c2-1);3)r1=c1-1(r2=c2+1)。

為簡單起見,下面省略矩陣的下標,令j=(1,1,…,1)表示全1行向量,jT表示它的轉(zhuǎn)置,則對矩陣M,有如下結(jié)論。

引理1[2]設(shè)M是式(2)中的矩陣,則

為了給出det(M)的具體表達式,根據(jù)指標集Ri、Ci的選取,把P(Q)分為4類:1)類型b,R1=C1(R2=C2),對應的矩陣記作Pb(Qb);2)類型u,|R1C1|=|C1R1|=1(|R2C2|=|C2R2|=1),對應的矩陣記作Pu(Qu);3)類型r,C1?R1,|R1C1|=1(C2?R2,|R2C2|=1),對應的矩陣記作Pr(Qr);4)類型c,R1?C1,|C1R1|=1(R2?C2,|C2R2|=1),對應的矩陣記作Pc(Qc)。

(3)

(4)

(5)

(6)

(7)

所以，

(8)

(9)

(10)

(11)

(12)

(13)

設(shè)M是式(2)中的矩陣,則根據(jù)其中P、Q類型，M可分為(b,b),(b,u),(u,b),(u,u),(r,c)((c,r))。

為了方便敘述,引進下面的記號。對任意的整數(shù)k,定義集合Ty,k={yi1,yi2,…,yik,0

為簡單起見,下面用一些關(guān)于T和H代數(shù)表達式。兩個集合的乘積是指它們指標集的卡氏積,而集合相加是指具有相同指標集的兩兩相加。

下面給出本文的主要結(jié)果。

定理1 對完全分裂圖Sn,m(n,m≥2),其k-階臨界理想為

下面考慮3≤k≤n+m-1的情形。首先指出下面的事實,對任意的s≤s′,t≤t′,有

(14)

1)當3≤k≤n+m-2時,令M(u,u)表示L(Sn,m;Y,X)所有k-階(u,u)型子式構(gòu)成集合,則由引理2得,M(u,u)={Ty,sTx,t,s+t=k-2,s≤n-2,t≤m-2}。同理可得,M(b,b)={Ty,sTx,t-(Ty,s+Hy,s)Hx,t,s+t=k,s≤n,t≤m};M(b,u)={(Ty,s+Hy,s)Tx,t,s+t=k-1,s≤n,t≤m-2};M(u,b)={Ty,sHx,t,s+t=k-1,s≤n-2,t≤m};M(r,c)=M(c,r)={Ty,sTx,t,s+t=k-1,s≤n-1,t≤m-1}。由式(14)得,M(b,b)和M(r,c)中的每一個元素都可由M(u,u)中的元素生成,而M(b,u)中除了(Ty,n+Hy,n)Tx,k-n-1,M(u,b)中除了Ty,k-m-1Hx,m,其他元素都可由M(u,u)中的元素生成,所以,Ik(Sn,m;Y,X)=(Ty,sTx,t,s+t=k-2,s≤n-2,t≤m-2;(Ty,n+Hy,n)Tx,k-n-1,Ty,k-m-1Hx,m)。

2)當k=n+m-1時,此時M(u,u)=?,M(b,b)={Ty,nTx,m-1-(Ty,n+Hy,n)Hx,m-1,Ty,n-1Tx,m-(Ty,n-1+Hy,n-1)Hx,m};M(b,u)={(Ty,n+Hy,n)Tx,m-2};M(u,b)={Ty,n-2Hx,m};M(r,c)=M(c,r)={Ty,n-1Tx,m-1}。同樣由式(14)得,In+m-1(Sn,m;Y,X)=(Ty,n-1Tx,m-1,Ty,n-2Hx,m,(Ty,n+Hy,n)Tx,m-2)。

2 完全分裂圖的臨界群

首先給出臨界群的定義,詳見文獻[8]。設(shè)G是一個n個頂點的連通圖,L(G)=L(G,XG)|XG=D是它的拉普拉斯矩陣,這里D={d1,d2,…,dn}是圖G的頂點度集合。令

fk=Δk/Δk-1,k=1,2,…,n,

(15)

定理2 對完全分裂圖Sn,m(n,m≥2),則

其中a=gcd(n,m)。

證明由完全分裂圖Sn,m的定義,它的度集合D={m,…,m;m+n-1,…,m+n-1},所以,Ty,s|D={ms},Tx,s|D={(m+n)s},Hy,s|D={sms-1},Hx,s|D={s(m+n)s-1}。

由定理1可得Δ1=Δ2=1,Δn+m-1=mn-1(n+m)m-1。對3≤k≤n+m-2,不妨設(shè)n≥m,計算可得Δk,

由式(15)可得，f3=f4=…=fm=gcd(m,n+m)=a,fm+1=…=fn=m,fn+1=…=fn+m-2=m(n+m)/gcd(m,n+m)=m(n+m)/a,fn+m-1=m(n+m)。結(jié)果得證。同理可證m>n的情況。

令μ(G)表示臨界群K(G)最小生成元的個數(shù),則由定理2可得下面的推論1。

推論1 對完全分裂圖Sn,m(n,m≥2),則