李 丹，蘇 宇，張力丹，王國(guó)平

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

李 丹，蘇 宇，張力丹，王國(guó)平

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

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

譜；路；圈

1 基礎(chǔ)知識(shí)

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

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

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

2 主要結(jié)論

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

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

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

定理2.2 設(shè)Pn是n階路.那么：

證明由引理2.1，有

如果λ＝－2，那么

因?yàn)棣眨≒n－1，－2）＝－2φ（Pn－2，－2）－φ（Pn－3，－2），進(jìn)而可以得到φ（Pn，－2）＝3φ（Pn－2，－2）＋2φ（Pn－3，－2）.

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

引理2.3（交錯(cuò)定理）［6］設(shè)A是n×n的對(duì)稱矩陣，其特征值為λ1，λ2，…，λn.B是A的一個(gè)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是恰有兩個(gè)三度點(diǎn)的樹；

（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）當(dāng)且僅當(dāng)c＝0，2是單根.

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

此外，當(dāng)（a，b，c）∈Ω／（0，0，0）時(shí)，2是單根；當(dāng)（a，b，c）＝（0，0，0）時(shí)，2是二重根.

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

進(jìn)而通過(guò)引理2.4又有

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

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

接下來(lái)，只需要考慮0≤a≤3的情況.

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

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

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

當(dāng)（a，b，c）＝（0，0，c）（c≠0）時(shí)，分兩步觀察.

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

因此當(dāng)（a，b，c）∈Ω／（0，0，0）時(shí)，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

（責(zé)任編校：晴川）

2013－08－21

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