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, University of Mohaghegh Ardabili, Ardabil, Iran.

3 Department of Mathematics, Yazd University, Yazd, Iran.

10.22060/ajmc.2020.18444.1035

Abstract

Let $G=(V,E)$ be a simple graph without isolated vertices. A set $Dsubset 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