張超

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

【關鍵詞】Spider圖；[1，2]-支配數；近似算法

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

一、引 言

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

二、Spider圖的[1，2]支配數性質

結論 Spider圖[1，2]-支配數滿足γ（G）=γ[1，2]（G）.

證明 Spider圖表示一個樹圖中，度數大于等于3的頂點個數最多為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分支上的葉子結點作為[1，2]-支配集，這樣可以滿足γ（G）=γ[1，2]（G）.

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

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

三、近似算

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

算法 尋找TREE圖的最大度點分解圖形結構進行計算.

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

輸出 [1，2]-集C的階數.

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

（2）若W為孤立點集，則進行下一步，否則重復步驟1；

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

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

該算法可以有效地提高計算效率，在頂點數目很龐大的網絡結構圖的運算中很有優(yōu)勢.

四、結束語

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

【參考文獻】

[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]呂琳媛，周濤.鏈路預測[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.