APP下载

眼镜图的谱刻图

2011-12-26吴廷增

关键词:邻接矩阵特征值顶点

吴廷增

(青海民族大学数学与统计学院,青海 西宁 810007)

眼镜图的谱刻图

吴廷增

(青海民族大学数学与统计学院,青海 西宁 810007)

只有与G同构的图才有相同的谱,则称图G是谱唯一确定的.眼镜图是在圈Cp和圈Cq的任意一个顶点之间加一条边构成的图,记为ɡ(p,q).证明了眼镜图是谱唯一确定的.

同谱图;图的谱;特征值

0 引言

在本文中如无特殊说明,我们仅考虑无环、无重边的无向简单图.未定义的符号和术语参见文献[1].对于任意的图G,V(G)={v1,v2,…,vn}表示其顶点集,E(G)表示其边集.对于任意的v∈V(G),用N(v)表示其邻集.用d(vi)表示顶点vi的度,并且用Δ表示图G中顶点的最大度.A(G)表示图G的邻接矩阵.多项式PA(G)(λ)=det(λI-A(G))是图G对应邻接矩阵的特征多项式,记作PA(G)(λ)=λn+a1λn-1+…+an.因为A(G)是实对称矩阵,所以它的特征根都是实数.假设λ1(G)≥λ2(G)≥…≥λn(G)是图G的特征值,那么所有的特征值及相应的重集分别称为图G的谱.其中λ1(G)称为图G的谱半径.

两个图是同谱的是指它们分享相同的谱.如果不存在非同构图H与图G有相同的谱,则称图G是谱唯一确定的.Cn和Pn分别表示n个顶点的圈和路.假设Cp和Cq是两个顶点不交的圈.令v1是Cp的顶点及vl是Cq的顶点.在顶点v1和vl之间插入一条长为l-1的路v1v2…vl,结果图记作ɡ(p,l,q),称为ɡ-图,见图1,这里l>1.在图ɡ(p,l,q)中,特别当l=2时,称其为眼镜图,记作ɡ(p,q),见图2.假设Pr+1,Ps+1和Pt+1是三条不交路,这里r,s,t≥1且它们中至多只有一个等于1.分别将三条路的首尾粘接起来所得的图记为θ(r,s,t),称为θ-图,见图3.

图1 ɡ-图

图2 眼镜图

图3 θ-图

研究图的谱唯一确定性是一个古老而又有趣的问题,迄今为止,仅有很小的一部分图是谱唯一确定的[2-7],应用背景及更详细的内容参见文献[8].在本文中,将证明眼镜图是谱唯一确定的.

1 预备知识

2 ɡ(p,q)是内部不同谱的

3 ɡ(p,q)与ɡ(r,s,t)(s≥1)是不同谱的

4 主要结果

如果ɡ(p,q)图有两个4-圈,所以有8个顶点,而8个顶点的θ(r,s,t)图只能含有一个4-圈.

定理如果ɡ(p,q)图不含唯一的4-圈,则图ɡ(p,q)是谱唯一确定的.

证明由引理3—8和推论1可直接获得该结果.

我们虽然证明了ɡ(p,q)的谱唯一确定性,但是图ɡ(r,s,t)是否谱唯一确定仍是一个非常困难的问题,还需要有新的方法才能刻画.

[1] CVETKOVIC'D M,DOOB M,SACHS H.Spectra of graphs[M].New York:Academic Press,1980:2-35.

[2] DOOB M,HAEMERS W H.The complement of the path is determined by its spectrum[J].Linear Algebra Appl,2002(356):57-65.

[3] HAEMERS W H,LIU XIAOGANG,ZHANG YUANPING.Spectral characterizations of lollipop graphs[J].Linear Algebra Appl,2008(428):2415-2423.

[4] WU TINGZENG,HU SHENGBIAO.Some edges-deleted subgraphs of complete graph are determined by their spetrum[J].Mathematical Research & Exposition,2010(30):833-840.

[5] RAMEZANI F,BROOJERDIAN N,TAYFEH-REZAIE B.A note on the spectral characterization ofθ-graphs[J].Linear Algebra Appl,2009(431):626-632.

[6] SHEN XIAOLING,HOU YAOPING,ZHANG YUANPING.GraphZnand some graphs related toZnare determined by their spectrum[J].Linear Algebra Appl,2005(404):58-68.

[7] WANG WEI,XU CHENGXIAN.On the spactral characterization ofT-shape trees[J].Linear Algebra Appl,2006(414):492-501.

[8] VAN DAM E R,HAEMERS W H.Which graph are determined by their spectrum?[J].Linear Algebra Appl,2003(373):241-272.

On the spectral characterization ofG-graph

WU Ting-zeng

(School of Mathematics and Statistics,Qinghai Nationalities University,Xining 810007,China)

A graphGis said to be determined by its spectrum if any graph having the same spectrum asGis isomorphic toG.A glasses graph is bicyclic graph obtained from two cyclesCpandCqadding a edge between a vertex ofCpandCq,respectively.denoted byɡ(p,q).It is proved in this paper that theɡ(p,q)is determined by its spectrum.

cospectral graph;spectra of graph;eigenvalues

O 157.5

110·7470

A

1000-1832(2011)03-0010-04

2009-11-04

国家自然科学基金资助项目(10861009);国家民委基金资助项目(10QH01).

吴廷增(1978—),男,硕士,讲师,主要从事代数图论研究.

陶 理)

猜你喜欢

邻接矩阵特征值顶点
轮图的平衡性
一类内部具有不连续性的不定Strum-Liouville算子的非实特征值问题
过非等腰锐角三角形顶点和垂心的圆的性质及应用(下)
过非等腰锐角三角形顶点和垂心的圆的性质及应用(上)
一类带强制位势的p-Laplace特征值问题
单圈图关联矩阵的特征值
基于邻接矩阵变型的K分网络社团算法
基于商奇异值分解的一类二次特征值反问题
基于子模性质的基因表达谱特征基因提取
数学问答