Uniform Length Dominating Sequence Graphs

Abstract

A sequence of vertices (nu(1), ... , nu(k)) of a graph G is called a dominating closed neighborhood sequence if {nu(1), ... , v(k)} is a dominating set of G and N [nu(i)] subset of boolean OR(i-1)(j=1) N[nu(j)] for every i. A graph G is said to be k-uniform if all dominating closed neighborhood sequences in the graph have equal length k. Bresar et al. (Discrete Math 336:22-36, 2014) characterized k-uniform graphs with k <= 3. In this article we extend their work by giving a complete characterization of all k-uniform graphs with k >= 4.