Graphs with large paired-domination number
Graphs with large paired-domination number
复制标题
DOI：
10.1007/s10878-006-9014-8
复制
发表时间：
2006-10
影响因子：
1
通讯作者：
Michael A. Henning
中科院分区：
文献类型：
--
作者：
Michael A. Henning
本文继续研究Haynes和斯莱特（1998）网络32：199-206中提出的图的成对控制。无孤立点图的成对控制集是指其导出子图具有完美匹配的顶点的控制集。G的成对控制数是G的成对控制集的最小基数，记为。设G是一个连通图，其最小度至少为2. Haynes和斯莱特（1998）网络32：199-206，表明ifn≥ 6，则。在本文中，我们证明了，正好有十个图，实现平等在这个界限。当n ≥ 14时，我们证明了这一点，并刻画了在这一界中达到相等的图的（无限族）.
In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (1998) Networks 32: 199–206. A paired-dominating set of a graphGwith no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number ofG, denoted by, is the minimum cardinality of a paired-dominating set ofG. LetGbe a connected graph of ordernwith minimum degree at least two. Haynes and Slater (1998) Networks 32: 199–206, showed that ifn≥ 6, then. In this paper, we show that there are exactly ten graphs that achieve equality in this bound. Forn≥ 14, we show thatand we characterize the (infinite family of) graphs that achieve equality in this bound.