立方图的对控制数

Paired-domination Number in Cubic Graphs

设G=(V,E)是一个简单图,对任意的顶点子集合S■V,G[S]表示图G中由S所导出的子图．如果S是G的一个控制集并且G[S]包含至少一个完备匹配,则称S是G的一个对控制集．G中对控制集的最少的顶点数称为G的对控制数,记为γp(G)．该文证明了对任意有n点的连通立方图G,γp(G)≤(3n)/5．

Let G = （V,E） be a simple graph. For a subset S lohtain in V, let G[S] denote the subgraph of G induced by S. S is a paired-dominating set of G if S is a dominating set of Gand G[S] contains at least one perfect matching. The paired domination number, denoted by γp（G）, is the minimum cardinality of a paired dominating set of G. In this paper, the authors show that for any cubic graph G of order n, γp（G） ≤ 3n.5.