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

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

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