亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        眼鏡圖的譜刻圖

        2011-12-26 08:59:30吳廷增
        關(guān)鍵詞:圖記鄰接矩陣特征值

        吳廷增

        (青海民族大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,青海 西寧 810007)

        眼鏡圖的譜刻圖

        吳廷增

        (青海民族大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,青海 西寧 810007)

        只有與G同構(gòu)的圖才有相同的譜,則稱圖G是譜唯一確定的.眼鏡圖是在圈Cp和圈Cq的任意一個(gè)頂點(diǎn)之間加一條邊構(gòu)成的圖,記為ɡ(p,q).證明了眼鏡圖是譜唯一確定的.

        同譜圖;圖的譜;特征值

        0 引言

        在本文中如無特殊說明,我們僅考慮無環(huán)、無重邊的無向簡單圖.未定義的符號(hào)和術(shù)語參見文獻(xiàn)[1].對于任意的圖G,V(G)={v1,v2,…,vn}表示其頂點(diǎn)集,E(G)表示其邊集.對于任意的v∈V(G),用N(v)表示其鄰集.用d(vi)表示頂點(diǎn)vi的度,并且用Δ表示圖G中頂點(diǎn)的最大度.A(G)表示圖G的鄰接矩陣.多項(xiàng)式PA(G)(λ)=det(λI-A(G))是圖G對應(yīng)鄰接矩陣的特征多項(xiàng)式,記作PA(G)(λ)=λn+a1λn-1+…+an.因?yàn)锳(G)是實(shí)對稱矩陣,所以它的特征根都是實(shí)數(shù).假設(shè)λ1(G)≥λ2(G)≥…≥λn(G)是圖G的特征值,那么所有的特征值及相應(yīng)的重集分別稱為圖G的譜.其中λ1(G)稱為圖G的譜半徑.

        兩個(gè)圖是同譜的是指它們分享相同的譜.如果不存在非同構(gòu)圖H與圖G有相同的譜,則稱圖G是譜唯一確定的.Cn和Pn分別表示n個(gè)頂點(diǎn)的圈和路.假設(shè)Cp和Cq是兩個(gè)頂點(diǎn)不交的圈.令v1是Cp的頂點(diǎn)及vl是Cq的頂點(diǎn).在頂點(diǎn)v1和vl之間插入一條長為l-1的路v1v2…vl,結(jié)果圖記作ɡ(p,l,q),稱為ɡ-圖,見圖1,這里l>1.在圖ɡ(p,l,q)中,特別當(dāng)l=2時(shí),稱其為眼鏡圖,記作ɡ(p,q),見圖2.假設(shè)Pr+1,Ps+1和Pt+1是三條不交路,這里r,s,t≥1且它們中至多只有一個(gè)等于1.分別將三條路的首尾粘接起來所得的圖記為θ(r,s,t),稱為θ-圖,見圖3.

        圖1 ɡ-圖

        圖2 眼鏡圖

        圖3 θ-圖

        研究圖的譜唯一確定性是一個(gè)古老而又有趣的問題,迄今為止,僅有很小的一部分圖是譜唯一確定的[2-7],應(yīng)用背景及更詳細(xì)的內(nèi)容參見文獻(xiàn)[8].在本文中,將證明眼鏡圖是譜唯一確定的.

        1 預(yù)備知識(shí)

        2 ɡ(p,q)是內(nèi)部不同譜的

        3 ɡ(p,q)與ɡ(r,s,t)(s≥1)是不同譜的

        4 主要結(jié)果

        如果ɡ(p,q)圖有兩個(gè)4-圈,所以有8個(gè)頂點(diǎn),而8個(gè)頂點(diǎn)的θ(r,s,t)圖只能含有一個(gè)4-圈.

        定理如果ɡ(p,q)圖不含唯一的4-圈,則圖ɡ(p,q)是譜唯一確定的.

        證明由引理3—8和推論1可直接獲得該結(jié)果.

        我們雖然證明了ɡ(p,q)的譜唯一確定性,但是圖ɡ(r,s,t)是否譜唯一確定仍是一個(gè)非常困難的問題,還需要有新的方法才能刻畫.

        [1] CVETKOVIC'D M,DOOB M,SACHS H.Spectra of graphs[M].New York:Academic Press,1980:2-35.

        [2] DOOB M,HAEMERS W H.The complement of the path is determined by its spectrum[J].Linear Algebra Appl,2002(356):57-65.

        [3] HAEMERS W H,LIU XIAOGANG,ZHANG YUANPING.Spectral characterizations of lollipop graphs[J].Linear Algebra Appl,2008(428):2415-2423.

        [4] WU TINGZENG,HU SHENGBIAO.Some edges-deleted subgraphs of complete graph are determined by their spetrum[J].Mathematical Research & Exposition,2010(30):833-840.

        [5] RAMEZANI F,BROOJERDIAN N,TAYFEH-REZAIE B.A note on the spectral characterization ofθ-graphs[J].Linear Algebra Appl,2009(431):626-632.

        [6] SHEN XIAOLING,HOU YAOPING,ZHANG YUANPING.GraphZnand some graphs related toZnare determined by their spectrum[J].Linear Algebra Appl,2005(404):58-68.

        [7] WANG WEI,XU CHENGXIAN.On the spactral characterization ofT-shape trees[J].Linear Algebra Appl,2006(414):492-501.

        [8] VAN DAM E R,HAEMERS W H.Which graph are determined by their spectrum?[J].Linear Algebra Appl,2003(373):241-272.

        On the spectral characterization ofG-graph

        WU Ting-zeng

        (School of Mathematics and Statistics,Qinghai Nationalities University,Xining 810007,China)

        A graphGis said to be determined by its spectrum if any graph having the same spectrum asGis isomorphic toG.A glasses graph is bicyclic graph obtained from two cyclesCpandCqadding a edge between a vertex ofCpandCq,respectively.denoted byɡ(p,q).It is proved in this paper that theɡ(p,q)is determined by its spectrum.

        cospectral graph;spectra of graph;eigenvalues

        O 157.5

        110·7470

        A

        1000-1832(2011)03-0010-04

        2009-11-04

        國家自然科學(xué)基金資助項(xiàng)目(10861009);國家民委基金資助項(xiàng)目(10QH01).

        吳廷增(1978—),男,碩士,講師,主要從事代數(shù)圖論研究.

        陶 理)

        猜你喜歡
        圖記鄰接矩陣特征值
        輪圖的平衡性
        一類帶強(qiáng)制位勢的p-Laplace特征值問題
        單圈圖關(guān)聯(lián)矩陣的特征值
        煙圖記
        趣味(語文)(2020年3期)2020-07-27 01:42:40
        圖記
        基于鄰接矩陣變型的K分網(wǎng)絡(luò)社團(tuán)算法
        基于商奇異值分解的一類二次特征值反問題
        一種判定的無向圖連通性的快速Warshall算法
        圖記 端午節(jié)的驚喜
        圖記
        区三区久久精品水蜜桃av| 久久久www成人免费无遮挡大片| 热99re久久精品这里都是免费| 吃下面吃胸在线看无码| 草青青视频手机免费观看| 四虎影在永久在线观看| 精品久久欧美熟妇www| 毛片毛片免费看| 亚洲一区二区三区美女av| 国产一级一级内射视频| 少妇aaa级久久久无码精品片| 国产在线高清视频| 国产人成在线免费视频| 亚洲综合偷自成人网第页色| 极品少妇一区二区三区四区| 欧美色欧美亚洲另类二区不卡| 国产一区二区三区亚洲精品| 日本超级老熟女影音播放| 国产无遮挡又爽又刺激的视频老师| 无码国产精品一区二区免费16| 中文字幕色视频在线播放| 中文字幕精品亚洲字幕| 亚洲精品久久久久中文字幕| 正在播放国产多p交换视频| 精品蜜桃视频在线观看| 亚洲av午夜一区二区三| 樱桃视频影视在线观看免费| 国产乱人伦AV在线麻豆A| 亚洲精品综合久久国产二区| 久久99精品久久久久婷婷| 久久人人爽人人爽人人片亞洲| 亚洲第一区二区快射影院| 国产片在线一区二区三区| 久久精品中文字幕大胸| 91老司机精品视频| av在线不卡一区二区三区| 亚洲国产精品久久久久久无码| 久久久精品2019免费观看| 亚洲在线一区二区三区四区| 国产麻豆精品传媒av在线| 少妇饥渴偷公乱a级无码|