【摘要】 设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．更多还原

【Abstract】 Let G=(V,E) be a simple graph. For a subset S■V, let G[S] denote the subgraph of G induced by S. 5 is a paired-dominating set of G if S is a dominating set of G and 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.更多还原