楊春燕，宋海洲

（華僑大學(xué)數(shù)學(xué)科學(xué)學(xué)院，福建泉州 362021）

給定頂點(diǎn)數(shù)和最大度的極大鄰接譜雙圈圖

楊春燕，宋海洲

（華僑大學(xué)數(shù)學(xué)科學(xué)學(xué)院，福建泉州 362021）

通過對(duì)圖進(jìn)行收縮、奪鄰、嫁接等運(yùn)算，并利用Perron向量的一些性質(zhì)，給出最大度為Δ（Δ≥3）的n（n≥5）階極大鄰接譜雙圈圖的一些性質(zhì)，同時(shí)得到極大鄰接譜雙圈圖的一些必要條件.

極大鄰接譜雙圈圖；鄰接譜；最大度；雙圈圖

本研究討論有限且無向的～.設(shè)B=（V，E）是以V為頂點(diǎn)集、E為邊集的～.用（u，v）或uv表示E中的一條邊，其中u、v∈V；d（v）表示頂點(diǎn)v的度；Δ表示B中頂點(diǎn)的最大度；NB（v）表示B中所有與頂點(diǎn)v相鄰的頂點(diǎn)構(gòu)成的集合；設(shè)A為B的鄰接矩陣，ρ（B）為B的鄰接譜半徑，若向量x=（x1，x2，…，xn）T滿足‖x‖=1且Ax=ρ（B）x，則稱x為B的Perron向量.

圖的鄰接譜是圖譜理論的主要研究?jī)?nèi)容之一.文獻(xiàn)[1]給出了圖的鄰接譜半徑的圖論意義.對(duì)于一個(gè)給定的圖的集合，確定該集合中圖的譜半徑的上界，并刻畫達(dá)到該上界的圖，是Brualdi等[2]提出的關(guān)于圖的譜半徑的一個(gè)問題，此后這個(gè)問題被廣泛研究.近年來關(guān)于雙圈圖的鄰接譜半徑的排序及分類問題的結(jié)果有很多.文獻(xiàn)[3]給出了前三大鄰接譜半徑及它們對(duì)應(yīng)的圖；文獻(xiàn)[4]進(jìn)一步給出了第四大和第五大鄰接譜半徑及它們對(duì)應(yīng)的圖；文獻(xiàn)[5]給出了第六大至第十大鄰接譜半徑及它們對(duì)應(yīng)的圖；文獻(xiàn)[6]研究了給定權(quán)集的賦權(quán)雙圈圖的譜半徑；文獻(xiàn)[7]研究了給定圍長(zhǎng)和懸掛點(diǎn)數(shù)的雙圈圖的譜半徑達(dá)到最大的極圖的一些性質(zhì)及極圖的部分特征.本研究考慮最大度為Δ的n階鄰接譜雙圈圖集中極大鄰接譜雙圈圖的性質(zhì).

1 一些定義和引理

定義1 設(shè)B*∈BΔn，若坌B∈BΔn，均有ρ（B）≤ρ（B*），則稱B*為BΔn中的一個(gè)極大鄰接譜雙圈圖.

定義2[4]設(shè)k≥2，v0，v1，…，vk為圖中互不相同的頂點(diǎn)，若d（v0）≥3，d（vk）≥3，且對(duì)任意滿足1≤i≤k-1的自然數(shù)i，均有d（vi）=2，則圖B的一個(gè)路徑v0v1…vk（k≥2）稱為圖B的一個(gè)內(nèi)部路.

定義3 設(shè)B=（V，E）是n階～，圖B中度為1的點(diǎn)稱為B的懸掛點(diǎn)，或稱該點(diǎn)為B的葉子頂點(diǎn).

定義4 設(shè)B是雙圈圖，C是B的一個(gè)圈.若導(dǎo)出子圖B[V（C）]是一個(gè)單圈圖，那么稱C為B的基圈.

引理1[8]設(shè)B是簡(jiǎn)單連通圖，x=（x1，x2，…，xn）T為B的Perron向量，xu、xv分別為頂點(diǎn)u、v對(duì)應(yīng)的Perron向量的分量，wi∈NB（v）{u}，i=1，…，k.令B1=B-（v，w1）-（v，w2）-…-（v，wk）+（u，w1）+（u，w2）+…+（u，wk），若B1仍為簡(jiǎn)單連通圖，且xu≥xv，則ρ（B1）＞ρ（B）.

引理2[8]設(shè)B=（V，E）是簡(jiǎn)單連通圖，x=（x1， x2，…，xn）T為B的Perron向量，分別為4個(gè)互不相同的頂點(diǎn)u1、u2、v1、v2對(duì)應(yīng)的Perron向量的分量，其中（u1，u2）、（v1，v2）∈E.令B1=B-（u1，u2）-（v1，v2）+（u1，v2）+（v1，u2），若B1仍為簡(jiǎn)單連通圖，且xu1≥xv1，xu2＜xv2，則ρ（B1）＞ρ（B）.

引理3[9]設(shè)B=（V，E）是簡(jiǎn)單連通圖，v0v1…vk（k≥2）為B的一條內(nèi)部路，若B1=B-（vi-1，vi）-（vi，vi+1）+（vi-1，vi+1）（1≤i≤k），則ρ（B1）≥ρ（B）.

引理4[10]設(shè)B=（V，E）是連通圖，u∈V（B），v埸V（B），B1=B+（u，v），則ρ（B1）＞ρ（B）.

①（v1，v3）∈E（B），（v2，v4）∈E（B），且（v1，v2）埸E（B），（v3，v4）埸E（B）.

②（v1，v4）∈E（B），（v2，v3）∈E（B），且（v1，v2）埸E（B），（v3，v4）埸E（B）.

證明 若①成立，令B1=B-（v1，v3）-（v2，v4）+（v1，v2）+（v3，v4），則易知.由xv1≥xv2≥xv3≥xv4，且xv1、xv2、xv3、xv4不全相等，有，由引理2知ρ（B1）＞ρ（B）.

若②成立，令B1=B-（v1，v4）-（v2，v3）+（v1，v2）+（v3，v4），則易知由不全相等，有不妨設(shè)由引理2知 ρ（B1）＞ρ（B）.

2 主要結(jié)果

引理6 設(shè)B*為中的極大鄰接譜雙圈圖，x=（x1，x2，…，xn）T為B*的Perron向量，分別為v1、v2對(duì)應(yīng)的Perron向量的分量.若d（v1）＞d（v2），則

證明 用反證法證明.假設(shè)xv1≤xv2.記p=d（v1）-d（v2）.由d（v1）＞d（v2），知v1、v2至多有d（v2）個(gè)公共鄰居，從而NB（*v1）{NB（*v2）∪{v2}}中存在p個(gè)點(diǎn)vj2，…，vjp，使得

引理7 設(shè)B*是中的一個(gè)極大鄰接譜雙圈圖，x=（x1，x2，…，xn）T為B*的Perron向量，則x的所有最大的分量對(duì)應(yīng)頂點(diǎn)的度均等于Δ.

證明 用反證法證明.設(shè)v*∈V（B*），滿足xv*=且d（v*）＜Δ.記p=d（v*），任取V（B*）中度為Δ的一個(gè)頂點(diǎn)u，則p＜Δ.由引理6知矛盾.故結(jié)論成立.

引理8 設(shè)B*是BΔn中的一個(gè)極大鄰接譜雙圈圖，x=（x1，x2，…，xn）T為B*的Perron向量.若u*對(duì)應(yīng)x中的分量xu*，滿足，則u*在B*的圈上.

證明 用反證法證明.設(shè)v*∈V（B*），滿足xv*=，點(diǎn)v*不在B*的任何一個(gè)圈上，由引理7可知d（v*）=Δ.這樣，B*中就存在一條長(zhǎng)為k的路v*v1…vk（k≥1），使得v*，v1，…，vk均不在B*的任何一個(gè)圈上，其中vk是葉子頂點(diǎn)，故d（vk）=1.對(duì)于B*的圈上任何一點(diǎn)u，有d（u）≥2＞d（vk），由引理7得xvk＜xu成立.

記v*為v0，設(shè)w是圈中離v*最近的頂點(diǎn)，在圈上任取2個(gè)異于w的相鄰頂點(diǎn)u1、u2，即u1≠w，u2≠w，（u1，u2）∈E（B*），則有與xv0≥xu2成立.從而存在自然數(shù)l∈[1，k]，使得如下2個(gè)不等式組中至少有1個(gè)成立：不妨假設(shè)自然數(shù)l0滿足1≤l0≤k，及.令+則易知.由引理2有 ρ（B1）＞ρ（B*），這與B*是BΔn中的一個(gè)極大鄰接譜雙圈圖矛盾.故結(jié)論成立.

推論 設(shè)B*是BΔn中的一個(gè)極大鄰接譜雙圈圖，x=（x1，x2，…，xn）T為B*的Perron向量，C為B*中的基圈，且V（C）={u1，u2，…，ul}，xu1，xu2，…，xul分別為頂點(diǎn)u1，u2，…，ul對(duì)應(yīng)的Perron向量的分量.若則l≤3.

證明 用反證法證明.假設(shè)l≥4.由引理7知d（u1）=d（u2）=…=d（ul）=Δ.不妨設(shè)u1，u2，…，ul在C上按順時(shí)針排列.由B*是雙圈圖知u1、u2、ul-1，ul中存在一個(gè)點(diǎn)，它有鄰居不在B*的圈上.不妨設(shè)u1的鄰居v1不在B*的圈上，由引理7知.令 B1=B-（u1，v1）-（ul-1，ul）+（u1，ul-1）+（v1，ul），B1和B如圖1所示，則易知由xu1=xu2=…=xul及可知又因?yàn)?，由引?有ρ（B1）＞ρ（B*），這與B*是中的一個(gè)極大鄰接譜雙圈圖矛盾.故假設(shè)不成立，從而結(jié)論成立.

圖1 B1和BFig.1 B1and B

引理9 設(shè)B∈BΔn，C是B中的基圈，V（C）={u1，u2，…，ul}（l≥4），且對(duì)任意滿足1≤i≤l-1的自然數(shù)i，均有（ui，ui+1）∈E（B），且（ul，u1）∈E（B）.若存在自然數(shù)i0∈[1，l]，使得d（ui0）=2，則存在B1∈BΔn，使得ρ（B1）＞ρ（B）.

證明 用反證法證明.假設(shè)B為BΔn中的極大鄰接譜雙圈圖.下面按C中度不小于3的點(diǎn)的個(gè)數(shù)分2種情形討論.

情形1 V（C）中至少有2個(gè)頂點(diǎn)的度不小于3.

記ul+1=u1，則對(duì)任意滿足1≤i≤l的自然數(shù)i，均有（ui，ui+1）∈E（B）.由于存在i0∈[1，l]，使得d（ui0）= 2，又V（C）中至少有2個(gè)點(diǎn)的度不小于3，可知存在滿足m≥2且1≤t≤l-m+1的自然數(shù)m和t，使得utut+1…ut+m為B的內(nèi)部路.令B1=（V（B1），E（B1）），其中：V（B1）=V（B）{ut+1}，E（B1）=E（B）-（ut，ut+1）-（ut+1，ut+2）+（ut，ut+2），易知B1∈BΔn-1，由引理3有ρ（B1）≥ρ（B）.

若B有葉子頂點(diǎn)，取B中的任意一個(gè)葉子頂點(diǎn)v0，令B2=B1+（v0，ut+1），易知B2∈BΔn，由引理4可得ρ（B2）＞ρ（B1），從而ρ（B2）＞ρ（B），與假設(shè)矛盾.

若B無葉子頂點(diǎn)，取B1中度為2的頂點(diǎn)v1，令B3=B1+（v1，ut+1），易知B3∈BΔn.由引理4可得ρ（B3）＞ρ（B1），從而ρ（B3）＞ρ（B），與假設(shè)矛盾.

情形2 V（C）中僅有一個(gè)點(diǎn)的度不小于3.

此時(shí)，設(shè)uj是V（C）中唯一的度不小于3的頂點(diǎn)，為方便，將C上的點(diǎn)重新編號(hào)為V（C）={v1，v2，…，vl-1，uj}，且v1，v2，…，vl-1，uj在C上按逆時(shí)針排列.由引理6可得

令B5=B-（vl-1，vl-2）+（vl-1，v1），則易知B5∈BΔn，由引理1有ρ（B5）＞ρ（B），與假設(shè)矛盾.

綜上可知假設(shè)不成立，故結(jié)論成立.

證明 因?yàn)閷?duì)于任意滿足1≤j≤l+1的自然數(shù)j，均有{uj，uj+1，…，uj+k-1}≠{r1，r2，…，rk}，所以k≥2，故C上存在不同的2點(diǎn)v1、v2，且存在滿足1≤i≤k，1≤s≤k及i＜s的自然數(shù)i和s，使得v1介于ri與ri+1（順時(shí)針）之間且與ri相鄰，v2介于rs與rs+1（順時(shí)針）之間且與rs相鄰，并且有由r1，r2，…，rk的定義可知x令B1=B-B1和B如圖2所示，則易知.因?yàn)橛梢?有ρ（B1）＞ρ（B），故定理結(jié)論成立.

圖2 B1和BFig.2 B1and B

[1]李喬，馮克勤.論圖的最大特征根[J].應(yīng)用數(shù)學(xué)學(xué)報(bào)，1979，2（2）：167-175.

[2] BRUALDI R A，SOLHEIDE S.On the spectral radius of complementary acyclic matrices of zerosandones[J].SIAMJAlgebra DiscreteMethods，1986，7：265-272.

[3] HE C X，LIU Y，SHAO J Y.On the spectral radii of bicyclic graphs[J]. Journal of Mathematical Research and Exposition，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]李丹，王國(guó)平.給定權(quán)集的賦權(quán)雙圈圖的譜半徑[J].華東師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2014（4）：39-42.

[7]張梅.雙圈圖的特征值與結(jié)構(gòu)參數(shù)[D].合肥：安徽大學(xué)，2010.

[8] BELARDO F，LI MARZI E M，SIMIC′S K，et al.On the spectral radius of unicyclic graphs with prescribed，degree sequence[J].Linear Algebra Application，2010，432（9）：2323-2334.

[10]方坤夫.圖的移接變換與譜半徑大小的關(guān)系[J].湖州師范學(xué)院學(xué)報(bào)，2007，29（2）：10-11.

（責(zé)任編校 馬新光）

Maximal-adjacency-spectrum bicyclic graphs with given order and maximum degree

YANG Chunyan，SONG Haizhou
（School of Mathematical Sciences，Huaqiao University，Quanzhou 362021，F(xiàn)ujian Province，China）

By using the operations of contracting，moving neighbors，grafting and the properties of Perron vector，the properties of the order n（n≥5）maximal-adjacency-spectrum bicyclic graphs with the maximum degree Δ（Δ≥3）are studied，and some necessary conditions about it are also obtained.

maximal-adjacency-spectrum bicyclic graphs；adjacency-spectrum；maximum degree；bicyclic graphs

1671-1114（2015）04-0016-04

O157.5

A

2014-12-17

華僑大學(xué)科研基金資助項(xiàng)目（10HZR26）.

楊春燕（1992—），女，碩士研究生.

宋海洲（1971—），男，副教授，主要從事圖論和組合優(yōu)化方面的研究.