Upper Bounds for the Paired-Domination Numbers of Graphs

详细信息    查看全文

• 作者：Changhong Lu ; Chao Wang ; Kan Wang
• 刊名：Graphs and Combinatorics
• 出版年：2016
• 出版时间：July 2016
• 年：2016
• 卷：32
• 期：4
• 页码：1489-1494
• 全文大小：356 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914
• 卷排序：32

文摘

A set \(S\subseteq V\) is a paired-dominating set if every vertex in \(V{\setminus } S\) has at least one neighbor in S and the subgraph induced by S contains a perfect matching. The paired-domination number of a graph G, denoted by \(\gamma _{pr}(G)\), is the minimum cardinality of a paired-dominating set of G. A conjecture of Goddard and Henning says that if G is not the Petersen graph and is a connected graph of order n with minimum degree \(\delta (G)\ge 3\), then \(\gamma _{pr}(G)\le 4n/7\). In this paper, we confirm this conjecture for k-regular graphs with \(k\ge 4\).KeywordsPaired-dominationRegular graphDominating set