關于圖Gp，q，sa，b，c的一個重要結(jié)論*

李 丹，蘇 宇，張力丹，王國平

關于圖Gp，q，sa，b，c的一個重要結(jié)論*

李 丹，蘇 宇，張力丹，王國平

（新疆師范大學數(shù)學科學學院，新疆烏魯木齊830054）

讓Gp，q，sa，b，c表示階為n的由三個lollipop圖通過一個公共點連接的圖.首先確定了φ（Pn，－2）的值，其次得到了2是圖Gp，q，sa，b，c的特征值的充要條件.

譜；路；圈

1 基礎知識

在這篇文章中，我們只考慮簡單無向圖.設G是階為n的圖，A（G）表示其鄰接矩陣.因為A（G）是實對稱矩陣，所以它的所有特征值均為實數(shù).我們分別用φ（G）＝φ（G，λ）表示圖G的A－特征多項式，SpecA（G）＝｛λ1（G），λ2（G），…，λn（G）｝（非增序列）表示圖G的A－譜.通常，用Cn和Pn分別表示n階圈和路.lollipop圖是將圈Cp連接在路Pn－p＋1的一個懸掛點上得到的圖，用Hp，n－p表示.θ－圖是由三條具有公共端點的內(nèi)部兩兩不交的路Pa，Pb，Pc得到的圖，用θa，b，c（a≤b≤c）表示.Dumbbell圖是在路Pc＋3（c≥－1）的兩個端點連接兩個內(nèi)部不交的圈Ca，Cb，用Da，b，c表示.文獻［1］和［2］刻畫了lollipop圖譜；［3］刻畫了θ－圖譜；［4］刻畫了Dumbbell－圖譜.設Gp，q，sa，b，c表示具有公共端點的三個內(nèi)部兩兩不交的lollipop圖（見圖1）.

圖1 Gp，q，sa，b，c的結(jié)構

本文首先證明了φ（Pn，－2）的值；其次確定了2∈ Spec（G）當且僅當（a，b，c）∈Ω＝｛（2，3，6），（2，4，4），（3，3，3），（0，0，c）（c≥0）｝.

2 主要結(jié)論

本節(jié)中，我們將給出主要結(jié)論.

引理2.1［5］設G是一個簡單圖.～Cv（～Ce）表示圖G中包含點v（邊e＝uv）的所有圈的集合.那么：

（2）φ（G，λ）＝φ（G－e，λ）－φ（G－u－v，λ）－

定理2.2 設Pn是n階路.那么：

證明由引理2.1，有

如果λ＝－2，那么

因為φ（Pn－1，－2）＝－2φ（Pn－2，－2）－φ（Pn－3，－2），進而可以得到φ（Pn，－2）＝3φ（Pn－2，－2）＋2φ（Pn－3，－2）.

按照這種步驟很容易有：當n為偶數(shù)時，φ（Pn，－2）＝（n－1）φ（P2，－2）＋（n－2）φ（P1，－2）＝n＋1；當n為奇數(shù)時，φ（Pn，－2）＝－（（n－1）φ（P2，－2）＋（n－2）φ（P1，－2）＝n＋1）＝－n－1.

引理2.3（交錯定理）［6］設A是n×n的對稱矩陣，其特征值為λ1，λ2，…，λn.B是A的一個m×m主子式，其特征值為λ*1，λ*2，…，λ*m.那么λi≥λ*i≥λn－m＋i（i＝1，2，…，m）.

引理2.4［7］Pn，Ta，b，c，θa，b，c和Hg，p分別表示路，T－型樹，θ－圖和lollipop圖.那么：

（1）φ（Pn，2）＝n＋1；φ（Ta，b，c，2）＝a＋b＋c＋2－abc；φ（Qa，b，c，2）＝4a＋4b＋4c－4ac－2bc－2ab＋abc，其中Qa，b，c是恰有兩個三度點的樹；

（2）φ（θa，b，c，2）＝ijk－（ij＋ik＋jk）－3（j＋i＋k）－5；

（3）φ（Hg，p，2）＝－gp；

（4）φ（Da，b，c，2）＝abc，并且2∈Spec（Da，b，c）當且僅當c＝0，2是單根.

定理2.5 設3≤p≤q≤s，0≤a≤b≤c，那么2∈Spec（Gp，q，sa，b，c）當且僅當（a，b，c）∈Ω＝｛（2，3，6），（2，4，4），（3，3，3），（0，0，c）（c≥0）｝.

此外，當（a，b，c）∈Ω／（0，0，0）時，2是單根；當（a，b，c）＝（0，0，0）時，2是二重根.

證明由引理2.1可以得到φ（Gp，q，sa，b，c）＝φ（Hp，a）φ（Dq，s，b＋c）－φ（Hp，a－1）φ（Hq，b）φ（Hs，c），

進而通過引理2.4又有

因此2∈Spec（Gp，q，sa，b，c）當且僅當abc－ab－ac－bc＝0.解這個等式可以得到

這隱含著c是關于a和b嚴格遞增的.所以當c≥b≥a≥4時，c在b＝a＝4是取得最大值，且由（2）可以直接得到，但這和c≥4是矛盾的.所以2?Spec（Gp，q，sa，b，c）.

接下來，只需要考慮0≤a≤3的情況.

現(xiàn)在證明第二部分.設u1，u2，u3和u4是Gp，q，sa，b，c中的三度點.接下來我們考慮兩種情況.

情形1（a，b，c）∈Ω／（0，0，0）

如果（a，b，c）＝｛（2，3，6），（2，4，4），（3，3，3）｝，由引理

當（a，b，c）＝（0，0，c）（c≠0）時，分兩步觀察.

（2）λ1λ1（G″）＞λ2（G″）＞2，λ3（G″）＜2，所以

因此當（a，b，c）∈Ω／（0，0，0）時，2是單根.

情形2（a，b，c）＝（0，0，0）

［1］Boulet R，Jouve B.The lollipop graph is determined by its spectrum［J］.The Electronic Journal of Combinatorics，2008.

［2］HaemersW H，Liu X，Zhang Y.Spectral characterizations of lollipop graphs［J］.Linear Algebra and Its Applications，2008，（11）：2415－2423.

［3］Ramezani F，Broojerdian N，Tayfeh－Rezaie B.A note on the spectral characterizations ofθgraphs［J］.Linear Algebra and Its Applications，2009，（5）：626－632.

［4］Wang J，Huang Q，Belardo F，et al.A note on the spectral characterizations of dumbbell graphs［J］.Linear Algebra and Its Applications，2009，（10）：1707－1714.

［5］Cvetkovic D M，Doob M，Sachs H.Spectra of Graphs：Theory and Application［M］.New York：Academic Press，1980.

［6］Van Dam E R，HaemersW H.Which graphs are determined by their spectrum？［J］.Linear Algebra and Its Applications，2003，373：241－272.

［7］Ghareghani N，OmidiGR，Tayfeh－Rezaie B.Spectral characterization of graphs with index atmost［J］.Linear Algebra and Its Applications，2007，（2）：483－489.

A M ain Result on the Graph G

LIDan，SU Yu，ZHANG Lidan，WANG Guoping
（School of Mathematical Sciences，Xinjiang Normal University，Urumqi Xinjiang 830054，China）

Let Gdenote the graph on n vertices obtained by taking three lollipop graphswith justa vertex in common.In this paper，we first prove thatφ（Pn，－2）＝n＋1 if n is even andφ（Pn，－2）＝－n－1 if n is odd；we then determine2∈Spec（G）if and only if（a，b，c）∈Ω＝｛（2，3，6），（2，4，4），（3，3，3），（0，0，c）（c≥0）｝.

spectrum；path；cycle

O157.5

A

1008－4681（2014）02－0005－02

（責任編校：晴川）

2013－08－21

李丹（1988－），女，新疆哈密人，新疆師范大學數(shù)學科學學院碩士生.研究方向：圖論與組合數(shù)學.