Classical Hamming graphs are Cartesian products of complete graphs, and two vertices are adjacent if they differ in exactly one coordinate. Motivated by connections to unitary Cayley graphs, we consider a generalization where two vertices are adjacent if they have no coordinate in common. This generalization is equivalent to a direct product of complete graphs. Metric dimension of classical Hamming graphs is known asymptotically, but, even in the case of hypercubes, few exact values have been found. In contrast, we determine the metric dimension for the entire diagonal family of 3-dimensional generalized Hamming graphs. Our approach is constructive and made possible by first characterizing resolving sets in terms of forbidden subgraphs of an auxiliary edge-colored hypergraph.
@article{10_37236_12399,
author = {Briana Foster-Greenwood and Christine Uhl},
title = {Metric dimension of a direct product of three complete graphs},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {2},
doi = {10.37236/12399},
zbl = {1536.05398},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12399/}
}
TY - JOUR
AU - Briana Foster-Greenwood
AU - Christine Uhl
TI - Metric dimension of a direct product of three complete graphs
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/12399/
DO - 10.37236/12399
ID - 10_37236_12399
ER -
%0 Journal Article
%A Briana Foster-Greenwood
%A Christine Uhl
%T Metric dimension of a direct product of three complete graphs
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/12399/
%R 10.37236/12399
%F 10_37236_12399
Briana Foster-Greenwood; Christine Uhl. Metric dimension of a direct product of three complete graphs. The electronic journal of combinatorics, Tome 31 (2024) no. 2. doi: 10.37236/12399
