A linear-time algorithm to compute total [1,2]-domination number of block graphs

Document Type : Original Article

Authors

1 Institute for Research in Fundamental Sciences (IPM), Tehran, Iran

2 Department of Computer Science, Yazd University, Yazd, Iran

3 Department of Computer Science, University of Mohaghegh Ardabili, Ardabil, Iran

4 Department of Mathematics, Yazd University, Yazd, Iran

Abstract

Let G=(V,E) be a simple graph without isolated vertices. A set D⊆V is a total [1,2]-dominating set if for every vertex v∈V,1≤|N(v)∩D|≤2. The total [1,2]-domination problem is to determine the total [1,2]-domination number γt[1,2](G), which is the minimum cardinality of a total [1,2]-dominating set for a graph G. In this paper, we present a linear-time algorithm to compute γt[1,2](G), for a block graph G.

Keywords

Main Subjects

References

[1] A. V. Aho, J. E. Hopcroft, The design and analysis of computer algorithms, Pearson Education India (1974).
[2] A. Bishnu, K. Dutta, A. Gosh, S. Pual, [1,j]-set problem in graphs, Discrete Mathematics 339 (2016), 2215- 2525.
[3] M. Chellali, O. Favaron, T. W. Haynes, S. T. Hedetniemi, A. McRae, Independent [1, k]-sets in graphs, Australasian Journal of Combinatorics 59, 1 (2014), 144-156.
[4] M. Chellali, T. W. Haynes, S. T. Hedetniemi, A. McRae, [1, 2]-sets in graphs, Discrete Applied Mathematics 161, 18 (2013), 2885-2893.
[5] O. Etesami, N. Ghareghani, M. Habib, M. R. Hooshmandasl, R. Naserasr, P. Sharifani, When an optimal dominating set with given constraints exists, Theoretical Computer Science, 780 (2019), 54-65.
[6] A. K. Goharshady, M. R. Hooshmandasl, M. Alambardar Meybodi, [1, 2]-sets and [1, 2]-total sets in trees with algorithms, Discrete Applied Mathematics, 198 (2016), 136-146.
[7] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of domination in graphs, CRC Press, 1998.
[8] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Domination in graphs: advanced topics, Marcel Dekker, 1998.
[9] S. T. Hedetniemi, R. Laskar, Topics on domination, Elsevier, 1991.
[10] D. B. West, Introduction to graph theory, 2ed Edition. Prentice hall Upper Saddle River, 2001.
[11] X. Yang, B. Wu, [1, 2]-domination in graphs, Discrete Applied Mathematics, 175 (2014), 79-86.
AUT Journal of Mathematics and Computing
Volume 1, Issue 2
September 2020
Pages 263-270

Files

Share

How to cite

Statistics