2021/02/22 by Kelenc, Aleksander, Toshi, Aoden Teo Masa, Skrekovski, Riste +1 · 1 citation
#05C12 #05C76 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2102.10916
The metric (resp. edge metric or mixed metric) dimension of a graph G, is the cardinality of the smallest ordered set of vertices that uniquely recognizes all the pairs of distinct vertices (resp. edges, or vertices and edges) of G by using a vector of distances to this set. In this note we show two unexpected results on hypercube graphs. First, we show that the metric and edge metric dimension of Qd differ by only one for every integer d. In particular, if d is odd, then the metric and edge metric dimensions of Qd are equal. Second, we prove that the metric and mixed metric dimensions of the hypercube Qd are equal for every d ≥ 3. We conclude the paper by conjecturing that all these three types of metric dimensions of Qd are equal when d is large enough.