何春陽

(1.青海師范大學(xué) 數(shù)學(xué)系，青海 西寧 810008； 2.鹽城師范學(xué)院 數(shù)學(xué)科學(xué)學(xué)院，江蘇 鹽城 224002)

不含三圈的雙圈圖的譜半徑

何春陽1，2

(1.青海師范大學(xué) 數(shù)學(xué)系，青海 西寧 810008； 2.鹽城師范學(xué)院 數(shù)學(xué)科學(xué)學(xué)院，江蘇 鹽城 224002)

Nikiforov等人最近將圖譜研究與極值圖論相結(jié)合，提出了譜Turán型問題：給定一個(gè)圖F，設(shè)G是一個(gè)不含子圖與F同構(gòu)的n階圖，那么圖G的譜半徑至多是多少？雙圈圖是邊數(shù)等于頂點(diǎn)數(shù)加1的簡(jiǎn)單連通圖。近期，部分學(xué)者對(duì)雙圈圖的譜半徑進(jìn)行了研究，確定了雙圈圖譜半徑的第1～10大值和相應(yīng)的極圖。受此啟發(fā)，研究了不含三圈的雙圈圖，確定不含三圈的雙圈圖的譜半徑的上界，并刻畫了相應(yīng)的極圖。

雙圈圖；譜半徑；禁用三圈；譜Turán型問題

本文所考慮的圖都是有限無向簡(jiǎn)單圖，設(shè)G=(V,E)是一個(gè)n階圖，A(G)表示圖G的鄰接矩陣。因?yàn)锳(G)是實(shí)對(duì)稱的，所以它的特征根都是實(shí)數(shù)。稱A(G)的最大特征根為圖G的譜半徑，記為ρ(G)。

經(jīng)典極值圖論的一個(gè)中心問題是Turán型問題：給定一個(gè)圖F，設(shè)G是一個(gè)不含子圖與圖F同構(gòu)的n階圖，那么圖G的邊數(shù)至多是多少？最近，Nikiforov研究了譜Turán型問題：給定一個(gè)圖F，設(shè)G是一個(gè)不含子圖與圖F同構(gòu)的n階圖，那么圖G的譜半徑至多是多少？當(dāng)圖F為n階完全圖Kr、路、圈等圖時(shí)，他們分別確定了圖G的最大譜半徑和相應(yīng)的極圖，詳見文獻(xiàn)[1]。

對(duì)于一個(gè)給定的圖的集合，確定該集合中圖的譜半徑的上界，并刻畫達(dá)到該上界的圖,這是Brualdi和Solheid在文[2]中提出的關(guān)于圖的譜半徑的一個(gè)問題。此后這個(gè)問題被廣泛研究，并且獲得了很多結(jié)論。邊數(shù)等于頂點(diǎn)數(shù)加1的簡(jiǎn)單連通圖稱為雙圈圖。對(duì)于雙圈圖，何常香[3]確定了譜半徑的前3大值和相應(yīng)的極圖，亓靜[4]確定了譜半徑的第4和第5大值以及相應(yīng)的極圖，王興科、譚尚旺[5]進(jìn)一步確定了譜半徑的第6到第10大值和相應(yīng)的極圖。

受上述問題的啟發(fā)，本文研究不含三圈的雙圈圖的譜半徑，確定了不含三圈的雙圈圖的譜半徑的上界，并刻畫了相應(yīng)的極圖。

1 記號(hào)和引理

引理1.1[6]設(shè)u、v是n階連通圖G的任意兩個(gè)頂點(diǎn)，s為某一正整數(shù)，若{v1,v2,…,vs}∈NG(v)NG(u)非空，且x=(x1,x2,…,xn)T是G的Perron向量，其中xi對(duì)應(yīng)于頂點(diǎn)vi(1≤i≤n)。將G中的邊vvi替換為uvi(1≤i≤s)，所得到的圖記為G*，若xu≥xv，則ρ(G)<ρ(G*).

引理1.2[7]u是圖G的一個(gè)頂點(diǎn),C(u)是所有包含u的圈集合, 則圖G的特征多項(xiàng)式滿足

設(shè)Cp和Cq是兩個(gè)頂點(diǎn)不相交的圈，v1是Cp的一個(gè)頂點(diǎn)，vl是Cq的一個(gè)頂點(diǎn)，B(p,l,q)表示把Cp和Cq通過長(zhǎng)為l-1(l≥1)的路v1v2…vl連接而成的圖(見圖1)，l=1表示將v1和vl粘合成一點(diǎn)。設(shè)Pl+1、Pp+1和Pq+1是3個(gè)頂點(diǎn)不相交的路(l,p,q≥1)，P(l,p,q)表示分別將這3條路Pl+1、Pp+1和Pq+1的始點(diǎn)和終點(diǎn)粘合而得到的圖(見圖2)。

圖1 B(p,l,q)Fig.1 B(p,l,q)

圖2 P(l,p,q)Fig.2 P(l,p,q)

2 主要結(jié)果

x6-(n+1)x4+(4n-16)x2-4(n-7)=0

圖3 G3Fig.3 G3

首先，我們證明l=1。如若不然，設(shè)l>1，v1v2…vl是連接Cp和Cq的路。不失一般性，設(shè)x1≥xl，vl+1為vl在圈Cq上的一個(gè)鄰點(diǎn)。令

其次，我們證明G的所有樹均接在B(p,1,q)的4度頂點(diǎn)v1上。如若不然，設(shè)B(p,1,q)的另一頂點(diǎn)vi上接有一棵樹Ti。不妨設(shè)vi在圈Cp上，NG(vi)={vi-1,vi+1,z1,z2,…,zs}，其中vi-1、vi+1在圈Cp上。NG(v1)={vj-1,vj+1,w1,w2,…,wt}，其中vj-1、vj+1在圈Cp上。則s≥1,t≥2。如果x1≥xi，令

如果x1

綜上可知,G是在B(4,1,4)的4度頂點(diǎn)上接出一些懸掛邊所得到的圖，即圖3。對(duì)圖G3的度最大的頂點(diǎn)應(yīng)用引理1.2可得

(4n-16)x2-4(n-7)]

所以ρ(G3)為方程x6-(n+1)x4+(4n-16)x2-4(n-7)=0的最大根。

圖4 G1Fig.4 G1

圖5 G4Fig.5 G4

圖6 G5Fig.6 G5

對(duì)圖G5的頂點(diǎn)v1和v5應(yīng)用引理1.1可得

ρ(G5)<ρ(G4)。注意到

G2=G4-v2v3+v6v3=G4-v6v5+v2v5

對(duì)圖G4的頂點(diǎn)v2和v6應(yīng)用引理1.1可得

圖7 G2Fig.7 G2

對(duì)圖G1和圖G2的度最大的頂點(diǎn)應(yīng)用引理1.2可得

(4n-20)x2-2n+12)

定理2.3 設(shè)n≥8，G∈Bn，則

ρ(G)≤ρ(G3)，注意到

G4=G3-v5v2+v7v2=G3-v7v3+v5v3

對(duì)圖G3的頂點(diǎn)v5和v7應(yīng)用引理1.1可得ρ(G3)<ρ(G4)。

[1] Nikiforov V. Some new results in extremal graph theory[M]. Cambridge:Cambridge University Press 2011:141-181.

[2]BrualdiRA,SolheidES.Onthespectralradiusofcomplementaryacyclicmatricesofzerosandones[J].SIAMJ.AlgebraDiscreteMethods, 1986,7:265-272.

[3]HeCX,LiuY,ShaoJY.OntheSpectralRadiiofBicyclicGraphs[J].JournalofMathematicalResearchandExposition, 2007,27(3):445-454.

[4] 亓靜.n階雙圈圖的鄰接譜半徑[J].海南師范學(xué)院學(xué)報(bào)：自然科學(xué)版,2006,19(4):289-300.

[5] 王興科,譚尚旺.雙圈圖按譜半徑的排序[J].數(shù)學(xué)學(xué)報(bào)：中文版,2010,53(3):469-476.

[6]WuBF,XiaoE,HongY.Thespectralradiusoftreesonkpendantvertices[J].LinearAlgebraAppl, 2005,395:343-349.

[7]ChangA,TianF,YuA.Onthespectralradiusofunicyclicgraphswithperfectmatchings[J].LinearAlgebraAppl, 2003,370:237-250.

(責(zé)任編輯：張英健)

On the Spentral Radii of Bicyclic Graphs: Forbidden 3-Cycle

HE Chunyang1，2

1.Department of Mathematics, Qinghai Normal University, Xining Qinghai 810008, China;2.School of Mathematical Sciences, Yancheng Teachers University, Yancheng Jiangsu 224002, China

Recently, Nikiforov et al., combining spectral graph theory with the extremal graph theory, proposed the spectral Turán problem : “Given a graphF, what is the maximum spectral radius of a graph of ordern, with no subgraph isomorphic toF?” When theFis complete graph, path, and cycle etc, they determine the maximum spectral radius of the graphGrespectively. A bicyclic graph is a connected graph in which the number of edges equals the number of vertices plus 1. Its spectra has been investigated widely. Inspired by the above problems, in this paper we investigate the spectral radius of triangle-free bicyclic graphs, determine the largest spectral radius together with the corresponding extremal graph among all triangle-free bicyclic graphs of order.n(n≥8)

bicyclic graph; spectral radius; forbidden 3-cycle; spectral Turán problem

2014-05-20

國家自然科學(xué)基金資助項(xiàng)目(11171290)

何春陽(1987-)，男，遼寧凌源人，碩士生，主要研究方向?yàn)閳D論。

O

A

1671-5322(2014)03-0018-04