發(fā)布時間：2017-08-05 08:03

  本文關(guān)鍵詞：圖的強平衡頂點蔭度若干問題研究

  更多相關(guān)文章： 平衡著色 (t k)-樹-著色 強平衡頂點蔭度 Nordhaus-Gaddum類型結(jié)果 Cartesian積網(wǎng)絡(luò)

【摘要】：圖的平衡著色問題是Meyer[36]于1973年提出并進行研究,目前該主題己經(jīng)獲得了廣泛的關(guān)注和研究.如果f是從V(G)到{1,2...,t}的一個映射,那么f是圖G中的t-著色.令Vi={v|f(v)=i}(1≤i≤t)如果對于所有的i和j有||Vi|-|Vj||≤1,那么圖G的t-著色f是平衡的.最近,Wu等人[42]提出了平衡(t,k)-樹-著色的概念,這一概念可以看作是真平衡t-著色的一個推廣.如果G[Vi](1≤i≤t)的每個分支是最大度不超過k的樹,那么這個t-著色f是圖G的一個(t,k)-樹-著色.一個平衡的(t,k)-樹-著色是一個(t,k)-樹-著色并且是平衡的.圖G的平衡頂點k-蔭度,記作vak=(G),是使得圖G有平衡的(t,k)-樹-著色的最小的整數(shù)t.圖G的強平衡頂點k-蔭度,記作vak≡(G),是使得圖G對于每個大于等于t的t'均有平衡的(t',k)-樹-著色的最小的整數(shù)t.Wu等人[42]研究了完全等部二部圖的強平衡頂點k-蔭度.他們給出了va1≡(kn,n)不va∞≡(Kn,n)的上界.同時,他們證明當(dāng)n≡2(mod 3)時,va1≡(Kn,n)達(dá)到了上界.隨后,Tao等人[40]對當(dāng)n≡0(mod 3)和n≡1(mod 3)時,va1≡(Kn,n)進行了研究.他們改進了其上界,并且對于一些特殊情形,獲得了精確值.在本文中,進一步研究圖的強平衡頂點蔭度問題.本文的主要研究結(jié)果包括以下幾個方面：1.研究了完全非等部二部圖Kn,n+1的強平衡頂點1-蔭度和完全非等部二部圖Kn,n+e(1≤e≤n)的強平衡頂點2-蔭度.對于va1≡(Kn,n+1)(n≥1),給出其上界.接著,分別對n≡0,1,2(mod 3)的所有情形進行了討論.當(dāng)n≡1 (mod 3)時,證明ua1≡(Kn,n+1)達(dá)到其上界.當(dāng)n≡0,2(mod 3)時,令n≡3k+i(i=0,2),又分四種子情形k≡0,1,2,3(mod 4)分別對其進行討論并改進了它的上界.對于va2≡(Kn,n+e)(1≤e≤n),給出了一個緊的上界.并且證明了當(dāng)n=3t(t≤2)時,va2≡(Kn,n+1)達(dá)到了其上界.2.研究了完全三部圖Kn,n,n的強平衡頂點2-蔭度和強平衡頂點3-蔭度.對于va2≡(Kn,n,n),當(dāng)n≡1,2,3(mod 4)時,分別獲得了其精確值.當(dāng)n≡0 (mod 4)時,令n=4k,再分五種子情形：k≡0,1,2,3,4 (mod 5)分別對其進行討論.對于k≡1,2,3,4(mod 5)的情形,分別獲得了其精確值.當(dāng)k≡0(mod 5)時,給出其上界.對于va3≡(Kn,n,n)(n≥3),首先給出其上界.當(dāng)n≡0,1,2(mod 4)時,令n≡4k+i(i=0,1,2),又分五種子情形：k≡0,1,2,3,4(mod 5)分別對其進行討論.當(dāng)n≡0(mod 4)且k≡1,2,3,4(mod 5)時,分別獲得了其精確值.對k≡0(mod 5)時,改進了其上界.當(dāng)n≡1(mod 4)且k≡2,3,4,0(mod 5)時,分別獲得了其精確值.對k≡1(mod 5)時,改進了其上界.當(dāng)n≡2(mod 4)且k≡3,4,0,1(mod 5)時,分別獲得其精確值.對k≡2(mod 5)時,改進了其上界.當(dāng)n≡3(mod 4),直接獲得了va3≡(Kn,n,n)的一個緊的上界.3.研究了一般圖的強平衡頂點k-蔭度問題.對于一般圖,給出了n個頂點的簡單圖的強平衡頂點k-蔭度的界1≤vak≡(G)≤[n/2],并且分別對達(dá)到vak≡(G)=1,cak≡(G)=[n/2]及vak≡(G)=[n/2]-1的圖進行了等價刻畫.同時,也獲得了關(guān)于一般圖的強平衡頂點k-蔭度的Nordhaus-Gaddum類型結(jié)果.4.研究了關(guān)于Cartesian積網(wǎng)絡(luò)的強平衡頂點k-蔭度問題.同時,也討論了阿貝爾群上度為3的Cayley圖的強平衡頂點k-蔭度.首先,討論了特殊圖類Cn,Pn和Petersen圖HP3的強平衡頂點k-蔭度.其次,對一般圖的Cartesian積網(wǎng)絡(luò),獲得了其強平衡頂點k-蔭度的上下界.接著,對于Cartesian積網(wǎng)絡(luò)Pn口pm(m≥ n≥2),Gn口Cm(m≥n≥3),Kn□Km(m,n≥3)和超Petersen網(wǎng)絡(luò)HP4討論了其強平衡頂點k-蔭度.最后,獲得了阿貝爾群上度為3的Cayley圖的強平衡頂點k-蔭度的精確值.
【關(guān)鍵詞】：平衡著色 (t k)-樹-著色 強平衡頂點蔭度 Nordhaus-Gaddum類型結(jié)果 Cartesian積網(wǎng)絡(luò)
【學(xué)位授予單位】：青海師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 中文摘要3-5
• 英文摘要5-10
• 第一章 緒論10-16
• § 1.1 引言10-11
• § 1.2 基本概念及術(shù)語11-12
• § 1.3 關(guān)于圖的頂點蔭度的研究進展12-13
• § 1.4 本文的主要研究結(jié)果13-15
• § 1.5 本論文的結(jié)構(gòu)15-16
• 第二章 完全二部圖的強平衡頂點蔭度16-24
• § 2.1 K_(n,n+1)的強平衡頂點1-蔭度16-21
• § 2.2 K_(n,n+(?))的強平衡頂點2-蔭度21-24
• 第三章 完全等部三部圖的強平衡頂點蔭度24-54
• § 3.1 K_(n,n,n)的強平衡頂點2-蔭度24-33
• § 3.2 K_(n,n,n)的強平衡頂點3-蔭度33-54
• 第四章 一般圖的強平衡頂點蔭度54-62
• § 4.1 給定強平衡頂點k-蔭度的圖類54-59
• § 4.2 Nordhaus ? Gaddum類型問題59-62
• 第五章 Cartesian積網(wǎng)絡(luò)的強平衡頂點蔭度62-73
• § 5.1 關(guān)于特殊圖類的強平衡頂點k-蔭度63-65
• § 5.2 Cartesian積網(wǎng)絡(luò)的強平衡頂點k-蔭度65-73
• 第六章 總結(jié)及進一步研究的問題73-77
• § 6.1 總結(jié)73-75
• § 6.2 進一步研究的問題75-77
• 參考文獻77-80
• 致謝80-81
• 個人簡介81
• 學(xué)習(xí)經(jīng)歷81
• 研究成果81-82

，

本文編號：623822