Metric Dimension of a Direct Product of Three Complete Graphs

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 gener...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2024-04, Vol.31 (2)
Main Authors: Foster-Greenwood, Briana, Uhl, Christine
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1077-8926
1077-8926
DOI:10.37236/12399