Spider图的[1，2]—支配数研究

张超

【摘要】图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]-集的性质及树的……