基于圈和三個孤立點的冠圖的Q-譜確定性

康同芳,　吳寶豐

(上海理工大學 理學院,上?！?00093)

?

基于圈和三個孤立點的冠圖的Q-譜確定性

康同芳,吳寶豐

(上海理工大學 理學院,上海200093)

設G是n階圖,H是m階圖,取n個H的拷貝,并將G的第i個點和第i個H中的每一點相連(i=1,2,…,n),所得到的(n+mn)階圖稱為冠圖,記為G°H.對基于圈和3個孤立點的冠圖的Q-譜確定性(無符號拉普拉斯譜確定性),即Cn°3K1的Q-譜確定性進行了研究,證明了當n≠32,64,128時,Cn°3K1由其Q-譜確定.

無符號拉普拉斯譜;Q-譜; 冠圖; 單圈圖

1　基本概念及背景介紹

現(xiàn)考慮的圖均為簡單無向圖.設G是n階圖,頂點集為V(G)={v1,v2,…,vn},邊集為E(G).矩陣Q(G)=D(G)+A(G)稱為G的Q-陣(無符號拉普拉斯矩陣).其中,A(G)為鄰接矩陣,若vi和vj之間有邊相連,則aij=1;否則,aij=0.D(G)=diag(d(v1),d(v2),…,d(vn))為度對角矩陣,d(vi)表示頂點vi的度.圖G的Q-特征多項式記為φQ(G,x)=det(xIn-Q(G)),G的Q-特征值即φQ(G,x)的根都是非負實數(shù),記為qi(G)(i=1,2,…,n),它們所構(gòu)成的多重集合{q1(G),q2(G),…,qn(G)}稱為G的Q-譜(無符號拉普拉斯譜).不妨設q1(G)≥q2(G)≥…≥qn(G)≥0,其中,當G連通時,qn(G)=0當且僅當G是二部圖.

Cn和Kn分別表示n階圈和n階完全圖,特別地,K1為孤立點.設G是n階圖,H是m階圖,取n個H的拷貝,并將G的第i個點和第i個H中的每一點相連(i=1,2,…,n),所得到的(n+nm)階圖稱為冠圖[1],記為G°H.例如,冠圖C4°3K1如圖1所示.

圖1　冠圖C4°3K1

對于圖G和圖H,如果它們的Q-譜相同,則稱它們是Q-同譜的.如果與G是Q-同譜的圖必與G同構(gòu),則稱圖G由其Q-譜確定.在圖譜理論中,“哪些圖由它的譜確定?”,換句話說“哪些圖的結(jié)構(gòu)由其譜確定?”,這個問題起源于半個世紀前的化學領域[2],一直以來,譜確定問題是一個比較困難的問題.一個圖是否由其譜確定,沒有一個統(tǒng)一的判斷方法,只能通過一些特殊的方法來判斷一些特殊的圖是否由其譜確定,相關研究見文獻[1-8].文獻[3-4]分別證明了Cn°K1由其Q-譜確定和由其L-譜(拉普拉斯譜)確定.文獻[1]證明了Cn°2K1由其L-譜確定,并且當n≠32,64時,Cn°2K1也由其Q-譜確定,類似的文獻還有文獻[5-7].

本文研究冠圖Cn°3K1的Q-譜確定性,給出了若干引理以及Cn°3K1的Q-譜及其性質(zhì),給出了Cn°3K1的Q-同譜圖其度序列可能的3種情況(定理1),并證明了當n≠32,64,128時,Cn°3K1由其Q-譜確定(定理2).

2　引理與推論

引理1[9]對于任意圖G,它的Q-特征值0的重數(shù)等于其二部連通分支的個數(shù).

b. 設G是n>1階連通圖,最大度為Δ,則q1(G)≥Δ+1.

引理3[9]設圖G有n個頂點、m條邊、t個三角形,頂點的度為d1,d2,…,dn.

引理4[10]設H是連通圖G的一個真子圖,則q1(H)

邊數(shù)等于頂點數(shù)的連通圖稱為單圈圖,它恰含一個圈,若這個圈為奇圈,則稱該圖為奇單圈圖.

引理5[3]設圖G的無符號拉普拉斯矩陣是Q,則det(Q)=4當且僅當G是奇單圈圖.

在文獻[11]中,Hoffman等給出了圖的內(nèi)部路的定義.設v0v1…vk(k≥1)是圖G的一條途徑,其中,v1,v2,…,vk互不相同(v0,vk不必不同),若d(v0)>2,d(vk)>2,d(vi)=2(i=1,2,…,k-1),則稱v0v1…vk為G的一條內(nèi)部路.

引理6[10,12]設uv是連通圖G的一條邊,Guv是通過對G的邊uv剖分得到的圖,則下面結(jié)論成立:

a. 若G=Cn,則q1(Guv)=q1(G)=4;

b. 若G≠Cn,uv不在G的一條內(nèi)部路上,則q1(Guv)>q1(G);

c. 若uv在G的一條內(nèi)部路上,則q1(Guv)

引理7[9]圖G的Q-特征多項式系數(shù)滿足

其中,求和取遍G中所有邊數(shù)為j的TU-子圖Hj.

引理8[13]設e是n階圖G中的一條邊,則

引理9[6]設G是n階圖,H是m階r-正則圖,則

即G°H的Q-譜是

推論1Cn°3K1的Q-譜是

推論3設n是偶數(shù),則

a. Cn°3K1所有非零Q-特征值的乘積為4n2;

證明a. n為偶數(shù)時,0是Cn°3K1的Q-特征值,重數(shù)為1,從而所有非零Q-特征值的乘積乘以(-1)4n-1等于特征多項式系數(shù)p4n-1.考慮Cn°3K1的(4n-1)條邊的TU-子圖,由引理7可得p4n-1=(-1)4n-14n2,從而結(jié)論a成立.

b. n為偶數(shù)時,由推論1可知Cn°3K1的Q-譜為

3　主要結(jié)論

定理1設圖G與Cn°3K1(n≥3)是Q-同譜的,Δ(G)是G的最大度,ai是G中度為i的頂點數(shù),t(G)是G中三角形的個數(shù),則下面結(jié)論之一成立:

a. Δ(G)=5,a0=0,a1=3n,a2=a3=a4=0,a5=n,t(G)=t(Cn°3K1);

b. Δ(G)=6,a0=1,a1=3n-2,a2=a3=0,a4=5,a5=n-6,a6=2,t(G)=0,n為偶數(shù);

c. Δ(G)=6,a0=1,a1=3n-2,a2=0,a3=1,a4=2,a5=n-3,a6=1,t(G)=1,n為偶數(shù).

證明由引理1可知G與Cn°3K1有相同的二部連通分支數(shù),即G至多有一個二部連通分支,所以,a0≤1.若a0=1,則G有孤立點,此時Cn°3K1為二部圖,n為偶數(shù),從而n≥4,t(Cn°3K1)=0.

情形1Δ(G)=4.由引理3可知

(1)

a. 若a0=0,解方程組(1)得

a1=6n-a4, a2=-8n+3a4,

a3=6n-3a4

從而a2+a3=-2n<0,與a2≥0,a3≥0矛盾.

b. 若a0=1,解方程組(1)得

a1=6n-3-a4, a2=-8n+3+3a4,

a3=6n-1-3a4

從而a2+a3=-2n+2≥0,得n≤1,矛盾.

情形2Δ(G)=5.由引理3可知

(2)

a. 若a0=0,解方程組(2)得

a1=6n-a4-3a5

a2=-8n+3a4+8a5

a3=6n-3a4-6a5

t(G)=4n+t(Cn°3K1)-a4-4a5

由a3≥0,a2+a3≥0得

此時a1=3n-a4≥0,a2=3a4≥0,a3=-3a4≥0,于是,a1=3n,a2=a3=a4=0,從而t(G)=t(Cn°3K1),即得定理1的結(jié)論a.

b. 若a0=1,解方程組(2)得

a1=6n-3-a4-3a5

a2=-8n+3+3a4+8a5

a3=6n-1-3a4-6a5

由a3≥0,a2+a3≥0得

情形3Δ(G)=6.由引理3可知

(3)

a. 若a0=0.當n≥4時,t(Cn°3K1)=0,解方程組(3)得

a1=6n-a4-3a5-6a6

a2=-8n+3a4+8a5+15a6

a3=6n-3a4-6a5-10a6

t(G)=4n-a4-4a5-10a6

于是

解得a6=0,與Δ(G)=6矛盾.

當n=3時,t(Cn°3K1)=1,此時t(G)=4n+1-a4-4a5-10a6,于是

b. 若a0=1,此時n為偶數(shù),n≥4,t(Cn°3K1)=0,解方程組(3)得

a1=6n-3-a4-3a5-6a6

a2=-8n+3+3a4+8a5+15a6

a3=6n-1-3a4-6a5-10a6

t(G)=4n+1-a4-4a5-10a6

于是

當a6=2時,同理可得a5=n-6,a4=5,從而a1=3n-2,a2=a3=0,t(G)=0,即得定理1的結(jié)論b.

綜合以上情形,定理1得證.

邊數(shù)等于頂點數(shù)加1的連通圖稱為雙圈圖.“dumbbell”圖是將2個不交的圈用路連接,且路的2個端點分別在2個圈上.“∞”圖是由2個圈組成,且這2個圈有且只有1個公共點.“θ”圖是將2個點用3條不相交的路連接得到(見圖2).每個雙圈圖必恰含“dumbbell”圖、“∞”圖、“θ”圖之一作為子圖,因此,雙圈圖可以分為3類:“dumbbell”型、“∞”型和“θ”型.

圖2　3類圖

引理10設G是雙圈圖,且q1(G)≤q1(Cn°3K1),則存在頂點v∈V(G),使得2≤d(v)≤4.進一步,當G是“dumbbell”型時,則至少存在2個頂點v1,v2∈V(G),使得2≤d(vi)≤4(i=1,2).

證明用反證法.按以下3種情況分別討論.

a.G是“dumbbell”型.假設G至多有1個度為2,3或4的點,則其余頂點的度是1或者大于等于5,從而G有真子圖Cg°3K1(g為某整數(shù)),由引理4和推論2可知,q1(G)>q1(Cg°3K1)=q1(Cn°3K1),矛盾.

b.G是“∞”型.假設G沒有度為2,3或4的點,則G有真子圖Cg°3K1(g為某整數(shù)),同理產(chǎn)生矛盾.

引理11設圖G與Cn°3K1是Q-同譜的,n=2γ,γ為正整數(shù),g為奇數(shù),則Cg°3K1不是G的1個分支.

(4)

引理12設圖G與Cn°3K1是Q-同譜的,若G與Cn°3K1具有相同的度序列,則G?Cn°3K1.

證明由引理1和引理3可知,G至多有1個二部連通分支,且G的邊數(shù)和頂點數(shù)相等.假設G恰有1個分支為樹,則G必有1個分支是雙圈圖,記為G0.因為,G與Cn°3K1具有相同的度序列,從而G沒有度為2,3或4的點,所以,由引理10可知,q1(G)≥q1(G0)>q1(Cn°3K1),矛盾,因此,G的所有分支均為單圈圖.

定理2設整數(shù)n≥3且n≠32,64,128,則Cn°3K1由其Q-譜確定.

證明設圖G與Cn°3K1是Q-同譜的,ai表示G中度為i的頂點數(shù),t(G)表示G中三角形的個數(shù).由定理1可知,Δ(G)=5或6.

假設Δ(G)=6,則G必滿足以下2種情況之一:

a. Δ(G)=6,a0=1,a1=3n-2,a2=a3=0,a4=5,a5=n-6,a6=2,t(G)=0,n為偶數(shù);

b. Δ(G)=6,a0=1,a1=3n-2,a2=0,a3=1,a4=2,a5=n-3,a6=1,t(G)=1,n為偶數(shù).

以下按G滿足的2種情況分別討論.

情形1a0=1,a1=3n-2,a2=a3=0,a4=5,a5=n-6,a6=2,t(G)=0,n為偶數(shù).此時Gi(i=1,2,…,c)的圍長均大于3.

情形1.1Gc是含2個奇圈的“dumbbell”型雙圈圖.

由引理10可知,Gc中至少有2個度為2,3或4的點.由a2=a3=0,a4=5得c≤4.設p(p≥10)是Gc中2個奇圈的長度和,q是連接Gc中2個奇圈的路的長度,則p+q≤4n-a1-5(c-1)=n-5c+7.另一方面,由引理7和推論3可知,G中所有非零Q-特征值的乘積為4c-1(4p+42q)=4n2.于是,

n+5c-7)≤q≤n-5c-3

即41-cn2-4n+20c+2≤0.

當c=1或2時,f(n)=41-cn2-4n+20c+2的判別式均小于0,矛盾.

當c=3時,解得27≤n≤37,考慮到n為2γ形式,所以,n=32,與條件不符.

當c=4時,解得23≤n≤233,所以,n=32,64或128,也與條件不符.

情形1.2若Gc不是含2個奇圈的“dumbbell”型雙圈圖.

此時,Gc是“θ”型、“∞”型或者是帶有1個偶圈1個奇圈的“dumbbell”型雙圈圖,由引理10可知,Gc中至少有1個度為2,3或4的點.由a2=a3=0,a4=5得c≤5.設x是Gc中使得Gc-e為奇單圈圖的邊e的個數(shù),則4cx=4n2,從而x=41-cn2≤4n-a1-5(c-1)=n-5c+7,即41-cn2-n+5c-7≤0.

當c=1時,解得-1≤n≤2,矛盾.

當c=2或3時,f(n)=41-cn2-n+5c-7的判別式均小于0,矛盾.

當c=4時,解得19≤n≤45,考慮到n為2γ形式,所以,n=32,與條件不符.

當c=5時,解得20≤n≤236,所以,n=32,64或128,也與條件不符.

情形2a0=1,a1=3n-2,a2=0,a3=1,a4=2,a5=n-3,a6=1,t(G)=1,n為偶數(shù).此時G中恰有1個三角形.

情形2.1Gc是含2個奇圈的“dumbbell”型雙圈圖.

由a2=0,a3=1,a4=2得c≤2.設p(p≥8)是Gc中2個奇圈的長度和,q是連接Gc中2個奇圈的路的長度.

當c=1時,G1是雙圈圖且含三角形,則p+q≤4n-a1=n+2.另一方面,4p+42q=4n2,于是

即n2-4n+16≤0,其判別式小于0,矛盾.

當c=2時,p+q≤max {4n-a1-5,4n-a1-3}=n-1.又4(4p+42q)=4n2.于是

即4-1n2-4n+28≤0,其判別式小于0,矛盾.

情形2.2若Gc不是含2個奇圈的“dumbbell”型雙圈圖.

由a2=0,a3=1,a4=2可知,c≤3.設x是Gc中使得Gc-e為奇單圈圖的邊e的個數(shù),則4cx=4n2,故x=41-cn2.

當c=1時,x=n2≤4n-a1=n+2,即n2-n-2≤0,解得-1≤n≤2,矛盾.

當c=2或3時,

4n-a1-5(c-1)}=n-5c+9

即41-cn2-n+5c-9≤0.

當c=2時,解得n=2,矛盾.

當c=3時,f(n)=41-cn2-n+5c-9的判別式小于0,矛盾.

綜合以上情形,Δ(G)≠6,即Δ(G)=5,因而由定理1可知,G與Cn°3K1具有相同的度序列,再由引理12可知,G?Cn°3K1,即Cn°3K1由其Q-譜確定.證畢.

當n=32,64或128時,Cn°3K1是否由其Q-譜確定,利用本文的方法無法確定,解決該問題需要用新的方法.同樣,文獻[1]也遺留了類似的問題:當n=32或64時,Cn°2K1不知道是否由其Q-譜確定.

[1]BU C J,ZHOU J,LI H B,et al.Spectral characterizations of the corona of a cycle and two isolated vertices[J].Graphs and Combinatorics,2014,30(5):1123-1133.

[2]VAN DAM E R,HAEMERS W H.Which graphs are determined by their spectrum?[J].Linear Algebra and its Applications,2003,373(11):241-272.[3]MIRZAKHAH M,KIANI D.The sun graph is determined by its signless Laplacian spectrum[J].Electronic Journal of Linear Algebra,2010,20:610-620.[4]BOULET R.Spectral characterizations of sun graphs and broken sun graphs[J].Discrete Mathematics and Theoretical Computer Science,2009,11(2):149-160.

[5]BU C J,ZHOU J.Starlike trees whose maximum degree exceed 4 are determined by theirQ-spectra[J].Linear Algebra and its Applications,2012,436(1):143-151.

[6]BU C J,HOU J,LI H B.Spectral determination of some chemical graphs[J].Filomat,2012,26(6):1123-1131.

[7]ZHANG Y P,LIU X G,ZHANG B Y,et al.The lollipop graph is determined by itsQ-spectrum[J].Discrete Mathematics,2009,309(10):3364-3369.

[8]沈富強,吳寶豐.最小Q-特征值為給定整數(shù)的一類圖[J].上海理工大學學報,2014,36(5):425-428.

[10]WANG J F,HUANG Q X,BELARDO F,et al.On graphs whose signless Laplacian index does not exceed 4.5[J].Linear Algebra and its Applications,2009,431(1/2):162-178.

[11]HOFFMAN A J,SMITH J H.On the spectral radii of topologically equivalent graphs[M]∥FIEDKER M.Recent Advances in Graph Theory.New York:Academic Press,1975:273-281.

(編輯:石瑛)

Q-Spectral Characterization of the Corona of A Cycle and Three Isolated Vertices

KANG Tongfang,WU Baofeng

(College of Science,University of Shanghai for Science and Technology,Shanghai 200093,China)

LetGbe a graph withnvertices,andHbe a graph withmvertices.The coronaG°His the graph withn+mnvertices obtained fromGandncopies ofHby joining thei-th vertex ofGto each vertex in thei-th copy ofH(i=1,2,…,n).TheQ-spectral characterization of the coronaCn°3K1was studied,whereCn°3K1was the corona of a cycle and three isolated vertices.It is proved thatCn°3K1is determined by its signless Laplacian spectrum whenn≠32,64,128.

signless Laplacian spectrum; Q-spectrum; corona; unicyclic graph

1007-6735(2016)04-0307-06

10.13255/j.cnki.jusst.2016.04.001

2016-04-08

國家自然科學基金資助項目(11301340,11201303);上海市自然科學基金資助項目(12ZR1420300);滬江基金資助項目(B14005)

康同芳(1990-),女,碩士研究生.研究方向:代數(shù)圖論.E-mail:1441005190@qq.com

吳寶豐(1978-),男,講師.研究方向:代數(shù)圖論.E-mail:baufern@usst.edu.cn

O 157.5

A