On graphs all of whose total dominating sequences have the same length

Abstract

A sequence of vertices in a graph G without isolated vertices is called a total dominating sequence if every vertex v in the sequence has a neighbor which is adjacent to no vertex preceding v in the sequence, and at the end every vertex of G has at least one neighbor in the sequence. Minimum and maximum lengths of a total dominating sequence is the total domination number of G (denoted by gamma(t)(G)) and the Grundy total domination number of G (denoted by gamma(t)(gr)(G)), respectively. In this paper, we study graphs where all total dominating sequences have the same length. For every positive integer k, we call G a total k-uniform graph if every total dominating sequence of G is of length k, that is, gamma(t)(G) = gamma(t)(gr)(G) = k. We prove that there is no total k-uniform graph when k is odd. In addition, we present a total 4-uniform graph which stands as a counterexample for a conjecture by [11] and provide a connected total 8-uniform graph. Moreover, we prove that every total k-uniform, connected and false twin-free graph is regular for every even k. We also show that there is no total k-uniform chordal connected graph with k >= 4 and characterize all total k-uniform chordal graphs. (C) 2021 Elsevier B.V. All rights reserved.