循環(huán)圖和廣義Petersen圖的支配參數(shù).pdf

1、圖的支配問(wèn)題是近年來(lái)圖論中一個(gè)比較活躍的研究領(lǐng)域，在網(wǎng)絡(luò)設(shè)計(jì)中有許多實(shí)際應(yīng)用。比如在一個(gè)通訊網(wǎng)絡(luò)的一些節(jié)點(diǎn)上放置發(fā)射器，要求每個(gè)發(fā)射器的節(jié)點(diǎn)一定和某個(gè)發(fā)射器的節(jié)點(diǎn)有一個(gè)直接的通訊線路。如何選擇節(jié)點(diǎn)使得放置的發(fā)射器的數(shù)目最小，就是一個(gè)支配數(shù)問(wèn)題。計(jì)算圖的支配數(shù)問(wèn)題屬于NP-完全問(wèn)題，因此至今只有少數(shù)類圖的支配數(shù)被找到并證明。 支配集是指集合S(∈)V(G)，對(duì)任意的頂點(diǎn)v∈V(G)，都有v∈S或著v和某點(diǎn)w鄰接，且w∈S.即，S是

2、一個(gè)支配集當(dāng)且僅當(dāng)M[S]=V(G).如果支配集S的任何真子集都不是圖G的支配集，則稱支配集S為圖G的一個(gè)極小支配集(minimal dominating set).如果對(duì)圖G的任意的一個(gè)極小支配集S*，滿足|S|≥|S|,則稱極小支配集S為圖G的一個(gè)最小支配集(minimum dominating set).最小支配集S中所含元素的個(gè)數(shù)稱為圖G的支配數(shù)(domination number)，記作γ(G). 獨(dú)立集是指集合S(∈

3、)V(G)，集合S內(nèi)不包含兩個(gè)鄰接的頂點(diǎn)。對(duì)于任何點(diǎn)集，如果其真子集是S，那么其都不是獨(dú)立的，那么稱S為圖G的極大獨(dú)立集(independent set).如果對(duì)圖G的任意一個(gè)極大獨(dú)立集S*(maximal independent set)，滿足|S*|≤|S|，則稱極大獨(dú)立集S為圖G一個(gè)最大獨(dú)立集(minimum independent set).最大獨(dú)立集S中所含元素的個(gè)數(shù)稱為圖G的獨(dú)立數(shù)(independence number)，

4、記作α(G). 本文利用計(jì)算機(jī)求出n和k比較小的廣義Petersen圖的獨(dú)立數(shù)和循環(huán)圖的支配數(shù)，并構(gòu)造出相應(yīng)的獨(dú)立集和支配集，從中找出規(guī)律，推出n和k較大時(shí)的獨(dú)立集和支配集，從而確定出循環(huán)圖C(n；{1，k})，n=3k,4k的支配數(shù)上確界和廣義Petersen圖P(n,k),k=1，2，3,5的獨(dú)立數(shù)的下確界。本文利用計(jì)算得的結(jié)果，并嚴(yán)格證明了循環(huán)圖C(n;{1，k})，n=3k，4k的支配數(shù)的下確界和廣義Petersen圖P