| 5-正则图的全控制数的一个注记 |
| |
| 引用本文： | 李姗,单而芳,张琳.5-正则图的全控制数的一个注记[J].运筹学学报,2017,21(1):125-128. |
| |
| 作者姓名： | 李姗 单而芳 张琳 |
| |
| 作者单位： | 1. 上海大学数学系, 上海 200444; 2. 上海大学管理学院, 上海 200444 |
| |
| 基金项目： | 国家自然科学基金 (Nos. 11571222, 11471210) |
| |
| 摘 要： | 设G是不含孤立点的图,S是G的一个顶点子集,若G的每一个顶点都与S中的某顶点邻接,则称S是G的全控制集.G的最小全控制集所含顶点的个数称为G的全控制数,记为γt(G).Thomasse和Yeo证明了若G是最小度至少为5的n阶连通图,则γt(G)≤17n/44.在5-正则图上改进了Thomasse和Yeo的结论,证明了若G是n阶5-正则图,则,γt(G)≤106n/275.
|
| 关 键 词： | 全控制集 正则图 超图 界 |
| 收稿时间： | 2016-07-24 |
A note on total domination in 5-regular graphs |
| |
| LI Shan,SHAN Erfang,ZHANG Lin.A note on total domination in 5-regular graphs[J].OR Transactions,2017,21(1):125-128. |
| |
| Authors: | LI Shan SHAN Erfang ZHANG Lin |
| |
| Institution: | 1. Department of Mathematics, Shanghai University, Shanghai 200444, China; 2. School of Management, Shanghai University, Shanghai 200444, China |
| |
| 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. |
| |
| Keywords: | total domination regular graph hypergraph bound |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
