Minimum dominating walks on graphs with large circumference

Abstract

A dominating walk W in a graph G is a walk such that for each v ε V(G), either v ε V(W) or v is adjacent to a vertex of W. A minimum closed dominating walk (MCDW) is a dominating walk of shortest length that starts and ends at the same point. We construct a MCDW in two infinite families of graphs.