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


BAHADIR S. , Gözüpek D., Doğan O.

Discrete Mathematics, vol.344, no.9, 2021 (Journal Indexed in SCI Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 344 Issue: 9
  • Publication Date: 2021
  • Doi Number: 10.1016/j.disc.2021.112492
  • Title of Journal : Discrete Mathematics

Abstract

© 2021 Elsevier B.V.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 γt(G)) and the Grundy total domination number of G (denoted by γgrt(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, γt(G)=γgrt(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.