Labeling resolving sets

Let $G$ be a simple, connected graph, $W \subseteq V (G)$ and $L : W \to \lbrace 1, 2, \dotsc, m \rbrace$. For $v \in V (G)$, define $v[i] = \lbrace d(u, v) \vert u \in L^{-1}[i] \rbrace$ and $R(v \vert L) = (v[1], v[2], \dotsc, v[m])$. The labeling $L$ is $m$-tracked if for any $v,w \in V (G)$ where $R(v \vert L) = R(w \vert L), v = w$. The minimum m such that $G$ has an $m$-tracked labeling is the graph’s tracking dimension $(\mathrm{Trac}(G))$. Tracked labelings are an extension of resolving sets, which were defined independently by Slater (1975) and Harary and Melter (1976). W is a resolving set if for every distinct pair $u, v \in V (G)$, there exists $x \in W$ where $d(x, u) \neq d(x, v)$. Albertson and Collins (1996) defined a labeling of the entire vertex set to be distinguishing if no nontrivial automorphism preserves the labels. The graph’s distinguishing number $(\mathrm{Dist}(G))$ is the minimum number of labels needed to have a distinguishing labeling. Tracked labelings must also break the graph’s symmetries, and in this way, bridge distinguishing labelings and resolving sets. We show that $\mathrm{Trac}(G) \geq \mathrm{Dist}(G)- 1$. For $n \gt 5$, we show $\mathrm{Trac}(C_n)$ achieves the lower bound, but for complements of cycles, $\mathrm{Trac}(G) - \mathrm{Dist}(G)$ can be arbitrarily large. For complete multipartite graphs, we show $\mathrm{Dist}(G) -1 \leq \mathrm{Trac}(G) \leq \mathrm{Dist}(G)$.

Keywords

determining number, distinguishing number, metric dimension, resolving sets

Full Text (PDF format)

Received 3 July 2018

Accepted 23 July 2019

Published 9 October 2020