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

        ?

        一類雙圈圖拉普拉斯譜刻畫(huà)

        2012-11-08 06:55:42
        關(guān)鍵詞:條邊拉普拉斯張掖

        劉 群

        (河西學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,甘肅 張掖 734000)

        一類雙圈圖拉普拉斯譜刻畫(huà)

        劉 群

        (河西學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,甘肅 張掖 734000)

        稱圖是由譜確定的,如果沒(méi)有非同構(gòu)的圖具有相同的譜。用Cq標(biāo)記長(zhǎng)度為q的圈。圈圖Cq的一個(gè)頂點(diǎn)與路圖Pr的一個(gè)懸掛點(diǎn)相連,圈圖Cq的一個(gè)頂點(diǎn)與Pr的另一個(gè)懸掛點(diǎn)相連,所得的圖稱為G(Cq,Cq,Pr)。本文將證明圖 G(Cq,Cq,Pr)由它的 Laplacian譜確定。

        圖的譜;共譜圖;特征值

        0 引言

        設(shè)圖 G=(V(G),E(G))是點(diǎn)集為 V(G)={v1,v2,v3,...,vn},邊集為 E(G)的圖。本文涉及到所有圖均為簡(jiǎn)單的無(wú)向圖。設(shè)A(G)圖G的(0,1)-鄰接矩陣,dk是點(diǎn)vk的度數(shù)。稱矩陣L(G)=D(G)-A(G)為圖G的Laplacian矩陣,其中D(G)是對(duì)角元素為{d1,d2,...,dn}的n×n階對(duì)角矩陣,記多項(xiàng)式P(L(G))=det(μI-L(G))為圖G 的Laplacian特征多項(xiàng)式,I為單位矩陣。令 P(L(G))=q0μn+q1μn-1+…… +qn,其中q0,q1,...,qn是多項(xiàng)式的系數(shù)。因?yàn)榫仃嘗(G)是實(shí)對(duì)稱矩陣,因此它的特征值都是實(shí)數(shù)。設(shè)μ1≥μ2≥……≥μn(=0)是圖的Laplacian特征值。圖G的Laplacian譜是由圖G的Laplacian特征值(帶重?cái)?shù))組成的。如果兩個(gè)圖具有相同的譜,那么稱這兩個(gè)圖是共譜的很明顯,如果兩個(gè)圖是共譜的,那么它們具有相同的點(diǎn)數(shù)。對(duì)于圖G,如果沒(méi)有非同構(gòu)的圖與它相關(guān)于Laplacian共譜,則稱圖G是由Laplacian譜確定的。

        在圖譜理論中,哪些圖是由圖譜確定的這一問(wèn)題似乎是一個(gè)比較難的問(wèn)題。

        截止目前,只有少數(shù)圖被證明有它的譜確定。本文將討論G(Cq,Cq,Pr)的拉普拉斯譜確定問(wèn)題,其中G(Cq,Cq,Pr)是指圈圖Cq的一個(gè)頂點(diǎn)與路圖Pr的一個(gè)懸掛點(diǎn)相連,圈圖Cq的一個(gè)頂點(diǎn)與Pr的另一個(gè)懸掛點(diǎn)相連。顯然它是一個(gè)具有2q-2+r個(gè)頂點(diǎn)和2q-1+r條邊的雙圈圖。

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

        引理1.1[1,2](1)設(shè)圖G是一個(gè)具有n個(gè)點(diǎn)和m條邊的圖,并設(shè)d=(d1,d2,…dn)點(diǎn)的不增的度序列,則多項(xiàng)式的一些系數(shù)滿足:

        其中m是圖G的邊數(shù),S(G)是圖G的支撐樹(shù)的數(shù)目。

        (2)對(duì)于Laplacian矩陣,根據(jù)它的譜我們可以得到:

        (a)圖G的連通分支數(shù);

        (b)圖G的生成樹(shù)的數(shù)目。

        (c)頂點(diǎn)度的平方和。

        引理1.2[3,4]設(shè)圖G是一個(gè)點(diǎn)集和邊集都不為空集的圖,則

        其中Δ(G)是圖G中點(diǎn)的度數(shù)的最大值,μ1是圖G的最大Laplacian特征值,mu是圖G中相鄰于點(diǎn)u的度數(shù)的平均值。

        2 圖G(Cq,Cq,Pr)是由它的Laplacian譜確定的

        定理2.1圖G(Cq,Cq,Pr)是由它的Laplacian譜確定。

        證明:設(shè)圖G'與圖G(Cq,Cq,Pr)相關(guān)于Laplacian矩陣同譜,則根據(jù)引理2.1

        和引理2.1(a),它們有相同數(shù)目的點(diǎn)數(shù)、邊數(shù)和連通分支數(shù),即圖G'有2q-2+r個(gè)點(diǎn)和2q-1+r條邊,并且它是連通的,由引理2.2可得4≤μ1≤4.8,因此圖G'沒(méi)有度數(shù)大于3的點(diǎn)。設(shè)圖G'中有度為i的點(diǎn)ni個(gè),i=1,2,...,△',Δ'≤3 是 G'的最大度,則

        若 Δ'≤2,則 n2=2q+r,n1= -2 <0 矛盾,因此 Δ'=3,得 n1=0,n2=2q+r-4,因此,G'是圖1 或圖2:

        圖 1 θ(a,b,c)

        圖 2 G(Ct,Cs,Ph)

        若 G'=θ(a,b,c),則 a+b+c-1=2q -2+r,ab+ac+bc=q2,解得 a∈φ,b∈φ,c∈φ 矛盾。

        若 G'=G(Ct,Cs,Ph),則 ts=q2,解得 t=q=s,故 G?G'。

        定理2.2圖G(Cq,Cq,Pr)是由它的Laplacian確定的。

        對(duì)于一個(gè)圖來(lái)說(shuō),它的Laplacian特征值確定了它的補(bǔ)圖的Laplacian特征值,因此顯然有下面的結(jié)論:

        推論2.3圖G(Cq,Cq,Pr)的補(bǔ)圖是由它的Lacplacian譜確定的。

        [1] E R van Dam,W H Haemers.Which graphs are determined by their spectrum[J].Linear Algebra Appl,2003(373):241 -272.

        [2] C S Oliveira,N M M de Abreu,S Jurkiewilz,The characteristic polynomial of the Laplacian of graphs in(a,b)-linear cases[J].Linear Algebra Appl,2002(365):113 -121.

        [3] A K Kelmans,V M Chelnokov.A certain polynomial of a graph and graphs with an extremal number of trees[J].Combin.Theory,Ser.B,1974(16):197-214.

        [4] J-S Li,X-D Zhang,On the Laplacian eigenvalues of a graph[J].Linear Algebra Appl,1998(285):305 -307.

        Laplacian Spectrum Characterization of a Class of Bicyclic Graphs

        LIU Qun

        (School of Mathematics and Statistics,Hexi University,Zhangye 734000,China)

        A graph G is determined by Laplacian spectrum if there is no other non-isomorphic graph with the same Laplacian spectrum.Cqdenotes the cycle with the length of q.G(Cq,Cq,Pr)is a graph consisting of two vertex-disjoints of cycle Cqand Prjoined by a path.This paper shows that graph G(Cq,Cq,Pr)is determined by its Laplacian spectrum.

        spectrum of a graph;cospectral graphs;eigenvalue

        O157.5

        A

        1009-3907(2012)08-0989-03

        2012-04-20

        劉群(1979-),女,甘肅張掖人,講師,碩士研究生,主要從事代數(shù)圖論方面的研究。

        責(zé)任編輯:程艷艷

        猜你喜歡
        條邊拉普拉斯張掖
        圖的Biharmonic指數(shù)的研究
        情暖張掖大地 讓愛(ài)不再孤單
        到張掖看黑河
        文學(xué)港(2019年5期)2019-05-24 14:19:42
        2018年第2期答案
        西夏時(shí)期的張掖
        西夏學(xué)(2016年2期)2016-10-26 02:20:26
        大美張掖
        絲綢之路(2016年13期)2016-08-10 07:58:08
        基于超拉普拉斯分布的磁化率重建算法
        認(rèn)識(shí)平面圖形
        位移性在拉普拉斯變換中的應(yīng)用
        含有一個(gè)參數(shù)的p-拉普拉斯方程正解的存在性
        亚洲最大av免费观看| 人人爽人人爽人人爽人人片av| 欧美大香线蕉线伊人久久| 无码国产日韩精品一区二区| 视频国产一区二区在线| 一本大道av伊人久久综合| 三年片免费观看大全国语| 中文不卡视频| 97女厕偷拍一区二区三区 | 亚洲 欧美 影音先锋| 国产又爽又黄又不遮挡视频| 亚洲1区第2区第3区在线播放 | 色哟哟精品视频在线观看| 国产精品原创巨作AV女教师| 中文熟女av一区二区| 国产精品成人一区二区不卡| 中文在线8资源库| 国产午夜久久久婷婷| 一本色道亚州综合久久精品| av中文字幕一区不卡| 三级特黄60分钟在线观看| 日本女优中文字幕看片| 日本精品人妻一区二区| 无码人妻aⅴ一区二区三区| 午夜亚洲www湿好大| 亚洲熟女国产熟女二区三区| 亚洲午夜精品一区二区麻豆av | 国产精品白浆免费观看| 亚洲一区精品在线中文字幕| 日日婷婷夜日日天干| 99国产精品久久久蜜芽| 高潮av一区二区三区| 女人高潮久久久叫人喷水| 亚洲成色在线综合网站| 国产免费的视频一区二区| 免费在线观看av不卡网站| 国产真实偷乱视频| 在线毛片一区二区不卡视频| 国产精品亚洲一区二区三区在线| 中文字幕乱码一区av久久不卡 | 不卡高清av手机在线观看|