眼镜图的谱刻图

吴廷增

（青海民族大学数学与统计学院，青海 西宁 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—），男，硕士，讲师，主要从事代数图论研究.

陶 理）