盧世芳

(青海大學(xué)基礎(chǔ)部,青海西寧810016)

盧世芳

(青海大學(xué)基礎(chǔ)部,青海西寧810016)

摘要：在他人研究整圖,Laplace整圖和Seidel-整圖的基礎(chǔ)上,刻畫(huà)了Q整圖新類(lèi).對(duì)圖類(lèi)?的無(wú)符號(hào)拉普拉斯特征多項(xiàng)式進(jìn)行研究分析,應(yīng)用矩陣的初等變換,給出了圖類(lèi)?是Q整圖的充分必要條件,得到了新的Q整圖類(lèi)?及其Q譜.

關(guān)鍵詞：無(wú)符號(hào)拉普拉斯譜;無(wú)符號(hào)拉普拉斯特征多項(xiàng)式;Q整圖

1　引言

本文中所提到的圖都是有限、無(wú)向、簡(jiǎn)單圖,沒(méi)有給出定義的記號(hào)和術(shù)語(yǔ)參見(jiàn)文獻(xiàn)[1-2].

設(shè)圖G的頂點(diǎn)集為V(G),邊集為E(G),A(G)=(aij)n×n是圖G的(0,1)-鄰接矩陣,即當(dāng)ViVj∈E(G)時(shí),aij=1;當(dāng)ViVj/∈E(G)時(shí),aij=0.矩陣

分別稱為圖G的Seidel矩陣、Laplace矩陣和無(wú)符號(hào)Laplace矩陣(或Q矩陣),其中D(G)是圖G的頂點(diǎn)度矩陣.多項(xiàng)式

分別稱為圖G的Seidel矩陣、Laplace矩陣和Q矩陣的特征多項(xiàng)式[2].如果,一個(gè)圖G的Seidel矩陣、Laplace矩陣和Q矩陣的特征值都是整數(shù),則圖G分別稱作S-整圖、Laplace整圖和Q整圖.設(shè)λ1,λ2,………,λs是圖G的s個(gè)不同的無(wú)符號(hào)Laplace特征值,對(duì)應(yīng)于它們的重?cái)?shù)分別是為圖G的無(wú)符號(hào)Laplace譜.

設(shè)Kn是n個(gè)頂點(diǎn)的完全圖,是從Kn中刪去互不相鄰的條邊所得的圖類(lèi).

有關(guān)整圖的研究源于上世紀(jì)70年代,文獻(xiàn)[3-4]中對(duì)有少數(shù)點(diǎn)構(gòu)成的所有整圖進(jìn)行了刻畫(huà).文獻(xiàn)[5]中給出了關(guān)于整圖的一些結(jié)果.文獻(xiàn)[6]中作者給出了完全6-部圖是Seidel-整圖的一個(gè)充分必要條件.文獻(xiàn)[7-10]中作者給出了關(guān)于Q整圖的一些結(jié)果.關(guān)于Q整圖新類(lèi)的刻畫(huà),迄今為止不是很多,具有很好的研究前景.這篇文章將從討論圖類(lèi)的無(wú)符號(hào)Laplace特征多項(xiàng)式入手,給出并證明圖類(lèi)是Q整圖的充分必要條件,得到了新的Q整圖類(lèi)以及它們的Q譜.

定理2.1設(shè)圖是具有n個(gè)頂點(diǎn)的完全圖Kn中刪去互不相鄰的條邊所得的圖類(lèi).則圖的無(wú)符號(hào)Laplace特征多項(xiàng)式為:

當(dāng)且僅當(dāng)方程

有整根,即當(dāng)且僅當(dāng)n2+4n+4?16t是一個(gè)完全平方數(shù)時(shí),圖類(lèi)是Q整圖.

證明圖G的無(wú)符號(hào)Laplace特征多項(xiàng)式QG(λ)為:

利用行列式行的初等變換,得到

有整根.在n2+4n+4?16t和3(n?2)有相同的奇偶性的條件下,當(dāng)且僅當(dāng)n2+4n+4?16t是一個(gè)完全平方數(shù)時(shí),方程有整根.

這里,當(dāng)3(n?2)是偶數(shù)時(shí),n是偶數(shù).也是偶數(shù).當(dāng)3(n?2)是奇數(shù)時(shí),n是奇數(shù).也是奇數(shù).

定理2.2設(shè)圖G=是具有n個(gè)頂點(diǎn)的完全圖Kn中刪去互不相鄰的條邊所得的圖類(lèi).

證明根據(jù)定理2.1得到圖G的無(wú)符號(hào)Laplace特征多項(xiàng)式QG(λ)為:

推論2.1設(shè)圖是具有n個(gè)頂點(diǎn)的完全圖Kn中刪去1條邊所得的圖類(lèi).則圖類(lèi)K?k2n它的無(wú)符號(hào)Laplace特征多項(xiàng)式為:

當(dāng)n2+4n?12是平方數(shù)時(shí),圖是Q整圖.

推論2.2設(shè)圖是具有n個(gè)頂點(diǎn)的完全圖Kn中刪去互不相鄰的2條邊所得的圖類(lèi).則圖它的無(wú)符號(hào)Laplace特征多項(xiàng)式為:

當(dāng)n2+4n?28是平方數(shù)時(shí),圖是Q整圖.

參考文獻(xiàn)

[1]Bondy J,Murty U S R.Graph Theory with Applications[M].New Youk:North-Holland,1976.

[2]Cvetovi′c D,Doob M,Sachs H.Spectra of Graphs Theory and Application[M].New York:Academic press, 1980.

[3]Harary F,Schwenk A J.Which graphs have integral[C]//Bari,Harary F.Graphs and Combinatorics.Berlin: Springer,1974.

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

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

[6]趙寧,吳廷增,郭承志.完全6-部圖是S-整圖的一個(gè)充分必要條件[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2013,29(2):132-139.

[7]盧世芳.完全4-部圖的無(wú)符號(hào)Laplacian整根[J].青海大學(xué)學(xué)報(bào):自然科學(xué)版,2009,27(6):46-48,83.

[8]Lu Shifang,Zhao Haixing.Signless Laplacian characteristic polynomials of complete multipartite Graphs[J].數(shù)學(xué)季刊,2012,27(1):36-40.

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

[10]盧世芳.s=4的完全多部圖Ka1n1,a2n2,………,asns的無(wú)符號(hào)Laplace特征多項(xiàng)式[J].價(jià)值工程,2012(7):12-13.

2010 MSC:05C78

中圖分類(lèi)號(hào)：O157.5

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1008-5513(2014)03-0229-05

DOI：10.3969/j.issn.1008-5513.2014.03.002

收稿日期：2013-12-01.

基金項(xiàng)目：教育部春暉計(jì)劃項(xiàng)目(Z2012091);青海大學(xué)中青年科研基金(2011-QGY-8).

作者簡(jiǎn)介：盧世芳(1970-),碩士,副教授,研究方向：圖論.

Some new families of Q-integral graphs

Lu Shifang
(Department of Basic Research,Qinghai University,Xining810016,China)

Abstract:Based on the results of integral graphs,L-integral graphs and S-integral graphs.Characterized some new families of Q-integral graphs.We fi rstly give the necessary and sufficient condition for the graphs?to be Q-integral.Using the elementary row transformation of a matrix and the signless Laplace characteristic polynomial of the graphs?.Furthemore,we obtain large families of Q-integral graphs and their spectra.

Key words:signless Laplace spectra,signless Laplace characteristic polynomial,Q-integral polynomials