立方图的对控制数

数学物理学报

立方图的对控制数

陈学刚; 孙良; 邢化明

华北电力大学数学系北京 102206

收稿日期:2005-02-20 修回日期:2006-03-25 出版日期:2007-02-25 发布日期:2007-02-25
通讯作者: 陈学刚

Paired-domination Number in Cubic Graphs

Chen Xuegang; Sun Liang; Xing Huaming

Department of Mathematics, North China Electric Power University, Beijing 102206

Received:2005-02-20 Revised:2006-03-25 Online:2007-02-25 Published:2007-02-25
Contact: Chen Xuegang

摘要/Abstract

摘要： 设G=(V,E)是一个简单图, 对任意的顶点子集合 $S\subseteq 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\subseteq 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 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.

Key words: Paired domination number, Cubic graph, Private neighbor

中图分类号:

05C05

陈学刚; 孙良; 邢化明. 立方图的对控制数[J]. 数学物理学报, 2007, 27(1): 166-170.

Chen Xuegang; Sun Liang; Xing Huaming. Paired-domination Number in Cubic Graphs[J]. Acta mathematica scientia,Series A, 2007, 27(1): 166-170.

[1]	陈东; 王维凡. 一些图的生成树数[J]. 数学物理学报, 2008, 28(5): 906-913.
[2]	聂晓冬, 刘红美, 徐俊明. Star图互连网络的容错性分析[J]. 数学物理学报, 2004, 24(2): 168-176.
[3]	陈协彬. 路或圈的笛卡尔乘积图的支撑树数[J]. 数学物理学报, 2003, 23(1): 70-76.