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

摘要

设G是不含孤立点的图,S是G的一个顶点子集,若G的每一个顶点都与S中的某顶点邻接,则称S是G的全控制集.G的最小全控制集所含顶点的个数称为G的全控制数,记为γt(G).Thomassé和Yeo证明了若G是最小度至少为5的n阶连通图,则γt(G)≤17n/44.在5-正则图上改进了Thomassé和Yeo的结论,证明了若G是n阶5-正则图,则γt(G)≤106n/275.%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 γt (G).Recently,Thomassé and Yeo showed that γt(G) ≤ 17n/44 for a connected graph G of order n with minimum degree at least five.In this paper we prove that γt(G) ≤ 106n/275 for a 5-regular graph G of order n,which improves sightly the bound of Thomassé and Yeo.