English

运筹学学报

• 运筹学 • 上一篇    

5-正则图的全控制数的一个注记

李姗1  单而芳2,*  张琳1   

  1. 1. 上海大学数学系, 上海 200444;   2. 上海大学管理学院, 上海 200444 
  • 收稿日期:2016-07-24 出版日期:2017-03-15 发布日期:2017-03-15
  • 通讯作者: 单而芳 efshan@shu.edu.cn
  • 基金资助:

    国家自然科学基金 (Nos. 11571222, 11471210)

A note on total domination in 5-regular graphs

LI Shan1  SHAN Erfang2,*  ZHANG Lin1   

  1. 1. Department of Mathematics,   Shanghai University,  Shanghai 200444,  China; 2. School of Management,   Shanghai University, Shanghai 200444,  China
  • Received:2016-07-24 Online:2017-03-15 Published:2017-03-15

PDF

415

摘要：

设G是不含孤立点的图, S是G的一个顶点子集, 若G的每一个顶点都与S中的某顶点邻接, 则称S是G的全控制集. G的最小全控制集所含顶点的个数称为G的全控制数, 记为\gamma_t(G). Thomass\'e~和Yeo证明了若G是最小度至少为5的n阶连通图, 则\gamma_t(G)\le 17n/44. 在5-正则图上改进了Thomass\'e和Yeo的结论, 证明了若G是n阶5-正则图, 则\gamma_t(G)\le 106n/275.

关键词: 全控制集, 正则图, 超图, 界

Abstract:

Let G be a graph without isolated vertices. A total dominating set of G is a subset S of V(G) such that every vertex of G is adjacent to a vertex in S. The minimum cardinality of a total dominating set of G is denoted by \gamma_t(G). Recently, Thomass\'e and Yeo showed that \gamma_t(G)\le 17n/44 for a connected graph G of order n with minimum degree at least five. In this paper we prove that \gamma_t(G)\le 106n/275 for a 5-regular graph G of order n, which improves sightly the bound of Thomass\'e and Yeo.

Key words: total domination, regular graph, hypergraph, bound