  The online dominating set problem is an online variant of the minimum
dominating set problem, which is one of the most important NP-hard problems on
graphs. This problem is defined as follows: Given an undirected graph $G = (V,
E)$, in which $V$ is a set of vertices and $E$ is a set of edges. We say that a
set $D \subseteq V$ of vertices is a {\em dominating set} of $G$ if for each $v
\in V \setminus D$, there exists a vertex $u \in D$ such that $\{ u, v \} \in
E$. The vertices are revealed to an online algorithm one by one over time. When
a vertex is revealed, edges between the vertex and vertices revealed in the
past are also revealed. A revelaed subtree is connected at any time.
Immediately after the revelation of each vertex, an online algorithm can choose
vertices which were already revealed irrevocably and must maintain a dominating
set of a graph revealed so far. The cost of an algorithm on a given tree is the
number of vertices chosen by it, and its objective is to minimize the cost.
Eidenbenz (Technical report, Institute of Theoretical Computer Science, ETH
Z\"{u}rich, 2002) and Boyar et al.\ (SWAT 2016) studied the case in which given
graphs are trees. They designed a deterministic online algorithm whose
competitive ratio is at most three, and proved that a lower bound on the
competitive ratio of any deterministic algorithm is two. In this paper, we also
focus on trees. We establish a matching lower bound for any deterministic
algorithm. Moreover, we design a randomized online algorithm whose competitive
ratio is at most $5/2 = 2.5$, and show that the competitive ratio of any
randomized algorithm is at least $4/3 \approx 1.333$.
