新的Q整图类

卢世芳

(青海大学基础部,青海西宁810016)

卢世芳

(青海大学基础部,青海西宁810016)

摘要：在他人研究整图,Laplace整图和Seidel-整图的基础上,刻画了Q整图新类.对图类的无符号拉普拉斯特征多项式进行研究分析,应用矩阵的初等变换,给出了图类是Q整图的充分必要条件,得到了新的Q整图类及其Q谱.

关键词：无符号拉普拉斯谱;无符号拉普拉斯特征多项式;Q整图

1　引言

本文中所提到的图都是有限、无向、简单图,没有给出定义的记号和术语参见文献[1-2].

设图G的顶点集为V(G),边集为E(G),A(G)=(aij)n×n是图G的(0,1)-邻接矩阵,即当ViVj∈E(G)时,aij=1;当ViVj/∈E(G)时,aij=0.矩阵

分别称为图G的Seidel矩阵、Laplace矩阵和无符号Laplace矩阵(或Q矩阵),其中D(G)是图G的顶点度矩阵.多项式

分别称为图G的Seidel矩阵、Laplace矩阵和Q矩阵的特征多项式[2].如果,一个图G的Seidel矩阵、Laplace矩阵和Q矩阵的特征值都是整数,则图G分别称作S-整图、Laplace整图和Q整图.设λ1,λ2,………,λs是图G的s个不同的无符号Laplace特征值,对应于它们的重数分别是为图G的无符号Laplace谱.

设Kn是n个顶点的完全图,是从Kn中删去互不相邻的条边所得的图类.

有关整图的研究源于上世纪70年代,文献[3-4]中对有少数点构成的所有整图进行了刻画.文献[5]中给出了关于整图的一些结果.文献[6]中作者给出了完全6-部图是Seidel-整图的一个充分必要条件.文献[7-10]中作者给出了关于Q整图的一些结果.关于Q整图新类的刻画,迄今为止不是很多,具有很好的研究前景.这篇文章将从讨论图类的无符号Laplace特征多项式入手,给出并证明图类是Q整图的充分必要条件,得到了新的Q整图类以及它们的Q谱.

定理2.1设图是具有n个顶点的完全图Kn中删去互不相邻的条边所得的图类.则图的无符号Laplace特征多项式为:

当且仅当方程

有整根,即当且仅当n2+4n+4−16t是一个完全平方数时,图类是Q整图.

证明图G的无符号Laplace特征多项式QG(λ)为:

利用行列式行的初等变换,得到

有整根.在n2+4n+4−16t和3(n−2)有相同的奇偶性的条件下,当且仅当n2+4n+4−16t是一个完全平方数时,方程有整根.

这里,当3(n−2)是偶数时,n是偶数.也是偶数.当3(n−2)是奇数时,n是奇数.也是奇数.

定理2.2设图G=是具有n个顶点的完全图Kn中删去互不相邻的条边所得的图类.

证明根据定理2.1得到图G的无符号Laplace特征多项式QG(λ)为:

推论2.1设图是具有n个顶点的完全图Kn中删去1条边所得的图类.则图类K−k2n它的无符号Laplace特征多项式为:

当n2+4n−12是平方数时,图是Q整图.

推论2.2设图是具有n个顶点的完全图Kn中删去互不相邻的2条边所得的图类.则图它的无符号Laplace特征多项式为:

当n2+4n−28是平方数时,图是Q整图.

参考文献

[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-整图的一个充分必要条件[J].纯粹数学与应用数学,2013,29(2):132-139.

[7]卢世芳.完全4-部图的无符号Laplacian整根[J].青海大学学报:自然科学版,2009,27(6):46-48,83.

[8]Lu Shifang,Zhao Haixing.Signless Laplacian characteristic polynomials of complete multipartite Graphs[J].数学季刊,2012,27(1):36-40.

[9]卢世芳,卫良,赵海兴.完全3-部图的无符号Laplacian谱[J].山东大学学报,2012(12):41-47.

[10]卢世芳.s=4的完全多部图Ka1n1,a2n2,………,asns的无符号Laplace特征多项式[J].价值工程,2012(7):12-13.

2010 MSC:05C78

中图分类号：O157.5

文献标识码：A

文章编号：1008-5513(2014)03-0229-05

DOI：10.3969/j.issn.1008-5513.2014.03.002

收稿日期：2013-12-01.

基金项目：教育部春晖计划项目(Z2012091);青海大学中青年科研基金(2011-QGY-8).

作者简介：卢世芳(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