Spider圖的[1，2]—支配數(shù)研究

張超

【摘要】圖G的一個點集S是一個[1，2]-支配集，則有每個不在S中的點滿足至少與S中的1個點且至多與S中的2個點相鄰.通過分析，證明Spider圖的支配數(shù)性質(zhì)結(jié)論.并討論一種計算[1，2]-數(shù)的近似算法.

【關(guān)鍵詞】Spider圖；[1，2]-支配數(shù)；近似算法

【基金項目】南京工業(yè)大學(xué)浦江學(xué)院科研項目（njpj-2016-2-02）.

一、引 言

一個集合SV（G）若被稱為圖G的支配集（Dominating Set）[1]，則有任意的頂點v或者在S中或者與S中的點相鄰接.我們把頂點數(shù)目最少的支配集稱為圖的最小支配集（Minimum Dominating Set），它的頂點數(shù)目稱為圖的支配數(shù)（Dominating Number），記作γ（G）.對于支配集S，若有任意的點v∈V（G）＼S滿足1≤|N（v）∩S|≤2，則此支配集S為圖G的[1，2]-集[2]，其最小階數(shù)即為圖的[1，2]-數(shù)（[1，2]-number），記作γ[1，2]（G）[3].

二、Spider圖的[1，2]支配數(shù)性質(zhì)

結(jié)論 Spider圖[1，2]-支配數(shù)滿足γ（G）=γ[1，2]（G）.

證明 Spider圖表示一個樹圖中，度數(shù)大于等于3的頂點個數(shù)最多為1個，稱其為中心點.

（1）若Spider圖含有一個P3m+1分支，那么滿足γ（G）=γ[1，2]（G）.

（2）若Spider圖所有分支都是P3m+2分支，則可以選定含有兩個2階頂點的一個[1，2]-支配集，仍滿足γ（G）=γ[1，2]（G）.

（3）若Spider圖含有一個或兩個P3m+2分支，而其余分支均為P3m，我們可以選定兩個P3m+2分支上的2階頂點和其他P3m分支的支撐點作為[1，2]-支配集，則滿足γ（G）=γ[1，2]（G）.

（4）若Spider圖至少含有3個P3m+2分支，而其余分支均為P3m，我們可以選定兩個P3m+2分支上的2階頂點，和其他P3m分支和P3m+2分支上的葉子結(jié)點作為[1，2]-支配集，這樣可以滿足γ（G）=γ[1，2]（G）.

（5）若Spider圖所有分支都是P3m分支，那么只有選取中心點和所有的支撐點作為[1，2]-支配集即可，滿足γ（G）=γ[1，2]（G）.

綜上分析，可以得出對于Spider圖[1，2]-支配數(shù)滿足γ（G）=γ[1，2]（G）.

三、近似算

Spider圖也是一種樹圖，分析計算樹的[1，2]-支配數(shù)[4]的近似算法.主要思想是利用貪婪策略，根據(jù)[1，2]-集的性質(zhì)及樹的特有結(jié)構(gòu)對樹進(jìn)行逐步分解，最后得到一系列點構(gòu)成樹的[1，2]-集.算法歸納如下：

算法 尋找TREE圖的最大度點分解圖形結(jié)構(gòu)進(jìn)行計算.

輸入 任意一個TREE圖的鄰接矩陣A，頂點數(shù)n.

輸出 [1，2]-集C的階數(shù).

（1）TREE圖中，選最大度點c，放入集合C，去掉c及所有與c鄰接的點，剩余點集為W=V-N[c]；

（2）若W為孤立點集，則進(jìn)行下一步，否則重復(fù)步驟1；

（3）記錄點集C=C∪W，C=V-C；

（4）檢查是否存在點u∈C，使得|N（u）∩C|≥3，則記C=C∪{u}，C=C-{u}，重復(fù)此步，直至這樣的點數(shù)為0，得到點集C中頂點數(shù).

該算法可以有效地提高計算效率，在頂點數(shù)目很龐大的網(wǎng)絡(luò)結(jié)構(gòu)圖的運(yùn)算中很有優(yōu)勢.

四、結(jié)束語

對于Spider圖的[1，2]-支配數(shù)進(jìn)行分析，證明其具有[1，2]-支配數(shù)等于支配數(shù)的結(jié)論，即γ（G）=γ[1，2]（G）.進(jìn)一步給出其近似算法.

【參考文獻(xiàn)】

[1]Bondy J A，Murty U S R.Graph theory with applications[M].London：The Macmillan Press Ltd，1976.

[2]Chellali M，Haynes T W，Hedetniemi S T，McRae A.[1，2]-sets in graphs[J].Discrete Applied Mathematics，2013（18）：2885-2893.

[3]呂琳媛，周濤.鏈路預(yù)測[M].北京：高等教育出版社，2013.

[4]Blidia M，Chellali M，Haynes T W.Characterizations of trees with equal paired and double domination numbers[J].Discrete Mathematics.2006（16）：1840-1845.