完全六部圖是S-整圖的一個充要條件

趙寧,吳廷增,郭承志

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

完全六部圖是S-整圖的一個充要條件

趙寧,吳廷增,郭承志

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

在他人研究完全多部圖的鄰接譜的基礎上,對整完全多部圖的Seidel多項式進行研究分析,以期得到完全六部圖G是S-整圖的充要條件.從討論完全六部圖的Seidel多項式入手,應用矩陣行初等變換的方法給出完全六部圖G是S-整圖的充要條件.

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

1 引言

本文僅考慮有限,無向的簡單圖,未定義的術語和符號參見文獻[1].令圖G表示n個頂點的簡單圖,設V(G),E(G)分別是圖G的頂點集和邊集.用A(G)表示圖G的鄰接矩陣,定義

稱作是圖G的Seidel譜.

如果一個圖的Seidel多項式的所有特征根都是整數,則稱此圖是S-整圖.有關整圖的研究源于上世紀70年代[2].文獻[3-4]中,對由少數點構成的所有整圖進行了刻畫;文獻[5-6]作者給出了關于拉普拉斯整圖的一些優美結果.但關于S-整圖方面的研究迄今不是很多.

這里Vi是非空的兩兩不相交的點集.|Vi|=ni(i=1,2,…,t).文獻[7]研究了完全多部圖Ka1.p1,a2.p2,…,as.ps的鄰接譜,并就此提出了一些整完全多部圖.本文將從討論完全六部圖的Seidel多項式入手,給出并證明完全六部圖G是S-整圖的充要條件.

2 主要結果及其證明

下面利用矩陣的一些性質,通過刻畫完全六部圖的Seidel譜給出S-整圖的一個充要條件.首先介紹所需引理.

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

將D3按第一列展開,得到類似于D2的展開式,重復上述計算D2的方法得到D3.逐步回代,最終可得圖G的Seidel多項式為(1)式.

定理2.1設G是完全六部圖Kn1,n2,…,n6,它的Seidel多項式為(1)式,那么圖G是S-整圖的充要條件是

的所有根是整數.

證明由引理知,完全六部圖G的Seidel多項式為(1)式.要使(1)式的所有根是整數,顯然必須而且只須

的所有根是整數.根據定理2.1,不難有以下結果:

推論2.1完全六部圖Kn,n,n,n,n,n是S-整圖,它的譜

3 結束語

本文應用矩陣行初等變換,刻畫了完全六部圖G=Kn1,n2,…,n6的Seidel多項式,并給出了G是S-整圖的一個充分必要條件.當{n1,n2,…,n6}是由一個整數或兩個不同的整數構成時,我們得到了完全六部圖Kn1,n2,…,n6是S-整圖的充分必要條件.當在{n1,n2,…,n6}中出現兩個以上不同的整數時,情況就變得比較復雜和繁瑣,是今后可以繼續考慮討論的問題.

參考文獻

[1]Bondy J A,Murty U S R.Graph Theory with Applications[M].New York:The Macmillan Press LTD,1976.

[2]Harary F,Schwenk A J.Which Graphs have Integral[C]//Barir,Harary F.Graphs and Combinatorics. Berlin:Springer,1974.

[3]Balinska K T,Kupczyk M,Simic S K,et al.On Generating all Integral Graphs on 11 Vertices[R]//Computer Science Center Report.Poznan:The Technical University of Poznan,2001.

[4]Balinska K T,Cvetkovic D,Radosavljevic Z,et al.A survey on integral graphs[J].Univ.Beograd.Publ. Elektrotehn.Fak.(Sermat),2002,13:42-65.

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

[6]王龍芹,橝江華,秦峰,等.圍長為r的n階本原有向圖的點指數[J].純粹數學與應用數學,2010,26(4):72-81.

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

The necessary and sufficient condition for the complete 6-partite graphs to be S-integral

Zhao Ning,Wu Tingzeng,Guo Chengzhi
(Department of Mathematics and Statistics,Qinghai Nationalities University,Xining810007,China)

Based on the results of Laplacian spectrum of a graph for the complete multipartite graph,we give the necessary and sufficient condition for the complete 6-partite graphs G to be S-integral.Using the elementary row transformation of a matrix and the Seidel polynomial of the complete 6-partite graphs.

Seidel polynomial,S-integral graph,complete 6-partite graphs

O157.5

A

1008-5513(2013)02-0132-08

10.3969/j.issn.1008-5513.2013.02.004

2012-11-15.

教育部“春暉計劃”(Z2011014);青海省自然科學基金(2011-Z-911).

趙寧(1974-),高級講師,研究方向：圖的譜理論.

2010 MSC:05C78