English

运筹学学报 >

2017 , Vol. 21 >Issue 1: 125 - 128

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2017.01.013

运筹学

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

展开
  • 1. 上海大学数学系, 上海 200444;   2. 上海大学管理学院, 上海 200444 

收稿日期: 2016-07-24

  网络出版日期: 2017-03-15

基金资助

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

收起

A note on total domination in 5-regular graphs

Expand
  • 1. Department of Mathematics,   Shanghai University,  Shanghai 200444,  China; 2. School of Management,   Shanghai University, Shanghai 200444,  China

Received date: 2016-07-24

  Online published: 2017-03-15

Fold

摘要

设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.

关键词： 全控制集; 正则图; 超图; 界

本文引用格式

李姗, 单而芳, 张琳 . 5-正则图的全控制数的一个注记[J]. 运筹学学报, 2017 , 21(1) : 125 -128 . DOI: 10.15960/j.cnki.issn.1007-6093.2017.01.013

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

参考文献

[1] Haynes T W, Hedetniemi S T, Slater P J. Fundamentals of Domination in Graphs [M]. New York: Marcel Dekker, 1998.
[2] Haynes T W, Hedetniemi S T, Slater P J. Domination in Graphs: Advanced Topics [M]. New York: Marcel Dekker, 1998.
[3] Cockayne E, Dawes R, Hedetniemi S. Total domination in graphs [J]. Networks, 1980, 10: 211-219.
[4] Henning M A, Yeo A.  Total Domination in Graphs [M]. New York: Springer, 2013.
[5] Dorfling M, Henning M A. Transversals in 5-uniform hypergraphs and total domination in graphs with minimum degree five [J]. Quaestiones Mathematicae, 2015, 38(2): 155-180.
[6] Brooks R L. On colouring the nodes of a network [J]. Mathematical Proceedings of the Cambridge Philosophical Society, 1941, 37: 194-197.
[7] Chv\'atal V, McDiarmid C. Small transversals in hypergraphs [J]. Combinatorica, 1992, 12: 19-26.
[8] Thomass\'e S, Yeo A. Total domination of graphs and small transversals of hypergraphs [J]. Combinatorica, 2007, 27: 473-487.
Options
文章导航

/

〈 〉