张超

【摘要】图G的一个点集S是一个[1，2]-支配集，则有每个不在S中的点满足至少与S中的1个点且至多与S中的2个点相邻.通过分析，证明Spider图的支配数性质结论.并讨论一种计算[1，2]-数的近似算法.

【关键词】Spider图；[1，2]-支配数；近似算法

【基金项目】南京工业大学浦江学院科研项目（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中顶点数.

该算法可以有效地提高计算效率，在顶点数目很庞大的网络结构图的运算中很有优势.

四、结束语

对于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.