完全五部圖的S-整圖性研究

趙寧,吳廷增

(青海民族大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,青海西寧810007)

完全五部圖的S-整圖性研究

趙寧,吳廷增

(青海民族大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,青海西寧810007)

應(yīng)用矩陣的初等變換得到了完全五部圖的Seidel多項(xiàng)式,并給出了完全五部圖是S-整圖的一個(gè)充分必要條件.進(jìn)一步刻畫了完全正則五部圖和兩類特殊完全五部圖的Seidel譜.

Seidel多項(xiàng)式;Seidel譜;S-整圖;完全五部圖

1 引言

本文涉及的圖都是簡(jiǎn)單圖,未定義的術(shù)語和符號(hào)見文獻(xiàn)[1].設(shè)G=(V(G),E(G))是n個(gè)頂點(diǎn)的圖.A(G)表示圖G的(0,1)-鄰接矩陣.稱S(G)=J?I?2A(G)是圖G的Seidel矩陣,其中J是全1-矩陣,I是單位矩陣.多項(xiàng)式SG(λ)=det(λI?S(G))稱為圖G的Seidel特征多項(xiàng)式(簡(jiǎn)記為Seidel多項(xiàng)式).由代數(shù)基本定理可知,SG(λ)=0至多有n個(gè)特征根.設(shè)λ1,λ2,···,λi是SG(λ)的i(1≤i≤n)個(gè)不同的特征根,且它們的重?cái)?shù)依次為k1,k2,···,ki,定義為圖G的Seidel 譜.

如果圖G的Seidel多項(xiàng)式的所有特征根都是整數(shù),則稱G是S-整圖.1974年,文獻(xiàn)[2]中首次提出了哪些圖是整圖,該問題的提出,引起了國(guó)內(nèi)外許多學(xué)者的關(guān)注,得到了許多重要的結(jié)論.2002年,文獻(xiàn)[3]給出了一個(gè)全面的綜述,并指出該問題的研究是非常困難的.近年來,一些關(guān)于圖其它形式的矩陣相對(duì)應(yīng)的整圖刻畫被研究,如:拉普拉斯矩陣、無符號(hào)拉普拉斯矩陣、Seidel矩陣等(參見文獻(xiàn)[4-12]).特別地,文獻(xiàn)[13]中構(gòu)造了整的完全四部圖,文獻(xiàn)[14]中給出了完全三部圖是整圖的充要條件.

令Kn1,n2,··,nt是完全t部圖,

這里Vi是非空且兩兩不相交的點(diǎn)集.為了方便,設(shè)|Vi|=ni(i=1,2,···,t).

如果n1=n2=···=nt=n,則稱為完全正則t部圖.文獻(xiàn)[3]對(duì)圖G的Seidel譜給出了一些初步結(jié)果,迄今關(guān)于S-整圖方面的研究不是很多.本文探討了完全多部圖是S-整圖的一些結(jié)果,證明了完全五部圖是S-整圖的一個(gè)充要條件,以及幾類特殊完全五部圖是整圖的優(yōu)美結(jié)果.

2 主要結(jié)果及其證明

為了證明后面的主要定理,給出下面的引理.

引理2.1設(shè)G是完全五部圖Kn1,n2,··,n5,則G的Seidel多項(xiàng)式

其中

證明設(shè)G是完全五部圖Kn1,n2,··,n5,由定義知,

其中Jni×nj是ni×nj(i?=j)階全1矩陣;Ani是主對(duì)角元素為λ,其余元素為?1的ni階方陣(i,j=1,2,···,5).

對(duì)SG(λ)施行變換:

i的取值依次為:

經(jīng)過上述運(yùn)算,得到

其中

其中Bni是ni階方陣(i=1,2,···,5),且

其中i,j=1,2,···,5,i?=j.

進(jìn)一步,對(duì)D施行如下變換:rn1+rn1?1+rn1?2+···+r1,rn1+n2+rn1+n2?1+rn1+n2?2+···+ rn1+1,···,rn1+n2+n3+n4+n5+rn1+n2+n3+n4+n5?1+rn1+n2+n3+n4+n5?2+···+rn1+n2+n3+n4+1,得到

對(duì)D1進(jìn)一步化簡(jiǎn)可得:

其中

對(duì)Di(i=3,4,5,6)施行變換:第一行乘以?1加到其余各行,然后將Di(i=3,4,5,6)按第i?3列展開,得到:

將D2按第一列展開,得

用計(jì)算Di(i=3,4,5,6)類似的方法計(jì)算并逐步回代,最終可得圖G的Seidel多項(xiàng)式為(1)式.

定理2.2設(shè)G是完全五部圖Kn1,n2,··,n5,則G是S-整圖當(dāng)且僅當(dāng)?shù)乃懈钦麛?shù).

證明由引理2.1知,完全五部圖G的Seidel多項(xiàng)式為(1)式.要使(1)的所有根是整數(shù),

由定理2.2可推導(dǎo)出以下結(jié)果:

推論2.3完全五部圖G=Kn,n,n,n,n是S-整圖,且

證明將(1)式中的ni(i=1,2,···,5)都替換為n,得到

顯然SG(λ)=0的根為(?1)6(n?1),(2n?1)5,(?4n?1)1,從而

推論2.4完全圖K5的Seidel譜Spec(K5)={14,(?4)1}.

證明取推論2.3中的n=1,便是完全圖K5.由(2)式得其譜Spec(K5)={14,(?4)1}.

推論2.5設(shè)G是完全五部圖Km,n,n,n,n,那么

(ii)G是S-整圖的充分必要條件是(2n+m)+16mn是整數(shù)且與m同為奇數(shù)或同為偶數(shù).

證明(i)由引理2.1,將Kn1,n2,··,n5中的n1,n2,n3,n4,n5用m,n,n,n,n替代,則相應(yīng)的完全五部圖Km,n,n,n,n的Seidel多項(xiàng)式為:

(ii)令

要使所有根都是整數(shù),只需

的根是整數(shù),由求根公式即可得證.

推論2.6設(shè)G是完全五部圖Km,m,n,n,n,那么

(i)SG(λ)=(λ+1)2m+3n?5[λ?(2n?1)]2[λ?(2m?1)][λ2+(n+2)λ+n?6mn+1];

證明(i)由引理2.1,將Kn1,n2,··,n5中的n1,n2,n3,n4,n5用m,m,n,n,n替代即可.

(ii)與推論2.5的(ii)式的證明類似.

3 結(jié)束語

本文應(yīng)用矩陣行初等變換,計(jì)算了完全五部圖G=Kn1,n2,··,n5的Seidel多項(xiàng)式,并給出了圖G是S-整圖的一個(gè)充分必要條件.并對(duì)當(dāng){n1,n2,···,n5}是由2個(gè)不同的正整數(shù)構(gòu)成時(shí),刻畫了對(duì)應(yīng)的完全五部圖的整圖性問題.當(dāng)n1,n2,n3,n4,n5是由3個(gè)或4個(gè)正整數(shù)構(gòu)成時(shí),對(duì)應(yīng)的完全五部圖的整圖性問題的討論就顯得比較繁瑣,更簡(jiǎn)便的辦法,值得繼續(xù)探討.

[1] Cvetkovi′c D,Doob M,Sachs H.Spectra of Graphs[M].New York:Academic press,1980.

[2] Harary F,Schwenk A J.Which graphs have integral[M]//Graphs and combinatorics.Berlin:Springer,1974.

[3] Bali′nska K T,Cvetkovi′c D,Radosavljevi′c Z,et al.A survey on integral graphs[J].Univ.Beograd.Publ. Elektrotehn.Fak.Ser.Mat.,2002,13:42-65.

[4] Lu Shifang,Zhao Haixing.Singless Laplacian characteristic polynomials of complete multipartite graphs[J]. Chinese Quarterly Journal of Mathematics,2012,27(1):36-40.

[5] Wang Ligong,Liu Xiaodong.Integral complete multipartite graphs[J].Discrete Math.,2008,308:3860-3870.

[6] Simi′c S K,Stanic Z.Q-integral graphs with edge-degrees at most fi ve[J].Discrete Math.,2008,308:4625-4634.

[7] Stani′c Z.Some results on Q-integral graphs[J].Ars Combin.,2009,90:321-335.

[8] Kirland S.Constructably laplacian integral graphs[J].Linear Algebra Appl.,2007,423:3-21.

[9] 趙國(guó)鵬,王力工.完全多部圖的拉普拉斯特征多項(xiàng)式[J].紡織高校基礎(chǔ)科學(xué)學(xué)報(bào),2011,24(2):243-245.

[10] 盧世芳,衛(wèi)良,趙海興.完全3-部圖的無符號(hào)Laplace譜[J].山東大學(xué)學(xué)報(bào):理學(xué)版,2012,47(12):41-47.

[11] 譚尚旺.矩陣特征多項(xiàng)式的圖論計(jì)算公式[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2009,25(2):12-18.

[12] 王龍芹,橝江華,秦峰.圍長(zhǎng)為r的n階本原有向圖的點(diǎn)指數(shù)[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2010,26(4):72-81.

[13] H′?c P,Pokom′y M.Integral complete 4-partite graphs[J].Discrete Math.,2008,308:3704-3705.

[14] H′?c P,Pokom′y M.New sufficient conditions for integral complete 3-partite graphs[J].Applicable Analysis and Discrete Mathematics,2008,2:276-284.

A study of S-integral graph of complete 5-partite graphs

Zhao Ning,Wu Tingzeng
(School of Mathematics and Statistics,Qinghai Nationalities University,Xining,Qinghai,810007,China)

By elementary transformation of a matrix,we compute the Seidel polynomial of complete 5-partite graph,and give a necessary and sufficient condition for a complete 5-partite graph to be an S-integral graph. Furthermore,we characterize the Seidel spectra of a complete regular 5-partite graph and two classes of complete 5-partite graphs with special structure,respectively.

Seidel polynomial,Seidel spectrum,S-integral graph,complete 5-partite graphs

O157.5

A

1008-5513(2014)05-0467-07

10.3969/j.issn.1008-5513.2014.05.005

2014-06-17.

青海省自然科學(xué)基金(2011Z911).

趙寧(1974-),碩士,副教授,研究方向：圖的譜理論.

2010 MSC:05C78