Total dominating sequences in graphs

A vertex in a graph totally dominates another vertex if they are adjacent. A sequence of vertices in a graph GG is called a total dominating sequence if every vertex vv in the sequence totally dominates at least one vertex that was not totally dominated by any vertex that precedes vv in the sequence, and at the end all vertices of GG are totally dominated. While the length of a shortest such sequence is the total domination number of GG, in this paper we investigate total dominating sequences of maximum length, which we call the Grundy total domination number, γgrt(G), of GG. We provide a characterization of the graphs GG for which γgrt(G)=|V(G)| and of those for which γgrt(G)=2. We show that if TT is a nontrivial tree of order  nn with no vertex with two or more leaf-neighbors, then γgrt(T)≥23(n+1), and characterize the extremal trees. We also prove that for k≥3k≥3, if GG is a connected kk-regular graph of order  nn different from Kk,kKk,k, then γgrt(G)≥(n+⌈k2⌉−2)/(k−1) if GG is not bipartite and γgrt(G)≥(n+2⌈k2⌉−4)/(k−1) if GG 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.