Total dominating sequences in graphs

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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,

g a m m a_{m g r}^{t} (G)

, of

G

. We provide a characterization of the graphs

G

for which

g a m m a_{m g r}^{t} (G) = | V (G) |

and of those for which

g a m m a_{m g r}^{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

g a m m a_{m g r}^{t} (T) g e f r a c 23 (n + 1)

, and characterize the extremal trees. We also prove that for

k g e 3

, if

G

is a connected

k

-regular graph of order~

n

different from

K_{k, k}

, then

g a m m a_{m g r}^{t} (G) g e (n + l c e i l f r a c k 2 c e i l - 2) / (k - 1)

if

G

is not bipartite and

g a m m a_{m g r}^{t} (G) g e (n + 2 l c e i l f r a c k 2 c e i l - 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.

Recommendations

Cites work

Cited in

(29)

This page was built for publication: Total dominating sequences in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q267175)