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

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

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

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