張超

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

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

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

一、引 言

一個(gè)集合SV（G）若被稱為圖G的支配集（Dominating Set）[1]，則有任意的頂點(diǎn)v或者在S中或者與S中的點(diǎn)相鄰接.我們把頂點(diǎn)數(shù)目最少的支配集稱為圖的最小支配集（Minimum Dominating Set），它的頂點(diǎn)數(shù)目稱為圖的支配數(shù)（Dominating Number），記作γ（G）.對(duì)于支配集S，若有任意的點(diǎn)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圖表示一個(gè)樹圖中，度數(shù)大于等于3的頂點(diǎn)個(gè)數(shù)最多為1個(gè)，稱其為中心點(diǎn).

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

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

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

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

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

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

三、近似算

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

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

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

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

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

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

（3）記錄點(diǎn)集C=C∪W，C=V-C；

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

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

四、結(jié)束語(yǔ)

對(duì)于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ù)測(cè)[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.