眼鏡圖的譜刻圖

吳廷增

（青海民族大學數學與統計學院，青海 西寧 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—），男，碩士，講師，主要從事代數圖論研究.

陶 理）