若干類圖支配問題的研究.pdf

1、圖的支配及其相關(guān)問題是近年來圖論中一個比較活躍的研究領(lǐng)域，它是由實際應(yīng)用領(lǐng)域提出來的.研究它不僅有重要的理論意義，而且在通訊網(wǎng)絡(luò)的設(shè)計與分析、社會科學(xué)、優(yōu)化理論、計算的復(fù)雜性和算法設(shè)計等諸多領(lǐng)域也有廣泛的應(yīng)用.本文對圖的支配數(shù)(DominAtion number)及其相關(guān)問題即圖的Packing數(shù)(Packing number)、圖的羅馬支配數(shù)(Roman domination number)以及圖的符號邊支配數(shù)(signed edge

2、 dominationnulnber)等問題進(jìn)行了較深入的研究，取得了較好的成果. 圖的支配問題是近年來圖論領(lǐng)域中的核心問題之一.目前為止僅知道很少的幾類圖的支配數(shù)，例如完全圖、完全二分圖、路徑、圈、星、冠圖以及部分笛卡兒乘積圖等.本文對圖的支配數(shù)進(jìn)行了研究，提出了重復(fù)支配數(shù)的概念，將計算圖的支配數(shù)問題轉(zhuǎn)化為計算圖的重復(fù)支配數(shù)問題，從而給出了廣義Petersen圖p(n,k)(k=2，3)、循環(huán)圖c(n：{1，k})(k=2，3

3、，4)的支配數(shù)，并給出了廣義Petersen圖P(n,k)(k為奇數(shù))支配數(shù)的一個較好的界. 圖的Packing數(shù)和圖的支配數(shù)密切相關(guān).Fisher D C對圖的Packing數(shù)進(jìn)行了研究，并給出了路徑、圈、完全二分圖以及完全格圖(complete grid graphs)的Packing數(shù).本文給出了廣義Petersen圖P(n，k)(k=1，2，3)的Packing數(shù)以及循環(huán)圖c(n；{1，k))的Packing數(shù)的一個較好

4、的界. 圖的羅馬支配問題是圖的支配相關(guān)問題中一個較新的問題.Cockayne E J等研究了圖的羅馬支配數(shù)，給出了路徑、圈、完全圖、完全二分圖的羅馬支配數(shù)，并證明了如下的幾類圖是羅馬圖：當(dāng)k≥1時，P3k，P3k+2，C3k，C3k+2是羅馬圖；當(dāng)min{m，n)≠2時，Km,n是羅馬圖.本文給出了廣義Petersen圖P(n，k)(k=1，2，3)、循環(huán)圖c(n；{1，k))(k=2，3，4)以及笛卡兒乘積圖C5m口5n的羅馬

5、支配數(shù)，并證明了當(dāng)n>3且n≠2 rood 4時廣義Petersen圖P(n，1)是羅馬圖：當(dāng)n=11或n≥7且n≠3 rood 4時廣義Petersen圖P(n，3)是羅馬圖；當(dāng)n=0 mod 4且0≤k≤[n-1/2]/2時廣義Petersen圖P(N,2K+1)是羅馬圖：當(dāng)n≥7且n≠4 rood 5時循環(huán)圖c(n；{1,3})是羅馬圖；當(dāng)n≥4(n≠2k)且n≠1 mod(2k+1)時循環(huán)圖c(n；{1，2，3….，k})是羅馬

6、圖以及當(dāng)m，n ≥ l時笛卡兒乘積圖C5m□5n是羅馬圖. 圖的符號邊支配問題也是圖的支配相關(guān)問題中一個較新的問題.徐保根等研究了圖符號邊支配數(shù)，并證明了對任意的n(n≥4)階圖G有，vs(G)≤[11/6n-1]本文構(gòu)造出了一類符號邊支配數(shù)為rs(Gm,k)=-k(m-1)(km+k+1)/2(k≥1)的k-連通圖Gm,k9從而證明了存在一類k-連通圖，它的符號邊支配數(shù)可以任意小.這個結(jié)論也證明了徐保根提出的2-連通圖的符號邊