趙寧,吳廷增

(青海民族大學數學與統(tǒng)計學院,青海西寧810007)

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

趙寧,吳廷增

(青海民族大學數學與統(tǒng)計學院,青海西寧810007)

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

Seidel多項式;Seidel譜;S-整圖;完全五部圖

1 引言

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

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

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

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

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

2 主要結果及其證明

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

引理2.1設G是完全五部圖Kn1,n2,··,n5,則G的Seidel多項式

其中

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

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

對SG(λ)施行變換:

i的取值依次為:

經過上述運算,得到

其中

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

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

進一步,對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,得到

對D1進一步化簡可得:

其中

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

將D2按第一列展開,得

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

定理2.2設G是完全五部圖Kn1,n2,··,n5,則G是S-整圖當且僅當的所有根是整數.

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

由定理2.2可推導出以下結果:

推論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設G是完全五部圖Km,n,n,n,n,那么

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

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

(ii)令

要使所有根都是整數,只需

的根是整數,由求根公式即可得證.

推論2.6設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 結束語

本文應用矩陣行初等變換,計算了完全五部圖G=Kn1,n2,··,n5的Seidel多項式,并給出了圖G是S-整圖的一個充分必要條件.并對當{n1,n2,···,n5}是由2個不同的正整數構成時,刻畫了對應的完全五部圖的整圖性問題.當n1,n2,n3,n4,n5是由3個或4個正整數構成時,對應的完全五部圖的整圖性問題的討論就顯得比較繁瑣,更簡便的辦法,值得繼續(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] 趙國鵬,王力工.完全多部圖的拉普拉斯特征多項式[J].紡織高?；A科學學報,2011,24(2):243-245.

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

[11] 譚尚旺.矩陣特征多項式的圖論計算公式[J].純粹數學與應用數學,2009,25(2):12-18.

[12] 王龍芹,橝江華,秦峰.圍長為r的n階本原有向圖的點指數[J].純粹數學與應用數學,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.

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

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

2010 MSC:05C78