廣義Petersen圖和循環(huán)圖的連通支配研究.pdf

1、圖的連通支配問題是近幾年來圖論中的一個比較活躍的研究領(lǐng)域。圖的連通支配問題的研究不僅具有很重要的理論意義，而且在優(yōu)化理論、通訊網(wǎng)絡(luò)設(shè)計與分析、網(wǎng)絡(luò)搜索、模式識別等許多領(lǐng)域也有很廣泛的應(yīng)用。 自1979年E．Sampathkumar和H．B．Walikar提出連通支配的概念以來，針對連通支配問題人們展開了大量的研究，主要集中在兩個方面：一個方面是算法的研究及應(yīng)用，另一個方面是連通支配數(shù)性質(zhì)的研究。同時，由連通支配引出的全支配、臨界

2、支配、獨(dú)立支配、樹支配等相關(guān)概念，也引起人們的廣泛關(guān)注和研究。 廣義Petersen圖和循環(huán)圖C(n；{1，k})的連通支配數(shù)、樹支配數(shù)問題至今尚未完全解決，本文主要運(yùn)用計算機(jī)計算和數(shù)學(xué)推理證明相結(jié)合的方法，針對廣義Petersen圖P(n，k)和循環(huán)圖C(n；{1，k})的連通支配數(shù)和樹支配數(shù)進(jìn)行了研究，得到如下結(jié)論： 對任意的k≥1，n≥4，P(n，k)的連通支配數(shù)和樹支配數(shù)為：γ<,c>(P(n，k))=γ<,tr

3、>(P(n，k))。當(dāng)k=1，n≥4時，γ<,c>(P(n，1))=γ<,tr>(P(n，1))=n。當(dāng)k=2，n≥5且為奇數(shù)時，γ<,c>(P(n,2))=γ<,tr>(P(n，2))=n-1。當(dāng)k=2，n≥6且為偶數(shù)時，γ<,c>(P(n，2))=γ<,tr>(P(n，2))=n。當(dāng)k=4，n≥17時，γ<,c>(P(n，4))=γ<,tr>(P(n，4))=n-1。當(dāng)k=6，n≥25時，γ<,c>(P(n，6))=γ<,tr>(P