定向超圖逆Perron值的若干上界

汪樂，徐靜

(安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230601)

近年來，超圖譜的研究引起了廣泛的關(guān)注,越來越多的學(xué)者通過張量(鄰接張量,拉普拉斯張量等)來研究超圖譜的性質(zhì)[1-4]。一個k階n維實張量A=(ai1i2…ik)是由nk個實元素ai1i2…ik組成,這里ij∈[n]([n]=1,2,…,n),j∈[k].超圖G=(V(G),E(G)),其中頂點集V(G)={v1,v2,…,vn},邊集E(G)={e1,e2,…,em},ej?V(G),?j∈[m].如果頂點v∈e(e∈E(G)),稱v和e是關(guān)聯(lián)的。若對任意的j∈[m]均有|ej|=k,稱G為k一致超圖。對于G中任意一點v∈V(G)d(v)=|{ej:v∈ej}|為頂點v的度,稱{d1,d2,…,dn}是G的度序列。對于G中任意兩點u,v∈V(G),從u到v的路定義為點與邊均不重復(fù)的交替序列v1,e1,v2,…,ed,vd+1其中v1=u,vd+1=v并且vi∈ei,vi+1∈ei,?i∈[d].若G的任意兩個頂點都有一條路連接, 則稱G是連通超圖。超圖G的k階n維鄰接張量A(G)[3]定義為A(G)=(ai1i2…ik)其中

設(shè)D(G)為k階n維度對角張量, 對角元素為dii…i=d(vi),?i∈[n]。

類似于超圖拉普拉斯張量,Gσ的拉普拉斯張量定義為L(Gσ)=D(Gσ)-A(Gσ),其中D(Gσ)是k階n維度對角張量。一般,對于一個n維實向量x∈Rn實數(shù)Axk和n維向量Axk-1的定義如下:

與定向超圖鄰接張量相類似, 根據(jù)定向超圖拉普拉斯張量的定義,容易得到

卜長江[7]等介紹了一致超圖的逆Perron值aj(G),通過aj(G)刻畫一致超圖的連通性。本文將逆Perron值aJ(G)推廣到定向超圖。定義定向超圖的逆Perron值aj(Gσ)如下:

1 主要結(jié)論

定理1.1設(shè)Gσ是有n個頂點和m條邊的定向超圖,{d1,d2,…,dn}是Gσ的度序列。對任意頂點j,我們有

證明對任意頂點j∈V(Gσ), 設(shè)向量x=(x1,x2,…,xn)T滿足

定理1.2設(shè)定向超圖Gσ有n個頂點和m條邊,{d1,d2,…,kn}是Gσ的度序列,則對任意的頂點j,我們有

我們有

aj(Gσ)≤L(Gσ)xk

通過均值不等式可以得到

我們?nèi)菀椎玫?/p>

定理1.3定向超圖Gσ有n個頂點和m條邊,則對Gσ中任意的頂點j∈V(Gσ),我們有

證明對于任意一個頂點j∈V(Gσ),設(shè)e0={j1,j2,…,jk}是Gσ中的一條邊并且j?e0,向量x=(x1,x2,…,xn)T滿足

aj(Gσ)≤L(Gσ)xk

2 結(jié)束語

定向超圖逆Perron值上界的刻畫有很多種，本文利用定向超圖的頂點數(shù)、邊數(shù)、度序列和逆Perron向量來刻畫，對于定向超圖的其他不變量, 如定向超圖的最大度、定向超圖的直徑等, 也可以利用本文的方法類似地刻畫定向超圖逆Perron值的上界。