一致超圖譜半徑界的改進(jìn)結(jié)果

鄢仁政,李薇

一致超圖譜半徑界的改進(jìn)結(jié)果

鄢仁政1,李薇2

(1.福建江夏學(xué)院數(shù)理教研部,福建福州350108;2.福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院,福建福州350002)

利用張量理論研究一致超圖的譜半徑.首先,利用對角相似張量與原張量同譜的性質(zhì),結(jié)合張量特征值的圓盤定理,給出譜半徑的上界,這一上界嚴(yán)格小于最大度;其次,通過超圖的度向量給出譜半徑的下界.改進(jìn)了超圖譜半徑上下界的原有結(jié)果.

一致超圖;張量;譜半徑;界

1 引言及預(yù)備知識

設(shè)超圖H=(V,E),其中V={1,2,···,n}是頂點(diǎn)集,E={e1,e2,···,em}是邊集.本文所考慮的均為k一致超圖,即對任意的i=1,···,m都有|ei|=k.k一致超圖也簡稱為k-超圖,若k取2,2-超圖通常稱為圖.顯然,超圖是圖的推廣,且在多個(gè)領(lǐng)域有著重要應(yīng)用[1].圖可自然地用矩陣表示,如鄰接矩陣、Laplacian矩陣和signless Laplacian矩陣等,基于這些矩陣的圖的研究,即圖譜理論,一直是圖論的研究熱點(diǎn).但超圖的一條邊關(guān)聯(lián)k個(gè)頂點(diǎn),矩陣無法完整的體現(xiàn)這些信息.Lim[2]最早提出利用張量表示超圖,通過張量研究超圖的性質(zhì).Cooper和Dutle[3]將這項(xiàng)工作具體化,定義了超圖的鄰接張量A,并利用其H-特征值研究超圖的性質(zhì),將圖譜理論的一些結(jié)果自然地推廣到超圖上.這項(xiàng)工作引發(fā)了利用張量研究超圖的興趣,超圖的譜理論也成為圖論中的一個(gè)新的研究熱點(diǎn)[4-5].

利用張量研究超圖[6-7]的工作中,最主要的就是關(guān)于張量特征值及其與超圖拓?fù)浣Y(jié)構(gòu)關(guān)系的研究,而在所有的特征值中,最大特征值無疑是最重要的.超圖鄰接張量的最大H-特征值,是這兩年超圖譜理論的主要研究對象之一.由于鄰接張量是非負(fù)的實(shí)張量,根據(jù)非負(fù)張量的性質(zhì)可知鄰接張量的模最大的特征值為實(shí)數(shù),該值也稱為超圖的譜半徑,記為λ1(A).文獻(xiàn)[3]確定了λ1(A)的取值范圍:ˉd≤λ1(A)≤△,這里的ˉd與△分別表示超圖的平均度與最大度.本文的主要工作是改進(jìn)了上述結(jié)果,得到譜半徑新的上下界,并用實(shí)例比較本文的結(jié)果與文獻(xiàn)[3]的結(jié)果.定理2.3在k取2時(shí)與圖譜理論中的經(jīng)典結(jié)論一致,因此可視為該結(jié)論在超圖的推廣.文中未說明的術(shù)語和記號可參考文獻(xiàn)[8].

定義1.1對k階n維的張量T=(ti1...ik),向量x∈Rn,Txk表示一個(gè)數(shù),定義為:

Txk?1是Rn中的一個(gè)向量,其第i個(gè)分量定義為:

定義1.2[2,9]設(shè)T是k階n維的張量,若?λ∈R,x∈Rn{0},?i=1,···,n滿足:

則稱λ是T的H-特征值,x是λ對應(yīng)的H-特征向量.

設(shè)k-超圖H的頂點(diǎn)數(shù)為n,其鄰接張量A(H)=(ai1i2··ik)的元素定義為:

顯然,A(H)是k階n維的實(shí)對稱張量.

引理1.1[10]設(shè)T=(ti1...ik)是k階n維的張量,P=diag(p1,···,pn)是n×n的對角陣且可逆,則P?(k?1)TP也是一個(gè)k階n維的張量,記為T′,其分量滿足:

稱T′與T對角相似,且T′與T是同譜的,即兩個(gè)張量具有相同的特征值,且重?cái)?shù)也相同.

引理1.2[10]設(shè)k-超圖H的頂點(diǎn)集為V={1,2,···,n},對應(yīng)的鄰接張量為A(H),將其頂點(diǎn)重新標(biāo)號,記為V={1′,2′,···,n′},其對應(yīng)的鄰接張量記為A′(H),則A(H)與A′(H)同譜.

張量特征值也有類似矩陣特征值的圓盤定理,這是文獻(xiàn)[9]首先提到的.

引理1.3[9]設(shè)T=(ti1··ik)是k階n維的張量,λ(T)是T的特征值,則λ(T)包含于下述n個(gè)圓盤的并之中:

2 主要結(jié)論

定理2.1設(shè)H是n個(gè)頂點(diǎn)的k-超圖,最大度為△1,次大度為△2,若H的每一條邊均含有度不等于△1的頂點(diǎn),則H的譜半徑滿足:

證明設(shè)H中度為△1的頂點(diǎn)數(shù)為s,將H的頂點(diǎn)重新標(biāo)號,使得其對應(yīng)的頂點(diǎn)度數(shù)滿足△1=d1=d2=···=ds>△2=ds+1≥···≥dn.由引理1.2,重新標(biāo)號不改變超圖的譜,因此可將新的鄰接張量仍記為A.

設(shè)P=diag(p1,···,pn)是n×n的對角陣,其中p1=···=ps=x,ps+1=···=pn=1,令x>1,則P可逆.記B=P?(k?1)AP,由引理1.1,λ1(B)=λ1(A).下面考慮λ1(B).

不難驗(yàn)證B的對角元均為0,計(jì)算B的n個(gè)圓盤的范圍如下:

若1≤i≤s,pi=x,由已知,含頂點(diǎn)i的邊至少含有一個(gè)度不為△1的頂點(diǎn),記為j,則pj=1,因此圓盤Zi內(nèi)的點(diǎn)滿足:

若s+1≤i≤n,pi=1,則圓盤Zi內(nèi)的點(diǎn)滿足:

由引理1.3,因此有,

再由λ1(B)=λ1(A),可知定理成立.

定理2.2設(shè)H是n個(gè)頂點(diǎn)的k-超圖,最大度為△1,次大度為△2,若H中每個(gè)度為△1的頂點(diǎn)都有至少一個(gè)鄰點(diǎn)的度不為△1,則H的譜半徑滿足:

證明設(shè)張量A、B,矩陣P的含義與定理2.1相同.

計(jì)算B的n個(gè)圓盤的范圍如下:

若1≤i≤s,pi=x,由已知,頂點(diǎn)i的鄰點(diǎn)中至少有一個(gè)度不等于△1,記為j,則pj=1,因此圓盤Zi內(nèi)的點(diǎn)滿足:

若s+1≤i≤n,pi=1,則圓盤Zi內(nèi)的點(diǎn)滿足:

因此有,

聯(lián)立方程:

定理成立.

定理2.2的條件是要求超圖不含這樣的頂點(diǎn),它的度以及與它相鄰的所有頂點(diǎn)的度均為最大度,顯然大部分的超圖都滿足該條件,而從結(jié)論可以看出此時(shí)λ1(A)<△1恒成立.

引理2.1[11]設(shè)T是k階n維的實(shí)對稱非負(fù)張量,則T的譜半徑滿足:

定理2.3設(shè)H是n個(gè)頂點(diǎn)的k-超圖,邊集E滿足|E|=m,則H的譜半徑滿足:

且當(dāng)H正則時(shí)等號成立.

證明令其中容易驗(yàn)證

因此由引理2.1,得

若H是r正則超圖,則

等號成立.

注2.1當(dāng)k=2時(shí),定理2.3與圖的譜半徑如下經(jīng)典結(jié)論[12]一致:

下面舉例說明上述三個(gè)定理對原有結(jié)果的改進(jìn).

例2.1設(shè)超圖H1=(V1,E1),頂點(diǎn)集V1={1,2,···,6},邊集E1={e1,e2,e3,e4},其中e1={1,2,6},e2={4,5,6},e3={1,2,3},e4={1,3,6}.容易看出d1=d6=3, d2=d3=2,d4=d5=1,因此△1=3,△2=2,dˉ=2.因?yàn)槊織l邊都有度不為3的頂點(diǎn),所以

由定理2.1,可得λ1(A)≤≈2.621<△1,再由定理2.3,可得λ1(A)≥2.243>.即原有結(jié)果λ1(A)∈[2,3]位于長為1的區(qū)間內(nèi),本文結(jié)論λ1(A)∈[2.243,2.621]位于長為0.378的區(qū)間內(nèi).

例2.2設(shè)超圖H2=(V2,E2),頂點(diǎn)集V2={1,2,···,8},邊集E2=E1∪{e5},其中E1定義與例2.1相同,e5={2,7,8}.容易看出

因此△1=3,△2=2,=1.875.因?yàn)槿〉阶畲蠖?的頂點(diǎn)都有度不為3的鄰點(diǎn),所以由定理2.2,可得λ1(A)≤max{2.874,2.621}=2.874<△1,再由定理2.3可得,λ1(A)≥2.225>.即原有結(jié)果λ1(A)∈[1.875,3]位于長為1.125的區(qū)間內(nèi),本文結(jié)論λ1(A)∈[2.225,2.874]位于長為0.649的區(qū)間內(nèi).

參考文獻(xiàn)

[1]Furedi Z.Matchings and covers in hypergraphs[J].Graphs and Combinatorics,1988,4(1):115-206.

[2]Lim L H.Singular values and eigenvalues of tensors:a variational approach[J].Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing,2005,1:129-132.

[3]Cooper J,Dutle A.Spectra of uniform hypergraphs[J].Linear Algebra Appl.,2012,436(9):3268-3292.

[4]Pearson K,Zhang T.Eigenvalues on the adjacency tensor of products of hypergraphs[J].Int.J.Contemp. Math.Sciences,2013,8(4):151-158.

[5]Xie J,Chang A.A new type of Laplacian tensor and its Z-eigenvalues of an even uniform hypergraph[J]. Int.J.Appl.Math.Stat.,2013,31(1):9-19.

[6]鄭國彪.D-完全一致混合超圖不可著色的一個(gè)充要條件[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2011,27(3):308-312.

[7]鄭國彪.關(guān)于D-完全一致混合超圖上色數(shù)的一個(gè)結(jié)論的推廣[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2012,28(3):294-302.

[8]貝爾熱C.超圖[M].南京:東南大學(xué)出版社,2002.

[9]Qi L.Eigenvalues of a real supersymmetric tensor[J].J.Symb.Comput.,2005,40(6):1302-1324.

[10]Shao J Y.A general product of tensors with applications[J].Linear Algebra Appl.,2013,439(8):2350-2366.

[11]Qi L.Symmetric nonnegative tensors and copositive tensors[J].Linear Algebra Appl.,2013,439(1):228-238.

[12]Bapat R B.Graphs and Matrices[M].London:Springer,2010.

New bounds for spectral radius of uniform hypergraphs

Yan Renzheng1,Li Wei2
(1.Department of Mathematics and Physics,Fujian Jiangxia University,Fuzhou350108,China; 2.College of Computer and Information Technology,Fujian Agriculture and Forestry University, Fuzhou350002,China)

In this paper,the spectral radius of a uniform hypergraph is studied according to properties of tensors.Firstly,based on Gerschgorin′s theorem and the property that two diagonal similar tensors have the same spectrum,an upper bound for the spectral radius is given.This bound is strictly less than the maximum degree of the hypergraph.Secondly,a lower bound for the spectral radius is introduced by using the degree vector of the hypergraph.These bounds are improvements of the original results.

uniform hypergraph,tensor,spectral radius,bound

O157.5

A

1008-5513(2014)06-0581-06

10.3969/j.issn.1008-5513.2014.06.006

2014-05-05.

福建省中青年教師教育科研項(xiàng)目(JB13194);福建江夏學(xué)院青年科研人才培育基金(JXZ2014007).

鄢仁政(1980-),碩士,講師,研究方向：圖論及其應(yīng)用.

李薇(1982-),博士生,講師,研究方向：圖論及其應(yīng)用.

2010 MSC:05C65