圖的支配臨界問題研究.pdf

1、圖論是組合數(shù)學的重要分支.圖論的廣泛應用，促進了它自身的發(fā)展.尤其是近幾十年來，隨著計算機技術的出現(xiàn)和進步，圖論理論有了飛速的發(fā)展并取得了驚人的成績. 圖的支配問題是近年來圖論中一個比較活躍的研究領域.圖的支配臨界問題是其中一類重要問題，它在網(wǎng)絡設計中有許多實際應用。對于圖G=(V，E)的頂點集V的子集S，如果對V中每個頂點或者在S中，或者與S中的某個頂點相鄰，則稱集合S是圖G的一個支配集.圖G的最小支配集元素的個數(shù)稱為其支配數(shù)，記為γ

2、(G).如果圖G的支配集S中的每個頂點至少與S中的另一個頂點相鄰，則S稱為圖G的一個全支配集.圖G的最小全支配集元素的個數(shù)稱為其全支配數(shù)，記為γt(G). 本文設計了計算圖的支配數(shù)及其相關問題的算法，利用該算法構(gòu)造出了一類k-(γ，2)-邊臨界圖，并給出了k-(γ，2)-邊臨界圖最小邊數(shù)的一個上界.然后對直徑為2的4-γt-點臨界圖進行了研究，并成功的構(gòu)造出了一個直徑為2的4-γt-點臨界圖，在此基礎上又進一步構(gòu)造出了一類k-