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

        ?

        Y(2,2,λ)形圖的伴隨多項(xiàng)式的分解及其補(bǔ)圖的色等價(jià)性

        2015-11-26 05:54:34王云蘆殿軍張秉儒
        關(guān)鍵詞:子圖奇數(shù)偶數(shù)

        王云,蘆殿軍,張秉儒

        (1.青海大學(xué),青海 西寧810006;2.青海師范大學(xué)數(shù)學(xué)系,青海 西寧810008)

        Y(2,2,λ)形圖的伴隨多項(xiàng)式的分解及其補(bǔ)圖的色等價(jià)性

        王云1,蘆殿軍2,張秉儒2

        (1.青海大學(xué),青海 西寧810006;2.青海師范大學(xué)數(shù)學(xué)系,青海 西寧810008)

        構(gòu)造了兩類圖簇Y(2,2,λ)∪K1(m為奇數(shù))和Y(2,2,λ)∪EGδ(m為偶數(shù)).運(yùn)用圖的伴隨多項(xiàng)式,討論了這兩類圖簇的伴隨多項(xiàng)式的因式分解式,(m=2k-1q-1,λk=(2kq-1)+2k-1qδ),研究了圖簇Y(2,2,λk)∪(k-1)K1和Y(2,2,λk)的伴隨多項(xiàng)式的因式分解式,進(jìn)而證明了這些圖的補(bǔ)圖的色等價(jià)性.

        伴隨多項(xiàng)式;因式分解;色等價(jià)性

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

        對(duì)于簡(jiǎn)單圖來說,用V(G)表示圖G的頂點(diǎn)集.E(G)表示圖G的邊集.是圖G的補(bǔ)圖.G∪H和nG分別表示圖G和H的點(diǎn)不重并,n個(gè)圖G的點(diǎn)不重并,未加說明的記號(hào)和術(shù)語參考文獻(xiàn)[1-2].設(shè)p(G,λ)為圖G的色多項(xiàng)式,稱圖G與H色等價(jià),若p(G,λ)=p(H,λ).稱圖G是色唯一圖,若從p(H,λ)=p(G,λ)得到圖H與G同構(gòu),記為G≌H.文獻(xiàn)[3-4]首先提出色等價(jià)圖和色唯一圖的概念.1987年文獻(xiàn)[5]提出了圖G的伴隨多項(xiàng)式h(G,x)和伴隨唯一性的概念,并在色唯一圖的研究中獲得一系列新成果[6-8].目前色等價(jià)圖的結(jié)構(gòu)規(guī)律尚待解決.本文中,由自然數(shù)m的奇偶性及已有的圖,構(gòu)造了幾類

        新的圖簇,且運(yùn)用圖的伴隨多項(xiàng)式的性質(zhì),主要討論了

        圖簇的伴隨多項(xiàng)式及其因式分解式,當(dāng)m=2kq-1,λn=(2nq-1)+2n-1qr時(shí),討論了圖簇Y(2,2,λk)∪(k-1)K1和Y(2,2,λk)的伴隨多項(xiàng)式的因式分解式,并且證明了上述圖簇的補(bǔ)圖的色等價(jià)性,確定了它們的補(bǔ)圖的色等價(jià)圖的構(gòu)成規(guī)律.

        2 圖的伴隨多項(xiàng)式的概念

        設(shè)G是p階圖,若圖G的生成子圖G0的所有分支是完全圖,則稱G0為圖G的理想子圖.用bi(G)表示圖G的具有p-i個(gè)分支的理想子圖的個(gè)數(shù)(0≤i≤p-1),由文獻(xiàn)[4]的定理15可知

        其中p=|V(G)|,(λ)k=λ(λ-1)(λ-2)···(λ-k+1).

        定義2.1[5]設(shè)G是p階圖,則圖G的多項(xiàng)式

        稱為簡(jiǎn)單圖G的伴隨多項(xiàng)式,h(G,x)可以簡(jiǎn)記為h(G).圖G的每個(gè)分支或是K1或是K2的生成子圖稱為圖G的一個(gè)匹配,圖G的一個(gè)K-匹配就是含有k條邊的匹配,由G的理想子圖的個(gè)數(shù)bi(G)的定義即得如下的.

        引理2.1[5]若G是無三角形K3的圖,則bi(G)等于圖G的匹配數(shù)目.

        定義2.2稱圖G與H是伴隨等價(jià)的,若h(G,x)=h(H,x),稱圖G是伴隨唯一的,若從h(G,x)=h(H,x)推出G與H同構(gòu),記為H≌G.

        引理2.2[6]圖G與H是伴隨等價(jià)的當(dāng)且僅當(dāng)和是色等價(jià)的;圖G是伴隨唯一的當(dāng)且僅當(dāng)是色唯一的.

        下面給出常用到圖的伴隨多項(xiàng)式h(G,x)的基本性質(zhì).

        引理2.3[7]設(shè)uv∈E(G)且uv不屬于圖G的任何三角形,則有

        引理2.4[7]設(shè)圖G具有k個(gè)分支G1,G2,···,Gk,則有

        設(shè)G是任意的連通圖,其伴隨多項(xiàng)式為h(G,x),以下簡(jiǎn)記為h(G).根據(jù)引理2.4,易得下面引理成立.

        引理2.5設(shè)G和H是任意的兩個(gè)圖,K1是一個(gè)孤立點(diǎn),n≥2是任意的自然數(shù),則有

        引理2.6[10]設(shè)n≥2是自然數(shù),Sn表示具有n個(gè)頂點(diǎn)的星圖,則有

        3 幾類新圖的伴隨多項(xiàng)式

        設(shè)G是任意的p階圖,nG表示n個(gè)圖G的不相交并,設(shè)Pn和Cn是具有n個(gè)頂點(diǎn)的路和圈,Sn是n個(gè)頂點(diǎn)的星圖,表示把星Sr+1的r個(gè)1度點(diǎn)分別與rG的每個(gè)分支的第i個(gè)頂點(diǎn)vi(1≤i≤p)重迭,并把另一個(gè)G的第i個(gè)頂點(diǎn)與Sr+1的r度點(diǎn)重迭后得到的圖(如圖3.1所示),其中δ=(r+1)p,r∈N,r≥2,di=d(vi);設(shè)

        圖3.1 EδG圖

        圖3.2 圖

        圖3.3 ΨK(2,m+2-1(m+1)δ)圖

        圖3.4 圖

        圖3.5 Y(2,m+2-1(m+1)δ)圖

        圖3.6 ΨT(2δ,2,m+2-1mδ),m=2t圖

        圖3.7 Y(2,2,(2m+1)+(m+1)δ)圖

        引理3.1設(shè)m(≥3)是奇數(shù),r是任意自然數(shù),r≥1,δ=(r+1)p,p=|V(G)|,則有

        引理3.3設(shè)m(≥4)為偶數(shù),r是自然數(shù),r≥1,δ=(r+1)p,p=|V(G)|,則有

        證明 參考圖3.3,m是偶數(shù),則m+1是奇數(shù),故d(vm)=2,d(vm+1)=r+di+1,這里di=d(vi),vi∈V(G),在圖Ψk(2,m+2-1(m+1)δ)中取邊e=vmvm+1,則由引理2.3和引理2.4,立即推知(9)式成立.

        引理3.4設(shè)m(≥3)為奇數(shù),r是自然數(shù),r≥1,δ=(r+1)p,p=|V(G)|,則有

        證明 當(dāng)m為奇數(shù)時(shí),此時(shí)m+1與m-1均為偶數(shù),d(u1)=1,d(v1)=di+r+1,這里di=d(vi),vi∈V(G),如圖3.4所示,在圖Y(1,2,m+2-1(m+1)δ)中取e=u1v1,由引理2.3和引理2.4,即得

        上式右端提取公因子x,即得(10)式.

        如圖3.5所示,在圖Y(2,2,m+2-1(m+1)δ)中取e=u1v1,由引理2.3和引理2.4,即得

        結(jié)合(10)式,容易推知(11)也成立.

        引理3.5設(shè)m(≥4)為偶數(shù),1≤r∈N,δ=(r+1)p,p=|V(G)|,則有

        證明 當(dāng)m為偶數(shù)時(shí),參考圖3.6,圖ΨT(δ,2,m+2-1mδ)即為ΨK(2,(m+1)+2-1(m+2)δ),故由(9)式即得(12)式.

        當(dāng)m為偶數(shù)時(shí),此時(shí)m-1為偶數(shù),d(u1)=r+di+1,d(vm)=3,這里di=d(vi),vi∈V(G),如圖3.6所示,在圖ΨT(2δ,2,m+2-1mδ)中取e=u1vm,由引理2.3和引理2.4,并運(yùn)用(12)式,即得

        由此可知(13)式成立.

        引理3.6設(shè)m和r都是自然數(shù),r≥1,δ=(r+1)p,p=|V(G)|,

        4 因式分解定理

        定理4.1設(shè)m(≥3)為奇數(shù),1≤r∈N,δ=(r+1)p,p=|V(G)|,則有

        證明 當(dāng)m(≥3)為奇數(shù)時(shí),注意到h(K1)=x,由引理2.5、(14)式和(11)式,即得

        因此(18)式成立.

        由引理2.5及(18)式,推知(19)式也成立.

        定理4.2設(shè)k(≥2)是任意自然數(shù)而q(≥3)是奇數(shù),λk=(2kq-1)+2k-1qδ,δ=(r+1)p,p=|V(G)|,則有

        證明 設(shè)m是形如m=2k-1q-1的奇數(shù),注意到λk=(2kq-1)+2k-1qδ,則計(jì)算可得

        將上述頂點(diǎn)數(shù)代入(18)式,即得

        由此可知(20)式成立;同理,將上述頂點(diǎn)數(shù)代入(19)式,即得(21)式.

        定理4.3設(shè)k(≥2)是任意自然數(shù)而q(≥3)是奇數(shù),λk=(2kq-1)+2k-1qδ,δ=(r+1)p,p=|V(G)|,則有

        證明 對(duì)自然數(shù)k≥2作數(shù)學(xué)歸納法:當(dāng)k=2時(shí),由(20)式易推知

        此時(shí)(22)式成立.假定結(jié)論對(duì)于k-1成立,對(duì)于k的情形,由引理2.5、(20)式及歸納假定即

        即當(dāng)k時(shí)結(jié)論也成立,故由數(shù)學(xué)歸納法原理知,對(duì)于任意的自然數(shù)k≥2,(22)式成立.

        根據(jù)引理2.4及(22)式,容易推知(23)式成立.

        定理4.4設(shè)k(≥2)是任意自然數(shù)而q(≥3)是奇數(shù),λk=(2kq-1)+2k-1qδ,δ=(r+1)p,p=|V(G)|,則有

        定理4.5設(shè)k(≥2)是任意自然數(shù)而q(≥3)是奇數(shù),λk=(2kq-1)+2k-1qδ,δ=(r+1)p,p=|V(G)|,則有

        上式兩端消去即得(26)式.

        由引理2.4及(26)式,容易推知(27)式成立.

        定理4.6設(shè)m(≥4)為偶數(shù),1≤r∈N,δ=(r+1)p,p=|V(G)|,則有

        故(28)式成立.

        由引理2.4及(28)式,容易推知(29)式成立.

        5 圖的色價(jià)性分析

        在給出幾類圖的伴隨分解的基礎(chǔ)上,討論這些圖色等價(jià)性.

        定理5.1設(shè)m(≥3)為奇數(shù),1≤r∈N,δ=(r+1)p,p=|V(G)|,則有圖簇Y(2,2,(2m+ 1)+(m+1)δ)∪K1與ΨK(2,m+2-1(m+1)δ)∪Y(2,2,m+2-1(m+1)δ)二者的補(bǔ)圖是色等價(jià)的.

        證明 根據(jù)(19)式知,Y(2,2,(2m+1)+(m+1)δ)∪K1=h(ΨK(2,m+2-1(m+ 1)δ)∪Y(2,2,m+2-1(m+1)δ)).由此及定義2.2可知,Y(2,2,(2m+1)+(m+1)δ)∪K1與ΨK(2,m+2-1(m+1)δ)∪Y(2,2,m+2-1(m+1)δ)圖簇是伴隨等價(jià)的,由此及引理2.2可知,補(bǔ)圖是色等價(jià)的.

        定理5.2設(shè)k(≥2)是任意自然數(shù)而q(≥3)是奇數(shù),λk=(2kq-1)+2k-1qδ,δ=(r+1)p,p=|V(G)|,則Y(2,2,λk)∪K1與ΨK(2,λk-1)∪Y(2,2,λk-1)圖簇的補(bǔ)圖是色等價(jià)的.

        證明 根據(jù)(21)式知

        由此及定義2.2可知Y(2,2,λk)∪K1與ΨK(2,λk-1)∪Y(2,2,λk-1)二者是伴隨等價(jià)的,由此及引理2.2可知,它們的補(bǔ)圖是色等價(jià)的.

        仿此,根據(jù)定義2.2和引理2.2以及(23)、(27)、(29)三式,同法可證如下的結(jié)論.

        定理5.3設(shè)?k∈N,k≥2而q(≥3)是正奇數(shù),λk=(2kq-1)+2k-1qδ,δ=(r+1)p,p=|V(G)|,則Y(2,2,λk)∪(k-1)K1與Y(2,2,λ1)∪ΨK(2,λ1)∪ΨK(2,λ2)∪...∪ΨK(2,λk-1)圖簇二者的補(bǔ)圖是色等價(jià)的.

        定理5.4設(shè)k(≥2)是任意自然數(shù)而q(≥3)是奇數(shù),λk=(2kq-1)+2k-1qδ,δ=(r+1)p,p=|V(G)|,則圖簇Y(2,2,λk)與Y(2,2,λ1)∪CEG1+λ1∪CEG1+λ2∪···∪CEG1+λk-1二者的補(bǔ)圖是色等價(jià)的.

        定理5.5設(shè)m(≥4)為偶數(shù),1≤r∈N,δ=(r+1)p,p=|V(G)|,則圖簇Y(2,2,(2m+ 1)+(m+1)δ)∪與Y(1,2,(m-1)+2-1mδ)∪ΨT(2δ,m+2-1mδ)二者的補(bǔ)圖是色等價(jià)的.

        [1]Bondy J A,Murty U S R.Graph Theory With Applications[M].Amsterdam:North-Holland,1976.

        [2]Bollobas B.Modern Graph Theory[M].New York:Spinger-Verlag,1998.

        [3]Chao C Y,Whitehead E G.On chromatic equivalance of graph[J].Springer Lecture Note in Mathematics,1978,642:121-131.

        [4]Koh K M,Teo K L.The search for chromatically unique graphs[J].Graph Combin,1990,6:259-285.

        [5]Biggs N.Algebraic Graph Theory[M].Cambridge:Cambridge University Press,1974.

        [6]Wang J F,Huang Q X,Liu R Y,Ye C F.A complete solution to the chromatic equivalence class of graph[J].Discrete Math.,2008,308:3607-3623.

        [7]Wang J F,Huang Q X,Liu R Y,Ye C F,et al.The chromatic equvalence class of graphdiscussiones math[J].Graph Theory,2008,28(2):189-218.

        [8]Zhao H X,Li X L,Liu R Y.On problems and conjectures on adjointly equivalent graphs[J].Discrete Mathematics,2005,295:203-212.

        [9]劉儒英.兩類圖的色多項(xiàng)式[J].科學(xué)通報(bào),1987,32:1147-1148.

        [10]張秉儒.圖的伴隨多項(xiàng)式的因式分解定理及應(yīng)用[J].數(shù)學(xué)學(xué)報(bào),2005,48(1):125-132.

        The factorizations of adjoint polynomials of graphs of shape as Y(2,2,λ)and chromatically equivalence of their complements

        Wang Yun1,Lu Dianjun2,Zhang Bingru2
        (1.Qinghai University,Qinghai Xining810008,China;2.Department of Mathematics,Qinghai Normal University,Qinghai Xingning810008,China)

        By unsing the properties of adjoint polynomials of graphs or even,we discuss the factorizations of adjoint polynomials of graphs Y(2,2,λ)∪K1(where m is odd)and Y(2,2,λ)∪EGδ(where m is even).Let m=2Kq-1,letλn=(2nq-1)+2n-1qδ,we discuss the factorizations of adjoint polynomials of graphs Y(2,2,λk)∪(k-1)K1and Y(2,2,λk).Further more,we prove chromatically equivalence of complements of these graphs.

        adjoint polynomials,factorization,chromatically equivalence

        O157.5

        A

        1008-5513(2015)04-0338-12

        10.3969/j.issn.1008-5513.2015.04.002

        2015-01-18.

        青海省自然科學(xué)基金(2015-ZJ-724);教育部春暉計(jì)劃(教外司留[2014]1310號(hào)).

        王云(1967-),碩士,副教授,研究方向:代數(shù)圖論,代數(shù)組合與密碼學(xué).

        2010 MSC:05C78

        猜你喜歡
        子圖奇數(shù)偶數(shù)
        認(rèn)識(shí)奇數(shù)與偶數(shù)
        奇數(shù)湊20
        奇數(shù)與偶數(shù)
        偶數(shù)階張量core逆的性質(zhì)和應(yīng)用
        關(guān)于奇數(shù)階二元子集的分離序列
        臨界完全圖Ramsey數(shù)
        基于頻繁子圖挖掘的數(shù)據(jù)服務(wù)Mashup推薦
        不含2K1+K2和C4作為導(dǎo)出子圖的圖的色數(shù)
        頻繁子圖挖掘算法的若干問題
        有多少個(gè)“好數(shù)”?
        伊人久久大香线蕉av色婷婷| 国产精品开放小视频| 欧美日韩激情在线一区二区| 日韩国产一区二区三区在线观看 | 香蕉久久久久久久av网站| 亚洲一区二区三区av在线免费| 蜜桃成人精品一区二区三区| 国产日产欧产精品精品蜜芽| 国产成人无码一区二区三区在线| 丰满少妇爆乳无码专区| 在线观看一区二区三区视频| 东北少妇不戴套对白第一次| 水蜜桃无码视频在线观看| 免费看国产精品久久久久| 久久影院最新国产精品| 精品av熟女一区二区偷窥海滩| 日日噜噜噜夜夜爽爽狠狠| 鲁丝一区鲁丝二区鲁丝三区| 五月婷婷开心六月激情| 免费人妻无码不卡中文字幕系| 亚洲一区爱区精品无码| 亚洲一区二区国产精品视频| 加勒比东京热中文字幕| 亚洲av麻豆aⅴ无码电影| 欧美日韩精品一区二区三区高清视频| 中文字幕人妻久久一区二区三区| 性欧美丰满熟妇xxxx性久久久 | 日本一区午夜艳熟免费| 一本色道久久综合狠狠躁中文 | 亚洲熟伦在线视频| 蜜桃视频在线观看网址| 久久综合给合综合久久| 国产精品天堂avav在线| 亚洲偷自拍国综合第一页国模| 国产a级三级三级三级| 国产一起色一起爱| av永远在线免费观看| 丰满人妻一区二区三区蜜桃| 国产精品jizz视频| a√无码在线观看| 国产日韩精品中文字幕|