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

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

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

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

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