On exact \(n\)-step domination
type: Item
instance of: scholarly article
title: On exact \(n\)-step domination
zbMATH Open document ID: 0940.05048
DOI: 10.1016/S0012-365X(99)00024-2
author: Patricia Hersh
published in: Discrete Mathematics
publication date: 2000-07-13T00:00:00Z
review text: The author defines a set \(S\subset V\) as exact \(n\)-step dominating the graph \(G=(V,E)\) if for each vertex \(v\in V\) there is a unique vertex \(s\in S\) that has distance \(n\) to \(v\). Thus if \(S\) is an exact \(n\)-step dominating set, the graph is partitioned in metric spheres of radius \(n\) with centers in \(S\). This generalizes the exact 2-step domination of \textit{G. Chatrand}, \textit{F. Harary}, \textit{M. Hossain}, and \textit{K. Schultz} [Math. Bohem. 120, No.~2, 125-134 (1995; Zbl 0863.05050)]. The author proves some properties of exact \(n\)-step dominating sets and the underlying graphs, among them that all \(n\)-step dominating sets of a graph have the same cardinality and that the cardinality of an exact \(n\)-step dominating set is at least \(\lfloor \log_2 n\rfloor + 2\). Also the author obtains the following result which was conjectured in \textit{Y. Alavi, D. R. Lick} and \textit{H. B. Zou} [Second order degree regular graphs. Graph theory, combinatorics, and applications, Vol.~1, 1-8 (1991; Zbl 0841.05080)]: If each vertex in a connected graph \(G\) has exactly one vertex at distance \(n\) to it, then the diameter of \(G\) is \(n\), or \(G\) is a path \(P_{2n}\).
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1334692
zbMATH Keywords: domination
zbMATH Keywords: exact domination
zbMATH Keywords: distance in graphs
zbMATH Keywords: partitioning in spheres
zbMATH Keywords: distance
zbMATH Keywords: dominating set
reviewed by: Peter Brass
MaRDI profile type: Publication
cites work: Q4873785
cites work: Exact $2$-step domination in graphs
cites work: On exact \(n\)-step domination.
description: scientific article; zbMATH DE number 1334692