卢世芳
(青海大学基础部,青海西宁810016)
卢世芳
(青海大学基础部,青海西宁810016)
摘要:在他人研究整图,Laplace整图和Seidel-整图的基础上,刻画了Q整图新类.对图类的无符号拉普拉斯特征多项式进行研究分析,应用矩阵的初等变换,给出了图类是Q整图的充分必要条件,得到了新的Q整图类及其Q谱.
关键词:无符号拉普拉斯谱;无符号拉普拉斯特征多项式;Q整图
本文中所提到的图都是有限、无向、简单图,没有给出定义的记号和术语参见文献[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 graphsto 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