# Total Dominating Sequences in Graphs

Research paper by **Bostjan Bresar, Michael A. Henning, Douglas F. Rall**

Indexed on: **27 Jan '16**Published on: **27 Jan '16**Published in: **Mathematics - Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

A vertex in a graph totally dominates another vertex if they are adjacent. A
sequence of vertices in a graph $G$ is called a total dominating sequence if
every vertex $v$ in the sequence totally dominates at least one vertex that was
not totally dominated by any vertex that precedes $v$ in the sequence, and at
the end all vertices of $G$ are totally dominated. While the length of a
shortest such sequence is the total domination number of $G$, in this paper we
investigate total dominating sequences of maximum length, which we call the
Grundy total domination number, $\gamma_{\rm gr}^t(G)$, of $G$. We provide a
characterization of the graphs $G$ for which $\gamma_{\rm gr}^t(G)=|V(G)|$ and
of those for which $\gamma_{\rm gr}^t(G)=2$. We show that if $T$ is a
nontrivial tree of order~$n$ with no vertex with two or more leaf-neighbors,
then $\gamma_{\rm gr}^t(T) \ge \frac{2}{3}(n+1)$, and characterize the extremal
trees. We also prove that for $k \ge 3$, if $G$ is a connected $k$-regular
graph of order~$n$ different from $K_{k,k}$, then $\gamma_{\rm gr}^t(G) \ge (n
+ \lceil \frac{k}{2} \rceil - 2)/(k-1)$ if $G$ is not bipartite and
$\gamma_{\rm gr}^t(G) \ge (n + 2\lceil \frac{k}{2} \rceil - 4)/(k-1)$ if $G$ is
bipartite. The Grundy total domination number is proven to be bounded from
above by two times the Grundy domination number, while the former invariant can
be arbitrarily smaller than the latter. Finally, a natural connection with edge
covering sequences in hypergraphs is established, which in particular yields
the NP-completeness of the decision version of the Grundy total domination
number.