A Characterization of Block graphs that are Well-\(k\)-Dominated

Johannes H. Hattingh1, Michael A. Henning2
1Department of Mathematics Rand Afrikaans University P. O. Box 524, 2006 Aucklandpark, South Africa
2Department of Mathematics and Applied Mathematics University of Natal P. O. Box 375, 3200 Pietermaritzburg, South Africa

Abstract

Let \(k \geq 1\) be an integer and let \(G\) be a graph. A set \(D\) of vertices of \(G\) is a \(k\)-dominating set if every vertex of \(V(G) – D\) is within distance \(k\) of some vertex of \(D\). The graph \(G\) is called well-\(k\)-dominated if every minimal \(k\)-dominating set of \(G\) is of the same cardinality. A characterization of block graphs that are well-\(k\)-dominated is presented, where a block graph is a graph in which each of its blocks is complete.