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

doi:10.15960/j.cnki.issn.1007-6093.2017.01.013

Abstract

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

Cite this article

LI Shan, SHAN Erfang, ZHANG Lin. A note on total domination in 5-regular graphs[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2017.01.013.

share this article

0
/ / Recommend

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2017.01.013

https://www.ort.shu.edu.cn/EN/Y2017/V21/I1/125

References

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

Related Articles 15

[1]	REN Yequan, BAI Yanqin, LI Qian, YU Changjun, ZHANG Liansheng. A second-order cone programming algorithm for pooling problem [J]. Operations Research Transactions, 2020, 24(2): 61-72.
[2]	LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao. On-line bounded-batching scheduling of unit-length jobs with two families [J]. Operations Research Transactions, 2019, 23(4): 105-110.
[3]	LI Tong, WANG Guanghui, ZHOU Wenling. A survey on rainbow matchings in graphs and hypergraphs [J]. Operations Research Transactions, 2019, 23(3): 77-90.
[4]	TAO Yanliang, HUANG Qiongxiang, CHEN Lin. Contraction graph method for the interval edge-colorings of graphs [J]. Operations Research Transactions, 2019, 23(2): 31-43.
[5]	PEI Jianfeng, LIN Shangwei. Two sufficient conditions for maximally restricted-edge-connected hypergraphs [J]. Operations Research Transactions, 2019, 23(2): 120-126.
[6]	CAI Shuang, YANG Ke, LIU Ke. Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints [J]. Operations Research Transactions, 2018, 22(4): 17-30.
[7]	GAO Leifu, ZHANG Yahong. A penalized FB function for symmetric cone complementarity problems [J]. Operations Research Transactions, 2018, 22(3): 125-131.
[8]	HE Simai, JIN Yujia, WANG Hua, GE Dongdong. A survey on online learning methods: Thompson sampling and others [J]. Operations Research Transactions, 2017, 21(4): 84-102.
[9]	YANG Guanghui, YANG Hui, XIANG Shuwen. Stability of solutions to parametric optimization problems under bounded rationality [J]. Operations Research Transactions, 2016, 20(4): 1-10.
[10]	WANG Chun, QIU Xiaoling, WANG Nengfa, CHEN Pinbo. Stability to bounded rationality for nonconvexity [J]. Operations Research Transactions, 2016, 20(3): 107-120.
[11]	LIN Yi, NI Zhenyu, SHAN Erfang. Total transversals in 5-uniform hypergraphs [J]. Operations Research Transactions, 2016, 20(2): 97-104.
[12]	ZHANG Xinyue, HUANG Zhenghai, LI Zhiming. A face recognition method based on discriminative hypergraph and nonnegative matrix factorization [J]. Operations Research Transactions, 2015, 19(3): 108-115.
[13]	TANG Guochun, LIU Xiaohui. Applications of operations research in automotive parts inbound logistics [J]. Operations Research Transactions, 2015, 19(3): 123-130.
[14]	LIU Yuanwen, OU Yigui. A hybrid method for a system of nonlinear equations with bound constraints [J]. Operations Research Transactions, 2015, 19(1): 45-56.
[15]	ZHANG Huizhen, WEI Xin, MA Liang. The bounded simplex method to solve the 0-1 linear integer programming problem [J]. Operations Research Transactions, 2014, 18(3): 71-78.

Metrics

Viewed

Full text

Abstract

Comments

Abstract
References
Related Articles
Recommended Articles
Metrics
Comments

TOP

A note on total domination in 5-regular graphs

PDF

Knowledge

Cited