On the Metric Dimensions for Sets of Vertices

Abstract

Resolving sets were originally designed to locate vertices of a graph one at a time. For the purpose of locating multiple vertices of the graph simultaneously, {ℓ}-resolving sets were recently introduced. In this paper, we present new results regarding the {ℓ}-resolving sets of a graph. In addition to proving general results, we consider {2}-resolving sets in rook’s graphs and connect them to block designs. We also introduce the concept of ℓ-solid-resolving sets, which is a natural generalisation of solid-resolving sets. We prove some general bounds and characterisations for ℓ-solid-resolving sets and show how ℓ-solid- and {ℓ}-resolving sets are connected to each other. In the last part of the paper, we focus on the infinite graph family of flower snarks. We consider the ℓ-solid- and {ℓ}-metric dimensions of flower snarks. In two proofs regarding flower snarks, we use a new computer-aided reduction-like approach.

Keywords

• resolving set
• metric dimension
• resolving several objects
• block design
• rook’s graph
• flower snark
• 05c12
• 05c69