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\subseteq V$ is a total $[1,2]$-dominating set if for every vertex $v\in V , 1\leq |N(v)\cap D|\leq 2$. The total $[1,2]$-domination problem is to determine the total $[1,2]$-domination number $\gamma_{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 $\gamma_{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