給定懸掛點數(shù)和關(guān)聯(lián)Q-譜半徑最大的k一致超圖的結(jié)構(gòu)

朱忠熏，周鋆鵬

(中南民族大學 數(shù)學與統(tǒng)計學學院，武漢 430074)

矩陣是高等代數(shù)學中的常見工具，也常見于統(tǒng)計分析等應(yīng)用數(shù)學學科中，但隨著社會的發(fā)展，高階高維、多索引數(shù)據(jù)在科學和工程領(lǐng)域的應(yīng)用變得十分廣泛.因此作為矩陣的高階推廣，張量(超矩陣)開始被學者們所關(guān)注.由于張量與超圖有著自然的對應(yīng)關(guān)系，因此可用張量來研究超圖.當今，超圖理論已經(jīng)成為了相關(guān)領(lǐng)域?qū)W者們研究的熱點問題.很多關(guān)于超圖譜理論的結(jié)果和性質(zhì)被提出，關(guān)于一致超圖的結(jié)果可看文獻[1-4]；關(guān)于一般超圖的結(jié)果可看文獻[5-6]；關(guān)于超圖極譜的結(jié)果可看文獻[7].文獻[2]中作者首次提出了關(guān)聯(lián)張量的概念，通過該張量的元素可以得到在與該張量對應(yīng)的一致超圖中包含某一個、兩個、或兩個以上點的超邊數(shù)量，該性質(zhì)是其他張量所不具有的，因此本文致力于研究關(guān)聯(lián)張量.在文獻[2]中給出了一般超圖對應(yīng)關(guān)聯(lián)張量的一些重要性質(zhì)；并且刻畫了一致超樹的極值結(jié)構(gòu).本文則刻畫階數(shù)為n且具有r個懸掛點的k一致連通超圖的極值結(jié)構(gòu)，刻畫了n-r≥k，以及n-r∈[k-1]中的一些情況.

1 準備知識

對于正整數(shù)k，張量A=(Ai1i2…ik是一個k階n維的數(shù)組，其ij∈[n]:={1,…,n}，j∈[k].如果對于下標的任意置換σ有Ai1i2…lk=Aσ(i1)σ(i2)…σ(ik)，則稱張量A是對稱的.

對階數(shù)為n大小為m的k一致超圖H,它的關(guān)聯(lián)矩陣B(H)定義為B(H)=(B(H)ij)n×m，其中:

H的關(guān)聯(lián)張量定義為Q*(H)=B(H)IB(H)T(見文獻[8])，這里I是適當維數(shù)的單位張量.通過張量積的定義[9],有:

(Q*(H))i1i2…ik=(B(H)IB(H)T)i1i2…ik=

對邊e={vi1,…，vik}和向量x∈Rn,記x(e)=xvi1+…+xvik，則：

ρ(Q*(H))=max{|λ|∶Q*(H)xk-1=λx[k-1]}.

通過著名的Perron-Frobenius定理，存在一個對應(yīng)于ρ(Q*(H))的單位正向量，稱其為H的主特征向量.為了方便，記ρQ(H)=ρ(Q*(H)).

引理1設(shè)H是連通k一致超圖.若H′是H的子圖，則ρQ(H′)≤ρQ(H).

引理3設(shè)H=(V,E)是連通k一致超圖且x是H的主特征向量.對i,m∈V(H)，如對每一條邊e∈E,i∈e暗示著m∈e，則xi≤xm.此外，如存在一條邊包含點m且不包含i，則xi

則:

通過引理2和引理3，類似于文獻[10]中引理5的證明，有下面的結(jié)果.

(i)c=2且t=0，或c≥3(參見文獻[10]).

2 主要結(jié)果

結(jié)論1F(V1)?F(V2)?……?F(Vc).

對任l2>l1，l1,l2∈[c],如果存在點u∈F(Vl2)F(Vl1)和點v∈F(Vl1)F(Vl2)，使得xu≥xv.設(shè)H1=H+((el1{v}∪{u})-el1，則通過引理2得ρQ(H1)>ρQ(H)，矛盾.因此F(Vl2)?F(Vl1)或F(Vl1)?F(Vl2).注意到|F(Vl2)|=k-|Vl2|≤k-|Vl1|=|F(Vl1)|.故F(Vl2)?F(Vl1).由l1，l2的任意性可得結(jié)論1.

設(shè)

因|V0|+|F(V1)|=n-r≥k+1且|V1|+|F(V1)|=k，有|V0|>|V1|.通過引理3，可設(shè):

因|Vi+1|>|Vi|，設(shè)

ρQ(H)+[x(e0)]k>ρQ(H).

這與H具有最大關(guān)聯(lián)Q-譜半徑相矛盾，因此

結(jié)論3|V1|=|V2|=…=|Vc|.

得到一個矛盾.則|Vc|≤|V1|.注意到

1≤|V1|≤|V2|≤…≤|Vc|，因此

|Vc|=|V1|且|V1|=|V2|=……=|Vc|.

如果|V1|≥2,設(shè)H3是由H通過刪除e1并且添加|V1|條邊生成的超圖，這里每條新邊包含V1中的一個點，V0中的任|V1|-1個點和F(V1),容易看出：

結(jié)論4設(shè)u∈Vi,i∈[c]且v∈e0，則xu

H6=H-ei+{{ei{uk}}∪{uj}}.

3 結(jié)論

對于連通k一致超圖，首先得出了n-r≥k+1時，具有最大關(guān)聯(lián)Q-譜半徑的唯一超圖；又得出了n-r=k時，具有最大關(guān)聯(lián)Q-譜半徑的唯一超圖；最后考慮了n-r≤k-1中的r=c(k-n+r)和r=c(k-n+r)+1兩種情況，分別得出了具有最大關(guān)聯(lián)Q-譜半徑的唯一超圖.