• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2016-11-08 05:13:32康同芳吳寶豐
    上海理工大學學報 2016年4期
    關鍵詞:偶數(shù)特征值頂點

    康同芳, 吳寶豐

    (上海理工大學 理學院,上?!?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

    猜你喜歡
    偶數(shù)特征值頂點
    認識奇數(shù)與偶數(shù)
    過非等腰銳角三角形頂點和垂心的圓的性質(zhì)及應用(下)
    一類帶強制位勢的p-Laplace特征值問題
    奇數(shù)與偶數(shù)
    偶數(shù)階張量core逆的性質(zhì)和應用
    單圈圖關聯(lián)矩陣的特征值
    關于頂點染色的一個猜想
    山東科學(2018年6期)2018-12-20 11:08:58
    基于商奇異值分解的一類二次特征值反問題
    關于兩個M-矩陣Hadamard積的特征值的新估計
    數(shù)學問答
    白水县| 郴州市| 辰溪县| 河北省| 漾濞| 定边县| 宝兴县| 五原县| 平远县| 比如县| 麦盖提县| 肥东县| 北辰区| 固始县| 乐陵市| 登封市| 郯城县| 华坪县| 大厂| 黄大仙区| 昌邑市| 长沙县| 湖州市| 旌德县| 菏泽市| 南宫市| 桐梓县| 台江县| 巫山县| 沙洋县| 佳木斯市| 湄潭县| 泾源县| 大埔区| 潮安县| 南阳市| 开平市| 无棣县| 南京市| 连江县| 湘西|