Metric Dimension of a Diagonal Family of Generalized Hamming Graphs

DOI10.37236/12399MaRDI QIDQ6406768zbMATH OpenFDO

Authors Briana Foster-Greenwood, Christine Uhl

Publication date 2 August 2022

Full work available at URL https://doi.org/10.37236/12399

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Hypergraphs (05C65) Graph operations (line graphs, products, etc.) (05C76)

Abstract: 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. 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.

Recommendations

• On the metric dimension of Cartesian powers of a graph
• On the metric dimension of Cartesian products of graphs
• The metric dimension of Cartesian products of graphs
• On the Metric Dimension of Cartesian Products of Graphs
• Resolvability in graphs and the metric dimension of a graph

Cited in

(4)

• On the vertices belonging to all edge metric bases
• On a tight bound for the maximum number of vertices that belong to every metric basis
• Metric dimension of a direct product of three complete graphs: the middle cone family
• On the weak k-metric dimension of Hamming graphs

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Metric Dimension of a Diagonal Family of Generalized Hamming Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6406768)