Rigid rotation in GR and a generalization of the virial theorem for
gravitomagnetism

Davide Astesianoa 111<EMAIL_ADDRESS>
a Department of Science and High Technology, Università dell’Insubria,

Via Valleggio 11, 22100, Como, Italy $\&$ INFN, sezione di Milano

Via Celoria 16, 20133, Milano, Italy

Abstract

In this work we study the properties of rigidly rotating neutral dust
solutions in general relativity. This class of solutions gained relevance
recently due to applications to the dynamics of spiral galaxies. We show that
this class could be interpreted as a “rigid body" in general relativity and we
analyze the different properties respect to the rigidly rotating disk in
special relativity: for example, the general relativistic counterpart shows no
Doppler effect for a light signal emitted and received from any two points at
rest respect to the “rigid body". This effect can be important to test the
validity of the assumed model for our galaxy.
In the second part we approach the problem from a low energy expansion
perspective and we write down a generalization of the virial theorem for
stationary spacetimes. The non-Newtonian contributions can lead to a re-
weighting of dark matter in galaxies.

x

##  1 Introduction

In the work [1] a tensor of deformations $\tilde{P}$ is introduced to define
covariant equations for “rigid-body" motions in special relativity. Using this
definition it is possible to show that a body which is rigidly rotating around
an axis satisfies the “linear speed-distance law" (2.17). We will use a
different definition for the deformation tensor respect to [1], eventually
reaching same conclusions. In the first part we review this construction in
order to study a generalization of the definition of rigid rotation around an
axis in a general relativistic context. To do this, we use dust as source for
the Einstein’s equations

$\displaystyle T=\rho\,u\otimes u,$ (1.1)

where $u$ is the four velocity field of the rotating body and $\rho$ its
density.
The class of solutions under consideration has gained relevance recently due
to applications to spiral galaxy models [2], [3],[4]. Our analysis shows that
these solutions are rigidly rotating even if they do not satisfy $r^{-1}v=$
constant, where the velocity $v$ is measured by the “zero angular momentum
observers" (ZAMO) [5].
In the second part we consider again dust solutions in general relativity,
without imposing the condition of rigid rotation. As well as writing down
exact solutions, one can describe these systems taking a gravito-magnetic
expansion approach as in [6] and [7]. In fact, in the second part we will
approach stationary solutions from a “low energy" expansion perspective and we
will provide a generalization of the Newtonian virial theorem in this general
relativistic context,which can be useful for galactic and extra-galactic
applications. Interestingly the relativistic modification of the theorem
presents an extra term which can reduce the required matter density to sustain
the motion of the dust compared to the Newtonian version of the same theorem.
In what follows we take $c=1,G=1$ and the signature is mostly plus.

##  2 Considerations on rigidly rotating dust

Here we consider a rotating disk around an axis in special relativity,
therefore neglecting its gravitational field.
Given a coordinate system $x^{\mu}$, in [1] the tensor of deformations
$\tilde{P}$ is defined as

$\displaystyle\tilde{P}_{\mu\nu}:=\frac{1}{2}\left(u_{\mu;\nu}+u_{\nu;\mu}+u_{\mu;\alpha}u^{\alpha}u_{\nu}+u_{\nu;\alpha}u^{\alpha}u_{\mu}\right),$
(2.1)

where $u^{\mu}$ is the four velocity field of the body. The condition for
rigid rotation adopted in [1] is $\tilde{P}_{\mu\nu}=0$:

$\displaystyle\left(u_{\mu;\nu}+u_{\nu;\mu}+u_{\mu;\alpha}u^{\alpha}u_{\nu}+u_{\nu;\alpha}u^{\alpha}u_{\mu}\right)=0.$
(2.2)

We are here taking a different perspective, eventually reaching the same
conclusions. We define the tensor of deformations $P$ as

$\displaystyle
P(u):=\mathcal{L}_{u}(g)=(u_{\mu;\nu}+u_{\nu;\mu})dx^{\mu}\otimes dx^{\nu},$
(2.3)

and its representation in covariant components read

$\displaystyle P_{\mu\nu}=u_{\mu;\nu}+u_{\nu;\mu}.$ (2.4)

If we now directly impose the nullity of $P$

$\displaystyle u_{\mu;\nu}+u_{\nu;\mu}=0,$ (2.5)

we obtain the Killing vector equations. If we want $u$ to be the four-velocity
of a real element of the body, then $(\ref{KillingCond})$ must be supplemented
by the condition $u^{\mu}u_{\mu}=-1$. In fact, the combination of these two
set of equations give the geodesic equation

$\displaystyle u^{\mu}u^{\nu}_{;\mu}=0.$ (2.6)

The class of solutions for $P=0$, plus the obvious condition
$u^{\mu}u_{\mu}=-1$, is a family of particles moving on straight lines.
Although this is clearly a rigid body motion, the condition $P=0$ is too
strong and does not allow for rigid rotation.
Let us now take a step back and consider the vector field given by the four
velocity of the body

$\displaystyle u=u^{\mu}\frac{\partial}{\partial{x^{\mu}}}.$ (2.7)

As it is well known, this vector field naturally defines a projection operator
on tensor fields at every point $x$. Its action on a vector $X$ is given by

$\displaystyle\mathcal{P}_{t}(X):=-u^{\mu}X_{\mu},\quad\mathcal{P}_{s}(X):=X+\mathcal{P}_{t}(X).$
(2.8)

For obvious reasons we can call $P_{t}(X)$ and $P_{s}(X)$ respectively the
temporal and the spatial projections of the vector field $X$ respect to $u$.
This action can be trivially extended on tensors with two indices if we
clearly state which index we are acting upon. In this sense, since we take
under consideration the deformation tensor field $P_{\mu\nu}$ in eq.(2.4)
which is symmetric, the action of $u$ is

$\displaystyle\mathcal{P}_{t}\mathcal{P}_{t}(P)$
$\displaystyle:=u^{\mu}P_{\mu\nu}u^{\nu}=0,$ (2.9)
$\displaystyle\mathcal{P}_{t}(P)$
$\displaystyle:=u^{\mu}P_{\mu\nu}=u^{\mu}u^{\nu}_{;\mu}.$ (2.10)

Therefore we can define the “spatial part" of the deformation tensor $P$ the
tensor

$\displaystyle\frac{1}{2}\left(u_{\mu;\nu}+u_{\nu;\mu}+u_{\mu;\alpha}u^{\alpha}u_{\nu}+u_{\nu;\alpha}u^{\alpha}u_{\mu}\right),$
(2.11)

which is exactly $\tilde{P}_{\mu\nu}$ in eq.(2.1). The term “spatial part"
clearly refers to the fact that it is orthogonal to $u$, in fact

$\displaystyle u^{\mu}\tilde{P}_{\mu\nu}=0,$ (2.12)

holds identically. The condition for rigid motion adopted in [1] is equivalent
to require that the projection perpendicular to $u$ of the deformation tensor
$P$ is zero, i.e. $\tilde{P}_{\mu\nu}=0$. From our perspective we are imposing
the rigid body condition on the space orthogonal to the four-velocity $u$ of
the elements of the rigid body.
In an inertial frame using cylindrical coordinates $(t,r,z,\phi)$, the
circular motion of a particle around the $\phi$-axis can be described as

$\displaystyle u^{0}=\sqrt{1+\sigma^{2}r^{2}},\qquad u^{x}=-\sigma y,\qquad
u^{y}=\sigma x,$ (2.13)

where $\sigma=\sigma(r)$ and $r^{2}=x^{2}+y^{2}$. As explained in [1],
inserting this into eq.(2.2) we get

$\displaystyle\frac{d\sigma}{dr}=\sigma^{3}r,$ (2.14)

which has for its solution

$\displaystyle\sigma=\frac{\omega}{\sqrt{1-\omega^{2}r^{2}}},$ (2.15)

provided that $\omega$ is a constant. We can get the three dimensional
velocity $v$ using

$\displaystyle v\gamma:=\sqrt{(u^{1})^{2}+(u^{2})^{2}}=\sigma r,$ (2.16)

which gives the usual Newtonian relation

$\displaystyle v=\omega r,$ (2.17)

to which before we referred to as the “linear speed-distance law".
The coordinates transformation from the inertial reference frame in
cylindrical coordinates to the rigidly rotating frame is given by

$\displaystyle\phi\rightarrow\phi+\omega t,$ (2.18)

while the other coordinates remain the same. As it is well known, we arrive at
the Born line element

$\displaystyle ds^{2}=-(1-\omega^{2}r^{2})dt^{2}+2\omega
r^{2}dtd\phi+r^{2}d\phi^{2}+dr^{2}+dz^{2},$ (2.19)

in what follows will be useful to interpret this as a stationary gravitational
field $\Phi_{C}=-\frac{\omega^{2}}{2}r^{2}$.
A useful class of observers in the following discussion are the “zero angular
momentum observers" (ZAMO) [5], [8]. They are orthogonal to the constant time
spacelike hypersurfaces and their orthonormal frame in the case we are
considering here, described in terms of the coordinates in (2.19) is

$\displaystyle e^{(t)}=dt,\quad e^{(\phi)}=d\phi+\omega dt,\quad
e^{(r)}=dr,\quad e^{(z)}=dz.$ (2.20)

Of course, in this specific case the ZAMO is in every point the inertial
reference frame, which is a rotating frame as seen from the rigidly rotating
frame defined by (2.18) with angular velocity $\omega$. In fact, the inverse
of the transformation $(\ref{RRF})$ sends back the frame $(\ref{VZ})$ of the
ZAMO to

$\displaystyle e^{(t)}=dt,\quad e^{(\phi)}=d\phi,\quad e^{(r)}=dr,\quad
e^{(z)}=dz.$ (2.21)

The rigidly rotating metric $(\ref{R})$ written on the basis of the
orthonormal frame of the ZAMO $(\ref{VZ})$ is

$\displaystyle ds^{2}=-dt^{2}+r^{2}\left(d\phi+\omega
dt\right)^{2}+dr^{2}+dz^{2}.$ (2.22)

###  2.1 Rigid rotation in General Relativity

Now we pass to consider the same problem in a general relativistic context,
without neglecting the energy-density of the matter. We will be a little more
general and consider neutral stationary, axysimmetric dust coupled to Einstein
equations. The matter is assumed to flow along the Killing vectors
$\partial_{t}$ and $\partial_{\phi}$ and depends only on the coordinates which
are not associated to Killing vectors $(r,z)$. Denoting the matter density
with $\rho$, in cylindrical coordinates the energy momentum tensor is given by

$\displaystyle T^{\mu\nu}(r,z)=\rho(r,z)u^{\mu}(r,z)u^{\nu}(r,z),\quad
u^{\mu}(r,z)=u^{t}(r,z)\left(1,0,0,\Omega(r,z)\right),$ (2.23)

where $\Omega(r,z)=\frac{d\phi}{dt}=\frac{u^{\phi}}{u^{t}}$. Here we are
interested in the case of constant angular velocity $\Omega(r,z)=\Omega$. For
constant $\Omega$, we can perform a rigid rotation of the coordinates to
rewrite the four velocity of the dust as

$\displaystyle u=\partial_{t}.$ (2.24)

The dust is now at rest compared to these new coordinate set and the class of
solution is now given by [9]

$\displaystyle ds^{2}=-\left(dt-\eta
d\phi\right)^{2}+r^{2}d\phi^{2}+e^{\mu}\left(dr^{2}+dz^{2}\right),$ (2.25)
$\displaystyle\eta_{,rr}+\eta_{,zz}-\frac{\eta_{,r}}{r}=0,\quad\mu_{,r}=\frac{(\eta_{,z})^{2}-(\eta_{,r})^{2}}{2r},\quad\mu_{,z}=-\frac{\eta_{,r}\eta_{,z}}{r},$
(2.26)

where we used the notation $\partial/(\partial a)(f):=f_{,a}$ with $a=r,z$.
To compare this metric with the metric of the rigidly rotating frame (2.22) we
must rewrite $(\ref{RRD})$ in terms of the vierbein of the ZAMO. The ZAMO’s
orthonormal frame in this case is

$\displaystyle e^{(t)}=\frac{1}{\sqrt{1-v^{2}}}dt,\quad
e^{(\phi)}=r\sqrt{(1-v^{2})}\left(d\phi-\chi dt\right),\quad
e^{(r)}=e^{\mu/2}dr,\quad e^{(z)}=e^{\mu/2}dz,$ (2.27)

where

$\displaystyle\chi=-\frac{v}{r}\left(\frac{1}{1-v^{2}}\right),\quad
v(r,z);=\frac{\eta(r,z)}{r}$ (2.28)

The function $v(r,z)$ is the velocity of the dust as judged from the ZAMO,
defined by

$\displaystyle-e^{0}_{\mu}u^{\mu}:=\frac{1}{\sqrt{1-v^{2}}}.$ (2.29)

Note that the definition of ZAMO consistently satisfies the requirement of
zero angular momentum $g_{\phi\phi}\,\chi+g_{\phi t}=0$. The rotating dust
metric (2.25) written in the basis of the vierbein of the ZAMO is

$\displaystyle ds^{2}=-\frac{1}{1-v^{2}}dt^{2}+r^{2}(1-v^{2})\left(d\phi-\chi
dt\right)^{2}+dr^{2}+dz^{2}.$ (2.30)

We now want to show that in the limit of $\rho\rightarrow 0$, this class of
solutions approach the rigidly rotating disk solution. The energy density
$\rho(r,z)$ is given by [9]

$\displaystyle 8\pi G\rho
e^{\mu}=\frac{(\eta_{,r})^{2}+(\eta_{,z})^{2}}{r^{2}},$ (2.31)

therefore we are interested in taking the limit for little $v$. If we expand
the metric (2.30) in powers of $v$ we see that the expansion up to order $v$
is exactly the metric of the rigidly rotating frame (2.22). This reflects the
fact that we are describing the general relativistic solution in the
coordinates of a rigidly rotating frame. This rigidly rotating frame is at
rest compared to the dust and it is in free falling with it.
From the metric (2.30) written in terms of the vierbein of the ZAMO, we can
read the gravitational potential, which is

$\displaystyle\Phi_{N}=\frac{v^{2}}{2},$ (2.32)

and gives the heuristic interpretation of the solution: the gravitational
potential due to the presence of the dust exactly balance the gravitational
potential of the non inertial force given by the rigidly rotation of the
reference frame. In fact the centrifugal force in the rigidly rotating disk,
with angular velocity $\chi$, is $\Phi_{C}=-\frac{\chi^{2}}{2}r^{2}$ and then
we have the usual balance equation

$\displaystyle\Phi_{N}+\Phi_{C}=\frac{v^{2}}{2}-\frac{\chi^{2}}{2}r^{2}=0+O(v^{2}),$
(2.33)

where we used eq.(2.28) up to order $v$

$\displaystyle\chi=-\frac{v}{r}+O(v^{2}).$ (2.34)

The compensation of the two stationary gravitational forces is also the reason
why $g_{tt}=-1$ everywhere in the full solution (2.25), which allows us to
choose a preferred time.
This class of rotating dust solutions has interesting properties, now we
investigate the structure in more detail.
The dust has four velocity

$\displaystyle u=\partial_{t},$ (2.35)

obviously, being $\partial_{t}$ a Killing vector eq.(2.5) is satisfied.
Therefore, all the components of the tensor of deformations vanish:

$\displaystyle P=0.$ (2.36)

This condition shows again that the dust is in rigid rotation even though
$r^{-1}v$ is not constant in general. The condition $P=0$ is stronger than the
analog condition for the rigidly rotating disk in special relativity, for
which only the “spatial part" $\tilde{P}$ of the tensor of deformations is
zero.
The rigid rotation (actually the nullity of $P$) has another interesting
implication for astrophysical measurements, since it allows for the existence
of a timelike Killing vector for which
$g_{tt}=g_{\mu\nu}(\partial_{t})^{\mu}(\partial_{t})^{\nu}=-1$. Let us imagine
that a light signal is emitted from a generic element of the body and it is
received from another element of the body, the measured redshift (or
blueshift) is 0, there is no shift in the frequence of the light! The reason
is that for every element composing the body the measured frequency $\nu$ is

$\displaystyle k^{\mu}u_{\mu}=-\nu$ (2.37)

but $u=\partial_{t}$ is the same for every observer at rest respect to the
rigid body. Again this reflects the compensation in eq.(2.33). The same
experiment performed on a rigidly rotating disk in special relativity, where
the metric is defined by eq. (2.19), would yield the following result for the
frequency shift between two the emitter (E) and the receiver (R) [10]

$\displaystyle\frac{\nu_{E}}{\nu_{R}}=\frac{\sqrt{1-\omega^{2}r^{2}_{R}}}{\sqrt{1-\omega^{2}r^{2}_{E}}},$
(2.38)

then it is different from 1 if they are at different radious.
The nullity of the light frequency shift can be important for applications to
real galaxies. If we are co-rotating with a rigidly rotating galaxy and we try
to apply the special relativistic formula of the doppler shift, therefore
neglecting the effect of gravity, the results would be completely wrong. There
is no shift between a light signal emitted and received at any two points of
the rigid body and this effect does not depend on the regime of application.
The works [3] and [4] propose this class of rigidly rotating solutions as a
model for our galaxy. The validity of the model can be confirmed if the
measurements actually reproduce the nullity of the light frequency shift from
the other stars in our galaxy.

##  3 Low energy expansion and a virial theorem for gravitomagnetism

In this section we reintroduce the constants $c$ and $G$. We want to study the
system of stationary neutral dust coupled to Einstein equations as in the last
section, but now we address the problem starting from a low energy expansion.
Then, as the standard procedure, we assume the existence of global coordinates
$(t,x^{i})$ in which the metric reads

$\displaystyle g_{\mu\nu}=\eta_{\mu\nu}+h_{\mu\nu},\qquad|h_{\mu\nu}|\ll 1.$
(3.1)

These coordinates select a preferred reference frame $\mathcal{I}$, defined by
the family of curves $t=$variable. In this reference frame all the matter
content is slow compared to the speed of light. To do this, we perform an
expansion in power of $1/c$ and we will consider the leading orders. We write
the solution of Einstein field equations in weak-field and slow-motion
approximation exploiting a well known analogy with Maxwell equations: this is
the so-called gravitoelectromagnetic formalism (see e.g. [11, 12]);
accordingly, the line element describing this solution is

$\displaystyle
ds^{2}=-c^{2}\left(1-2\frac{\Phi}{c^{2}}\right)dt^{2}-\frac{4}{c}A_{\hat{i}}dx^{\hat{i}}dt+\left(1+2\frac{\Phi}{c^{2}}\right)\delta_{ij}dx^{\hat{i}}dx^{\hat{j}}.$
(3.2)

The coordinates are splitted as $\\{\hat{i},\hat{j}\\}=\\{x,y,z\\}$ are the
spatial indices. Accordingly, we must choose a form of the energy momentum
tensor suitable for such expansion of the geometry. For the four-velocities
and the energy-momentum tensor of matter $T^{\mu\nu}$ we assume the following
approximation

$\displaystyle u^{0}=$ $\displaystyle 1+O(c^{-2}),\quad
u^{\hat{i}}=v_{\hat{j}}+O(c^{-3}),$ (3.3) $\displaystyle T^{00}=$
$\displaystyle\rho+O(\rho c^{-2}),\quad T^{0\hat{i}}=\rho v_{\hat{j}}+O(\rho
c^{-3}),\quad T^{\hat{j}\hat{k}}=\rho v_{\hat{j}}v_{\hat{k}}+O(\rho c^{-4}).$
(3.4)

In the above equation the gravitoelectric ($\Phi$) and gravitomagnetic
($A_{i}$) potentials, in stationary conditions, are solutions of Poisson
equations

$\displaystyle\nabla^{2}\Phi$ $\displaystyle=$ $\displaystyle-4\pi G\,\rho,$
(3.5) $\displaystyle\nabla\wedge\left(\nabla\wedge\vec{A}\right)$
$\displaystyle=$ $\displaystyle 8\pi G\,\rho\frac{\vec{v}}{c},$ (3.6)

where $\vec{A}$ and $\vec{v}$ clearly refer to the components of the
respective vectors. Usually in the Newtonian limit, one assume that the
dominant contribution to gravitation comes from $T_{00}$ and then neglect the
$(0,\hat{i})$ components of the Einstein equations under the assumption $A\sim
O(c^{-1})$. Introducing

$\displaystyle
B_{\hat{i}}:=\epsilon_{\hat{i}}^{\,\,\hat{j}\hat{k}}\partial_{\hat{j}}A_{\hat{k}},$
(3.7)

allows us to express the time and spatials components of the local
conservation equation $T^{\mu\nu}_{\quad;\nu}=0$ respectively as

$\displaystyle\frac{\partial\rho}{\partial t}+\frac{\partial\left(\rho
v_{\hat{i}}\right)}{\partial x^{\hat{j}}}=0,$ (3.8)
$\displaystyle\rho\frac{dv_{\hat{i}}}{dt}=-\rho\left(\Phi_{,\hat{i}}+2\epsilon^{\hat{i}\hat{j}\hat{k}}\frac{v_{\hat{j}}}{c}B_{\hat{k}}\right),$
(3.9)

where we defined $d/dt:=\partial_{t}+v_{\hat{j}}\partial_{\hat{j}}$. These
equations are well known, the first one is the continuity equation and the
second one is the analogue of the Lorentz force law [7].
We note that

$\displaystyle-2\rho\epsilon^{\hat{i}\hat{j}\hat{k}}\frac{v_{\hat{j}}}{c}B_{\hat{k}}=$
$\displaystyle-\frac{1}{4\pi
G}\epsilon^{\hat{i}\hat{j}\hat{k}}B_{\hat{k}}\epsilon^{\hat{j}\hat{l}\hat{s}}\partial_{\hat{l}}B_{\hat{s}}=$
(3.10) $\displaystyle=\frac{1}{4\pi
G}\left(B^{\hat{j}}\partial^{\hat{i}}B_{\hat{j}}-B^{\hat{j}}\partial_{\hat{j}}B^{\hat{i}}\right)=-\frac{1}{4\pi
G}\partial_{\hat{j}}\left(B^{\hat{j}}B^{\hat{i}}-\frac{1}{2}\delta^{\hat{i}\hat{j}}B^{\hat{k}}B_{\hat{k}}\right),$
(3.11)

where we used the following consequences of eq.(3.6) and eq.(3.7)

$\displaystyle\partial_{\hat{j}}\left(\epsilon^{\hat{i}\hat{j}\hat{k}}B_{\hat{k}}\right)=\frac{8\pi
G}{c}\rho v^{\hat{i}},\quad B^{\hat{i}}_{\,\,,\hat{i}}=0.$ (3.12)

Thanks to these results it is useful to define the two stress pseudo tensors

$\displaystyle t_{N|\hat{i}\hat{j}}:=\frac{1}{4\pi
G}\left(\Phi_{,\hat{i}}\Phi_{,\hat{j}}-\frac{1}{2}\delta_{\hat{i}\hat{j}}\Phi_{,\hat{k}}\Phi_{,\hat{k}}\right),$
(3.13) $\displaystyle t_{\mathcal{J}|\hat{i}\hat{j}}:=\frac{1}{4\pi
G}\left(B^{\hat{i}}B^{\hat{j}}-\frac{1}{2}\delta^{\hat{i}\hat{j}}B^{\hat{k}}B_{\hat{k}}\right),$
(3.14)

such that $\Phi_{,\hat{i}}=\partial_{\hat{i}}\Phi$. We can rewrite the
equation of motion for the matter (3.9) as

$\displaystyle\rho\frac{dv^{\hat{i}}}{dt}=-\partial_{\hat{j}}\left(t_{N|\hat{i}\hat{j}}+t_{\mathcal{J}|\hat{i}\hat{j}}\right),$
(3.15)

or, equivalently

$\displaystyle\frac{\partial}{\partial t}\left(\rho
v_{\hat{i}}\right)+\left(t_{N|\hat{i}\hat{j}}+t_{\mathcal{J}|\hat{i}\hat{j}}+\rho
v_{\hat{i}}v_{\hat{j}}\right)_{,\hat{j}}=0.$ (3.16)

At our order of approximation the last equation can be integrated as

$\displaystyle\frac{d^{2}\mathcal{I}_{\hat{i}\hat{j}}}{dt^{2}}=2\int\left(t_{N|\hat{i}\hat{j}}+t_{\mathcal{J}|\hat{i}\hat{j}}+\rho
v_{i}v_{j}\right)d^{3}x,$ (3.17)

where we used the second moment of the system’s mass distribution

$\displaystyle\mathcal{I}_{\hat{i}\hat{k}}=\int\rho
x_{\hat{i}}x_{\hat{j}}d^{3}x.$ (3.18)

In this derivation, we made use of the following known result [13], [14]

$\displaystyle\frac{d}{dt}\int\rho fd^{3}x=\int\rho\frac{df}{dt}d^{3}x+O(\rho
c^{-2}),$ (3.19)

where $f$ is a generic function.Usually one is interested in taking the time
“long" average of $(\ref{VT})$, in the approximation where this average for
the second derivative of the second moment of the system’s mass distribution
is zero

$\displaystyle\langle\int t_{N|ij}d^{3}x+\int
t_{\mathcal{J}|ij}d^{3}x+\int\rho v_{i}v_{j}d^{3}x\rangle=0,$ (3.20)

when we take the trace, this equation becomes

$\displaystyle\langle\int\rho
v^{2}\,d^{3}x-\frac{1}{2}\int\rho\Phi\,d^{3}x+\int
t_{\mathcal{J}}\,d^{3}x\rangle=0,$ (3.21)

which can be rewritten in the usual form

$\displaystyle\langle 2\mathcal{K}+\mathcal{U}-\frac{1}{8\pi
G}\int\mathcal{H}d^{3}x\rangle=0,$ (3.22)
$\displaystyle\mathcal{H}:=\left(\partial_{\hat{i}}A_{\hat{j}}\right)^{2}-\left(\partial_{\hat{i}}A_{\hat{j}}\right)\left(\partial_{\hat{j}}A_{\hat{i}}\right).$
(3.23)

It is interesting to note that this result can reduce the amount of matter
needed to sustain a motion with velocity $v$ compared to the Newtonian version
of the same theorem. A formal discussion of the virial theorem for spherical
and stationary axisymmetric spacetimes is given in [15]. The approach used
here is substantially different and it is not restricted to axisymmetric
spacetimes, although we will see an explicit application of (3.22) for
axisymmetric systems in the next section. More importantly, the specific
chosen expansion allowed for a new explicit result (3.22) that can be directly
tested on real galaxies. Moreover, our result makes clear that the off-
diagonal terms $h_{0i}$, which have a nice interpretation as “gravito-
magnetic" fields, can have the effect of reducing the energy density content
$\rho$ compared to the purely Newtonian case.
This modification respect to the Newtonian version of the virial theorem can
have interesting applications on systems as galaxies or clusters of galaxies.
In particular could lead to a re-evaluation of the amount of required dark
matter for such systems. This aspect deserves further investigations.
The reduction of the needed amount of matter that arise when considering non
negligible off-diagonal terms has been already noted, from an exact solution
perspective, in [16].
The virial theorem can be written in a more suggestive way

$\displaystyle\langle 2\int\rho v^{2}d^{3}x-\frac{1}{8\pi
G}\int\left(E^{2}+B^{2}\right)d^{3}x\rangle=0.$ (3.24)

Using the analogy with electromagnetism we see that the second term is the
total energy stored in the gravity fields. Therefore we have the balance
equation

$\displaystyle 2\times\text{energy of free dust (kinetic energy)}=\text{energy
of gravity}.$ (3.25)

###  3.1 Explicit example in stationary axisymmetric spacetimes

As an explicit application of the above results, let us take an axisymmetric
stationary system dominated by “angular currents" $h_{0\hat{i}}\equiv
S_{\hat{i}}$ which are not time dependent $\partial_{t}S_{\hat{i}}\sim 0$ in
our approximation. We then take a simplified version of the metric

$\displaystyle
ds^{2}=-c^{2}\left(1-2\frac{\Phi}{c^{2}}\right)dt^{2}-4\frac{\tilde{S}(r,z)}{c}dtd\phi+\left(1+2\frac{\Phi}{c^{2}}\right)\left(r^{2}d\phi^{2}+dr^{2}+dz^{2}\right).$
(3.26)

We switch to cartesian coordinates $(x,y)$ in the $z=0$ plane

$\displaystyle rdr=xdx+ydy,$ (3.27) $\displaystyle r^{2}d\phi=-ydx+xdy,$
(3.28)

and one gets the following form for the metric

$\displaystyle ds^{2}=$
$\displaystyle-c^{2}\left(1-2\frac{\Phi}{c^{2}}\right)dt^{2}+4\frac{\tilde{S}(r,z)}{c}\frac{y}{x^{2}+y^{2}}dtdx-4\frac{\tilde{S}(r,z)}{c}\frac{x}{x^{2}+y^{2}}dtdy+$
$\displaystyle+\left(1+2\frac{\Phi}{c^{2}}\right)\left(dx^{2}+dy^{2}+dz^{2}\right).$
(3.29)

With the conventions of the last section we have the identification

$\displaystyle A_{x}=-\tilde{S}(r,z)\frac{y}{x^{2}+y^{2}},\quad
A_{y}=\tilde{S}(r,z)\frac{x}{x^{2}+y^{2}},\quad A_{z}=0.$ (3.30)

Then we have from eq. (3.23)

$\displaystyle\mathcal{H}=\frac{\tilde{S}^{2}_{,z}+\tilde{S}^{2}_{,r}}{r^{2}}.$
(3.31)

Assuming reflection symmetry $z\leftrightarrow-z$ at the equatorial axis
$z=0$, we can neglect the $z-$derivatives and the result in the equatorial
$z=0$ plane is

$\displaystyle\mathcal{H}_{z=0}=\frac{1}{r^{4}}\left(x\tilde{S}_{,x}+y\tilde{S}_{,y}\right)^{2}=\left(\frac{1}{r^{2}}\,\vec{r}\cdot\nabla\tilde{S}\right)^{2}.$
(3.32)

We can rewrite the virial equation (3.22) as

$\displaystyle\langle\int\rho v^{2}-\frac{1}{16\pi
G}\int\frac{\tilde{S}^{2}_{,z}+\tilde{S}^{2}_{,r}}{r^{2}}-\frac{1}{2}\int\rho\Phi\rangle=0.$
(3.33)

As already noted from the general result (3.23), the off-diagonal term affects
the required density. In this particular case of axisymmetric spacetimes the
term $\mathcal{H}$ in eq.(3.31) is always positive and then its presence
guarantees the reduction of the needed matter compared to the purely Newtonian
case. The resulting difference from the Newtonian version of the theorem is
essentially the presence of the term

$\displaystyle\frac{1}{r^{2}}\vec{r}\cdot\nabla\tilde{S}.$ (3.34)

The same effect can be understood from a different perspective. Let us study
the deflection of light due to the presence of an object whose metric can be
written as in $(\ref{APPM1})$. We limit the problem to the galactic plane
$z=0$, when the angular momentum of the approaching light is different from
zero (the impact parameter is $\neq 0$), using an approach similar to [13].
Here we are neglecting the Newtonian potential $\Phi$ because we want to focus
on the effect due to the non-diagonal elements of the metric. We consider the
motion in the galactic plane of a photon coming from far away with initial
velocity

$\displaystyle v^{t}=\tilde{\omega},\qquad v^{x}=\tilde{\omega},\qquad
v^{y}=0.$ (3.35)

During its trajectory we suppose that $v^{t}=\tilde{\omega}$ and
$v^{x}=\tilde{\omega}$ remain approximately constant, while $v^{y}$ depends
only on the value of $x$. The photon arrives from $x=-\infty$, travel across
the gravitational field of the galaxy at a nearly constant value of $y=R$, and
then flies away at $x=\infty$. During this trip the value of $v^{y}$ is
increased due to the bending of the trajectory by the galaxy, and the
deflection angle is

$\displaystyle\Delta\phi=\frac{v^{y}_{Final}}{v^{x}_{Final}}=\frac{v^{y}_{Final}}{\tilde{\omega}},$
(3.36)

our approximations are justified by the assumption of a small resulting value
for the angle. The geodesic equation is

$\displaystyle\frac{dv^{y}}{d\tau}=\frac{dx}{d\tau}\frac{dv^{y}}{dx}=\tilde{\omega}\frac{dv^{y}}{dx}=-(\Gamma^{y}_{tt}+2\Gamma^{y}_{tx}+\Gamma^{y}_{xx})\tilde{\omega}^{2},$
(3.37)

at the first order in $\tilde{S}$, we have

$\displaystyle\frac{v^{y}_{Final}|_{y=R}}{\tilde{\omega}}=-\int^{+\infty}_{-\infty}\frac{\vec{r}\cdot\vec{\nabla}\tilde{S}}{r^{2}}dx|_{y=R}=-\int^{+\infty}_{-\infty}\frac{y\tilde{S}_{,y}+x\tilde{S}_{,x}}{x^{2}+y^{2}}dx|_{y=R}.$
(3.38)

##  4 Final remarks and perspectives

In the first part we studied rigidly rotating neutral dust solutions in
general relativity under the assumptions of stationarity and axysimmetry and
we tried to understand their properties and their difference with well known
solutions in special relativity. We discussed the interpretation of the
usually adopted coordinates and the nullity of the tensor of deformations $P$
for such solutions. The features of the solutions allowed us to draw some
limits of the $\Omega=$ constant model assumed in [3] and [4] as a model for
our galaxy. In this sense, we suggested that a strong indicator for the
validity of this rigidly rotating model for our galaxy is the nullity of the
Doppler effect between any two points (the receiver and the emitter of the
light signal) co-rotating with the dust. This can be important for galactic
applications. If this effect is not verified by the observations one should
therefore take under consideration the larger class of $\Omega\neq$ constant
as a model for our galaxy. The most general solution for rotating dust under
the assumptions of stationarity and axysimmetry and its application to
galaxies was studied in [16] and more work is in order.
In the second part we did not restrict the discussion to rigid rotation and we
approached the problem from a different perspective. We generalized the virial
theorem to gravito-magnetism and this provided a new formulation that can be
tested on real objects. Interestingly, this generalized version of the virial
theorem reduces the matter needed to sustain the motion compared to the
usually adopted Newtonian version of the same theorem. In the light of the
dark matter problem this additional contribution can lead to a re-weighting of
the contribution of dark matter in galaxies or in clusters.
In future would be interesting to explicitely write down more general versions
of the virial theorem lowering the number of symmetries of the system.

## Acknowledgements

I would like to thank Professor Matteo Luca Ruggiero for reviewing this
manuscript.

## Data availability

No new data were generated or analysed in support of this research.

##  Appendix A More details on Gravitomagnetism

We consider the field of a galactic or an extra-galactic source in the linear
approximation of GR. We therefore assumed the metric in the form (3.1). The
Einstein equations can be casted in the form

$\displaystyle\Box\bar{h}_{\mu\nu}$ $\displaystyle=16\frac{\pi
G}{c^{4}}T_{\mu\nu},$ (A.1) $\displaystyle\bar{h}_{\mu\nu}$
$\displaystyle=h_{\mu\nu}-{1\over 2}\eta_{\mu\nu}h,$ (A.2)

where $h=g^{\mu\nu}h_{\mu\nu}$ after retaining only the terms linear in
$h_{\mu\nu}$. As usual, to obtain the equations in this form, one has to
impose the Lorentz gauge condition $\bar{h}^{\mu\nu},_{\nu}=0$. To obtain a
parallelism with the electromagnetic theory, we choose the metric such that
$\bar{h}_{00}=4\Phi/c^{2}$, $\bar{h}_{0i}=-2A_{i}/c^{2}$ and
$\bar{h}_{ij}=O(c^{-4})$, where $\Phi(t,{\bf x})$ is the gravitoelectric
potential, ${\bf A}(t,{\bf x})$ is the gravitomagnetic vector potential and we
neglect all terms of order $c^{-4}$ and lower [11]. From the side of the
source, $T^{00}=c^{2}\rho$ is the gravitational “charge" density and
$T^{0i}=cj^{i}$ is the corresponding current. Thus, far from the source

$\Phi\sim\frac{GM}{r},\;\;\;\;\;\;\;\;\;\;\;{\bf A}\sim\frac{G}{c}\frac{{\bf
J}\times{\bf r}}{r^{3}},$ (A.3)

where $M$ and ${\bf J}$ are the total mass and angular momentum of the source,
respectively.
Under these assumptions, the Lorentz gauge condition can be expressed as

$\frac{1}{c}\frac{\partial\Phi}{\partial
t}+\mbox{\boldmath$\nabla$}\cdot\left({1\over 2}{\bf A}\right)=0,$ (A.4)

The spacetime metric involving the gravitoelectromagnetic potentials is then
given by (3.2)

$\displaystyle
ds^{2}=-c^{2}\left(1-2\frac{\Phi}{c^{2}}\right)dt^{2}-\frac{4}{c}A_{\hat{i}}dx^{\hat{i}}dt+\left(1+2\frac{\Phi}{c^{2}}\right)\delta_{ij}dx^{\hat{i}}dx^{\hat{j}}.$
(A.5)

At this point we can define the gravito-electro and gravito-magnetic fields

${\bf E}=-\mbox{\boldmath$\nabla$}\Phi-{1\over c}{\partial\over\partial
t}\left({1\over 2}{\bf A}\right),\;\;\;\;\;\;\;\;{\bf
B}=\mbox{\boldmath$\nabla$}\times{\bf A},$ (A.6)

in close analogy with electrodynamics. It follows from the field equations
(A.1) and the gauge condition (A.4) that

$\mbox{\boldmath$\nabla$}\cdot{\bf E}=4\pi G\rho,$ (A.7)

$\mbox{\boldmath$\nabla$}\cdot\left({1\over 2}{\bf B}\right)=0,$ (A.8)

$\mbox{\boldmath$\nabla$}\times{\bf E}=-{1\over c}{\partial\over\partial
t}\left({1\over 2}{\bf B}\right),$ (A.9)

$\mbox{\boldmath$\nabla$}\times\left({1\over 2}{\bf B}\right)={1\over
c}{\partial\over\partial t}{\bf E}+{4\pi\over c}G\>{\bf j}\>,$ (A.10)

explicitly analogous to the Maxwell equations for the GEM field.
The magnetic parts of equations (A.7) - (A.10) appear with a factor of $1/2$
as compared to standard electrodynamics is due to the fact that the effective
gravitomagnetic charge is twice the gravitoelectric charge.
Under the assumption of stationarity, from the presented equations one obtains
(3.5) and (3.6).
The geodesics of the particles of dust given by (3.9), can be obtained from
the variational principle $\delta\int{\mathcal{L}}dt=0$, where
${\mathcal{L}}=mcds/dt$. The lagrangian is

$\displaystyle{\mathcal{L}}=$ $\displaystyle-
mc\sqrt{-g_{\mu\nu}\frac{dx^{\mu}}{dt}\frac{dx^{\nu}}{dt}}=-mc^{2}\sqrt{-g_{00}-2g_{0\hat{i}}\frac{dx^{\hat{i}}}{dt}-g_{\hat{j}\hat{k}}\frac{v^{\hat{j}}v^{\hat{k}}}{c^{2}}}=$
$\displaystyle-mc^{2}\left[1-{v^{2}\over c^{2}}-{2\over
c^{2}}\left(1+{v^{2}\over c^{2}}\right)\Phi+{4\over c^{3}}{\bf v}\cdot{\bf
A}\right]^{1/2},$ (A.11)

which to linear order in $\Phi$ and ${\bf A}$ boils down to

${\mathcal{L}}=-mc^{2}\left(1-{v^{2}\over
c^{2}}\right)^{1/2}+m\gamma\left(1+{v^{2}\over c^{2}}\right)\Phi-{2m\over
c}\gamma{\bf v}\cdot{\bf A}.$ (A.12)

The gauge transformations

$\Phi\rightarrow\Phi-{1\over c}{\partial\psi\over\partial t},\;\;\;\;\;{\bf
A}\rightarrow{\bf A}+2\mbox{\boldmath$\nabla$}\psi,$ (A.13)

leave the GEM fields (A.6) and hence the GEM equations (A.7)-(A.10) invariant.
The Lorentz gauge condition (A.4) is also satisfied provided $\Box\psi=0$.
The gravitational field corresponding to the metric (A.5) is given by the
Riemann curvature tensor

$R_{\mu\nu\rho\sigma}={1\over
2}(h_{\mu\sigma,\;\nu\rho}+h_{\nu\rho,\;\mu\sigma}-h_{\nu\sigma,\;\mu\rho}-h_{\mu\rho,\nu\sigma}),$
(A.14)

where

$\displaystyle h_{00}=2\Phi/c^{2},\quad h_{ij}=(2\Phi/c^{2})\delta_{ij},\quad
h_{0i}=-2A_{i}/c^{2},$ (A.15)

plus higher order terms. The components of the Riemann tensor may be expressed
in the following form [17]

${\mathcal{R}}=\begin{pmatrix}{\mathcal{E}}&{\mathcal{B}}\\\
{\mathcal{B}}^{T}&{\mathcal{S}}\end{pmatrix}\,,$ (A.16)

where ${\mathcal{E}}$ and ${\mathcal{S}}$ are symmetric $3\times 3$ matrices
and ${\mathcal{B}}$ is traceless. These matrices read explicitly

${\mathcal{E}}_{ij}={1\over c^{2}}E_{j,i}+O(c^{-4}),$ (A.17)

${\mathcal{B}}_{ij}=-{1\over c^{2}}B_{j,i}+{1\over
c^{3}}\epsilon_{ijk}{\partial E_{k}\over\partial t}+O(c^{-4}),$ (A.18)

and the spatial components are given by

${\mathcal{S}}_{ij}=-{1\over c^{2}}E_{j,i}+{1\over
c^{2}}(\mbox{\boldmath$\nabla$}\cdot{\bf E})\delta_{ij}+O(c^{-4}).$ (A.19)

They are explicitly invariant under (A.13).
To obtain the generalized virial theorem we defined the tensor
$t_{\mathcal{J}|\hat{i}\hat{j}}$ in eq.(3.14), which again is explicitly
invariant under the gauge transformations $(\ref{e14})$, therefore also
$\mathcal{H}\sim B^{2}$ possess the same property.

## References

  * [1] N. Rosen, “Notes on rotation and rigid bodies in relativity theory,” Physical Review, vol. 71, pp. 54–58, 1947.
  * [2] F. I. Cooperstock and S. Tieu, “General relativity resolves galactic rotation without exotic dark matter,” 7 2005.  arXiv:0507619.
  * [3] H. Balasin and D. Grumiller, “Non-Newtonian behavior in weak field general relativity for extended rotating sources,” Int. J. Mod. Phys. D, vol. 17, pp. 475–488, 2008.
  * [4] M. Crosta, M. Giammaria, M. G. Lattanzi, and E. Poggio, “On testing CDM and geometry-driven Milky Way rotation curve models with Gaia DR2,” Mon. Not. Roy. Astron. Soc., vol. 496, no. 2, pp. 2107–2122, 2020.
  * [5] J. M. Bardeen, W. H. Press, and S. A. Teukolsky, “Rotating Black Holes: Locally Nonrotating Frames, Energy Extraction, and Scalar Synchrotron Radiation,” apj, vol. 178, pp. 347–370, Dec. 1972.
  * [6] G. O. Ludwig, “Galactic rotation curve and dark matter according to gravitomagnetism,” Eur. Phys. J. C, vol. 81, no. 2, p. 186, 2021.
  * [7] M. L. Ruggiero, A. Ortolan, and C. C. Speake, “Galactic Dynamics in General Relativity: the Role of Gravitomagnetism,” 12 2021.  arXiv:2112.08290.
  * [8] D. Bini, C. Cherubini, A. Geralico, and R. T. Jantzen, “Physical frames along circular orbits in stationary axisymmetric spacetimes,” Gen. Rel. Grav., vol. 40, p. 985, 2008.
  * [9] J. Winicour, “All stationary axisymmetric rotating dust metrics,” Journal of Mathematical Physics, vol. 16, no. 9, pp. 1806–1808, 1975.
  * [10] J. L. SYNGE, “Group motions in space-time and doppler effects,” Nature, vol. 198, no. 4881, pp. 679–679, 1963.
  * [11] M. L. Ruggiero and A. Tartaglia, “Gravitomagnetic effects,” Nuovo Cim., vol. B117, pp. 743–768, 2002.
  * [12] B. Mashhoon, “Gravitoelectromagnetism: A Brief review,” 11 2003.
  * [13] C. W. Misner, K. S. Thorne, and J. A. Wheeler, Gravitation.  San Francisco: W. H. Freeman, 1973.
  * [14] S. Chandrasekhar, “The Post-Newtonian Equations of Hydrodynamics in General Relativity.,” apj, vol. 142, p. 1488, Nov. 1965.
  * [15] S. Bonazzola, “The virial theorem in general relativity,” The Astrophysical Journal, vol. 182, p. 335, 1973.
  * [16] D. Astesiano, S. L. Cacciatori, and F. Re, “Towards a full general relativistic approach to galaxies,” 6 2021.  arXiv:2106.12818.
  * [17] B. Mashhoon, F. Gronwald, and H. I. M. Lichtenegger, “Gravitomagnetism and the clock effect,” Lect. Notes Phys., vol. 562, pp. 83–108, 2001.


# Metric Dimension of a Diagonal Family of Generalized Hamming Graphs

Briana Foster-Greenwood  Department of Mathematics and Statistics, California
State Polytechnic University, Pomona, CA 91768<EMAIL_ADDRESS>and  Christine
Uhl  Department of Mathematics, St. Bonaventure University, St Bonaventure, NY
14778<EMAIL_ADDRESS>
###### 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.

###### Key words and phrases:

metric dimension, resolving set, Hamming graph, unitary Cayley graph,
hypergraph, forbidden subgraph, edge coloring

###### 2020 Mathematics Subject Classification:

05C69 (Primary) 05C12, 05B30, 05C15 (Secondary)

##  1\. Introduction

Consider an $m\times n$ chessboard with some cells occupied by landmarks. A
landmark in cell $(i,j)$ sees all other cells that are in row $i$ or column
$j$. Is it possible to place landmarks on the board so that each unoccupied
cell is seen by a different (possibly empty) set of landmarks? What is the
minimum number of landmarks required? What if the puzzle is played in higher
dimensions on an $n_{1}\times\cdots\times n_{r}$ board, where a landmark sees
all other cells that share at least one coordinate with the landmark’s cell?

This optimization puzzle is equivalent to finding the metric dimension of a
generalized Hamming graph. After providing background on metric dimension and
Hamming graphs, we solve the $2$-dimensional puzzle using known results and
then devote the rest of the paper to solving $3$-dimensional puzzles on
$n\times n\times n$ boards.

###  1.1. Metric dimension

Let $G$ be a finite connected graph with vertex set $V$. For vertices $x,y\in
V$, define the distance $d(x,y)$ to be the length of the shortest path between
$x$ and $y$ in $G$. Given a subset of vertices $W\subseteq V$, whose elements
are referred to as landmarks, we say $W$ is a resolving set (or $W$ resolves
$G$) provided that for every pair of distinct vertices $x,y\in V-W$, there
exists a landmark $w\in W$ such that $d(x,w)\neq d(y,w)$. A minimum size
resolving set is a metric basis for $G$. The metric dimension of $G$, denoted
$\dim G$, is the size of a metric basis.

In the graph theory context, metric dimension was introduced independently by
Harary and Melter [HM76] and Slater [Sla75] in the 1970s. Bounds and values
for metric dimension and its variants have been found for many graph families.
See [TFL21] for a nice survey paper on metric dimension and some applications,
which include source localization (detecting the source of spread in
networks), detecting network motifs, and embedding biological sequence data.
See [KY21] for a survey on the many variants of metric dimension.

###  1.2. Hamming graphs

While there are many generalizations of Hamming graphs, we adopt the
definition from [San10]. For an $r$-tuple of positive integers
$n_{1},\ldots,n_{r}$ and a set of distances $K\subseteq\\{1,2,\ldots,r\\}$,
let the generalized Hamming graph $HG(n_{1},\ldots,n_{r};K)$ be the graph with
vertex set $V=\\{(x_{1},\ldots,x_{r})\mid 1\leq x_{i}\leq n_{i}\\}$ and
adjacency defined by $x\sim y$ if and only if there exists $k\in K$ such that
$x$ and $y$ differ in exactly $k$ coordinates.

As noted in [San10], generalized Hamming graphs include Cartesian products of
complete graphs

$HG(n_{1},\ldots,n_{r};1)\cong K_{n_{1}}\Box\cdots\Box K_{n_{r}}.$

In particular, this includes the classical Hamming graphs $H(d,q)$ which are
the Cartesian products of $d$ copies of the complete graph $K_{q}$ (with the
case of $q=2$ yielding hypercubes, also known as binary Hamming graphs).
Cáceres, et al. [CHM+07] determine the metric dimension of a Cartesian product
of two complete graphs and bound the metric dimension of the Cartesian product
of a complete graph with another graph. Research on resolvability in Hamming
graphs includes, for instance, work on coin-weighing problems (e.g., [ER63],
[Lin64], [CM66],[LY22]), asymptotic results for metric dimension of general
Cartesian powers [JP19], and an integer linear programming approach for
testing resolvability [LTBL20]. For more details and references, see the
survey [TFL21]. We also note that Junnila, et al. [JLL19] determine the
minimum size of self-locating-dominating codes for the Hamming graphs
$H(3,q)$, which is a different problem but has a similar flavor to metric
dimension.

For purposes of the puzzle introduced at the beginning of this article, we are
interested in the generalized Hamming graphs $HG(n_{1},\ldots,n_{r};r)$, in
which two vertices are adjacent if they have no coordinates in common. For
$r\geq 2$ and $n_{i}\geq 3$, the graphs are connected with diameter two. In
particular,

$d(x,y)=\begin{cases}0&\text{if $x=y$,}\\\ 1&\text{if $x$ and $y$ have no
coordinates in common,}\\\ 2&\text{if $x$ and $y$ have at least one coordinate
in common.}\end{cases}$

(Note that for $r\geq 2$, if $n_{1}=n_{2}=2$, the graph
$HG(n_{1},\ldots,n_{r};r)$ is disconnected, and if $n_{1}=2$ and
$n_{2},\ldots,n_{r}\geq 3$, the graph is connected but has diameter $3$.)

In terms of the puzzle, we see that, for $r\geq 2$ and $n_{i}\geq 3$, the
cells of an $n_{1}\times\cdots\times n_{r}$ board correspond to vertices in
the graph $HG(n_{1},\ldots,n_{r};r)$, and a landmark $w$ sees vertex $x$
precisely when $d(w,x)=2$. Also, $x$ and $y$ that are not landmarks will be
resolved if and only if there is a landmark that sees $x$ or $y$ but not both,
i.e., $x$ and $y$ are seen by different sets of landmarks. Therefore a
resolving set for the graph $HG(n_{1},\ldots,n_{r};r)$ corresponds to a
solution to the puzzle, and the metric dimension is the minimum number of
landmarks required to solve the puzzle.

Note that, alternatively, we could use the graphs
$HG(n_{1},\ldots,n_{r};1,\ldots,r-1)$. These graphs also have diameter two,
but the criteria for distance one and distance two are swapped. It follows
that the graphs $HG(n_{1},\ldots,n_{r};r)$ and
$HG(n_{1},\ldots,n_{r};1,\ldots,r-1)$ have the same resolving sets and metric
dimension, so we could use either graph to represent our puzzles.

The generalized Hamming graphs under consideration can be expressed in terms
of various graph operations involving Cartesian products, complements, power
graphs, and exact distance graphs. Given a graph $G$, we can construct the
graph complement $\overline{G}$, the $k$-th power graph $G^{(k)}$, and the
exact distance-$k$ graph $G^{[\natural k]}$. All three graphs share the same
vertex set as $G$. Distinct vertices are adjacent in the $k$-th power graph if
they are at most distance $k$ apart in $G$, while adjacency in the exact
distance-$k$ graph requires a distance of exactly $k$. By [San10, Lemma 3.1],
the graphs $HG(n_{1},\ldots,n_{r};r)$ and
$HG(n_{1},\ldots,n_{r};1,\ldots,r-1)$ are complements of each other and we
have the isomorphisms

$HG(n_{1},\ldots,n_{r};r)\cong(K_{n_{1}}\Box\cdots\Box K_{n_{r}})^{[\natural
r]}$

and

$HG(n_{1},\ldots,n_{r};1,\ldots,r-1)\cong(K_{n_{1}}\Box\cdots\Box
K_{n_{r}})^{(r-1)}.$

For structural results on exact distance graphs of product graphs, see
[BGKT19]. The above isomorphisms will be useful in solving the $2$-dimensional
puzzle.

###  1.3. Two- and three-dimensional puzzles

By the remarks in the previous subsection, we can solve the $2$-dimensional
puzzle on an $m\times n$ board by finding the metric dimension and minimum
resolving sets of the graph $HG(m,n;2)\cong(K_{m}\Box K_{n})^{[\natural 2]}$
or $HG(m,n;1)\cong K_{m}\Box K_{n}$. Choosing the latter, we can apply
[CHM+07, Theorem 6.1] that for all $n\geq m\geq 1$,

$\dim(K_{m}\square
K_{n})=\begin{cases}\lfloor\frac{2}{3}(n+m-1)\rfloor&\text{if $m\leq n\leq
2m-1$}\\\ n-1&\text{if $n\geq 2m-1$.}\end{cases}$

Moreover, [CHM+07, Lemma 6.2] provides necessary and sufficient conditions for
a subset of vertices $S$ to be resolving based on relationships between the
elements of $S$.

To solve the puzzle on an $n_{1}\times n_{2}\times n_{3}$ board, we want to
find the metric dimension of $HG(n_{1},n_{2},n_{3};3)\cong(K_{n_{1}}\Box
K_{n_{2}}\Box K_{n_{3}})^{[\natural 3]}$ or
$HG(n_{1},n_{2},n_{3};1,2)\cong(K_{n_{1}}\Box K_{n_{2}}\Box K_{n_{3}})^{(2)}$.
We are unaware of any results that give the metric dimension of these graphs,
so that will be the focus of the remainder of the paper. In Section 2, we find
a lower bound for the metric dimension. In Section 3, we focus our attention
on the diagonal family $HG(n,n,n;3)$ and develop a characterization of
resolving sets in terms of forbidden edge-colored subgraphs of an auxiliary
hypergraph. In Section 4, we apply the theorems from Section 3 to construct
minimum resolving sets for diagonal Hamming graphs. We end with the
comprehensive Theorem 4.6 for the metric dimension of the Hamming graphs
$HG(n,n,n;3)$ for $n\geq 3$ and indicate further research directions with
connections to unitary Cayley graphs.

Throughout the paper, let
$\mathcal{N}=\\{(n_{1},n_{2},n_{3})\in\mathbb{N}^{3}\mid n_{1},n_{2},n_{3}\geq
3\\}$ and let the diagonal be $\operatorname{diag}(\mathcal{N})=\\{(n,n,n)\mid
n\geq 3\\}$. We commonly denote an element of $\mathcal{N}$ as
$\mathbf{n}=(n_{1},n_{2},n_{3})$ and increment each coordinate to get
$\mathbf{n}+\mathbf{1}=(n_{1}+1,n_{2}+1,n_{3}+1)$. For $n\in\mathbb{N}$, we
let $[n]=\\{1,2,\ldots,n\\}$.

##  2\. Lower Bound

In this section, we prove a lower bound for the metric dimension of the
Hamming graphs $HG(n_{1},n_{2},n_{3};3)$.

Given $\mathbf{n}\in\mathcal{N}$ and a subset of vertices $W$ of the Hamming
graph $HG(\mathbf{n};3)$, let $W_{i,a}$ be the set of landmarks in the plane
$x_{i}=a$, i.e.,

$W_{i,a}=\\{(x_{1},x_{2},x_{3})\in W\mid x_{i}=a\\}$

for $1\leq i\leq 3$ and $a\in[n_{i}]$. We call the sets $W_{i,a}$ blocks of
color $i$.

We begin with a constraint on the minimum number of landmarks in the blocks of
a given color. Namely, if $W$ is a resolving set, then the absence of
landmarks in a block forces the other blocks of that color to each contain at
least three landmarks. Additionally, if a block has only one landmark in it,
then the other blocks of that color are forced to each contain at least two
landmarks.

######  Lemma 2.1.

If $W$ is a resolving set for the Hamming graph $G=HG(n_{1},n_{2},n_{3};3)$
(each $n_{i}\geq 3$), then

$|W_{i,a}|+|W_{i,b}|\geq 3$

for all $1\leq i\leq 3$ and distinct $a,b\in[n_{i}]$.

###### Proof.

Let $W$ be a subset of the vertex set of $G$ and let $i=1$ (the proofs for
$i=2,3$ are analogous). First suppose $|W_{1,a}|=0$ and $|W_{1,b}|=2$ for some
$a,b\in[n_{1}]$. Say the two landmarks in $W_{1,b}$ are $(b,x_{1},y_{1})$ and
$(b,x_{2},y_{2})$. Now, since $n_{2},n_{3}\geq 3$, we can choose
$x_{3}\in[n_{2}]-\\{x_{1},x_{2}\\}$ and $y_{3}\in[n_{3}]-\\{y_{1},y_{2}\\}$
and define $(x,y)$ as follows:

$(x,y)=\begin{cases}(x_{1},y_{2})&\text{if $x_{1}\neq x_{2}$ and $y_{1}\neq
y_{2}$}\\\ (x_{1},y_{3})&\text{if $x_{1}=x_{2}$}\\\ (x_{3},y_{1})&\text{if
$y_{1}=y_{2}$.}\end{cases}$

To resolve the vertices $(a,x,y)$ and $(b,x,y)$, we would need a landmark that
has a coordinate in common with one of the vertices but not the other, i.e., a
landmark from $W_{1,a}\cup W_{1,b}$. But $W_{1,a}$ is empty, and, by
construction, $(x,y)$ has exactly one coordinate in common with
$(x_{1},y_{1})$ and exactly one coordinate in common with $(x_{2},y_{2})$,
which implies $(a,x,y)$ and $(b,x,y)$ are distance two from the elements of
$W_{1,b}$. Hence $(a,x,y)$ and $(b,x,y)$ are unresolved.

Next suppose $|W_{1,a}|=1$ and $|W_{1,b}|=1$. Say the landmarks in
$W_{1,a}\cup W_{1,b}$ are $(a,x_{1},y_{1})$ and $(b,x_{2},y_{2})$. Defining
$(x,y)$ as in the previous case, we can similarly show that $(a,x,y)$ and
$(b,x,y)$ are distance two to the landmarks in $W_{1,a}\cup W_{1,b}$ and are
hence unresolved.

Finally, if $|W_{1,a}|+|W_{1,b}|<2$, the case is all the worse, for if $W$ was
resolving, then we could add another landmark to $W_{1,a}\cup W_{1,b}$ to
create a resolving set $W^{\prime}$ with
$|W^{\prime}_{1,a}|+|W^{\prime}_{1,b}|=2$, a contradiction. ∎

We next use the pairwise bound from Lemma 2.1 to determine a lower bound on
the total number of landmarks required to resolve Hamming graphs
$HG(\mathbf{n};3)$.

######  Theorem 2.2.

For $n_{3}\geq n_{2}\geq n_{1}\geq 3$, the Hamming graph
$G=HG(n_{1},n_{2},n_{3};3)$ cannot be resolved with fewer than $2n_{3}-1$
landmarks.

###### Proof.

Suppose $W$ resolves $G$. For $1\leq i\leq 3$, the sum
$|W_{i,1}|+|W_{i,2}|+\cdots+|W_{i,n_{i}}|$ is the total number of landmarks in
$W$. If the minimum term in this sum is zero, Lemma 2.1 says the remaining
terms are greater than or equal to three, giving at least $3(n_{i}-1)$
landmarks. If the minimum term is one, Lemma 2.1 says the remaining terms are
greater than or equal to two, giving at least $1+2(n_{i}-1)$ landmarks. If the
minimum term is two, we have at least $2n_{i}$ landmarks. Note that, under the
assumption $n_{i}\geq 3$, we have

$2n_{i}-1<2n_{i}\leq 3(n_{i}-1).$

So, regardless of the minimum term in the sum, we have $2n_{i}-1$ as a lower
bound on the number of landmarks in $W$. In particular, $2n_{3}-1$ is a lower
bound (and with the assumption $n_{3}\geq n_{2}\geq n_{1}$, it is the greatest
of the lower bounds $2n_{i}-1$). ∎

In Section 4, we will show the bound in Theorem 2.2 is sharp by resolving the
Hamming graphs $HG(n,n,n;3)$ for $n\geq 5$ in $2n-1$ landmarks. In
preparation, we develop an equivalent characterization of resolving sets.

##  3\. Landmark Graphs and Forbidden Configurations

A priori, determining whether a subset of vertices $W$ is a resolving set for
a Hamming graph $HG(\mathbf{n};3)$ involves checking whether all pairs of
vertices are resolved. Instead of doing this directly, we shift our focus to
relationships between the elements of $W$. We define an edge-colored
hypergraph based on $W$ and then characterize whether $W$ is resolving in
terms of forbidden edge-colored subgraphs. This characterization will be used
in Section 4 to construct minimum resolving sets for the diagonal family
$HG(n,n,n;3)$.

###  3.1. Landmark graphs and systems

As in Section 2, given a subset of vertices $W$ in a Hamming graph
$HG(\mathbf{n};3)$, let $W_{i,a}$ be the set of elements in $W$ whose $i$-th
coordinate is $a$. To highlight relationships between the coordinates of
elements of $W$, we define the landmark graph $\mathcal{G}(W)$ to be the
hypergraph with vertex set $W$ and hyperedges those $W_{i,a}$ that are
nonempty. We often refer to $\mathcal{G}(W)$ as the graph of $W$. The graph of
$W$ is $3$-regular and has a proper $3$-edge-coloring obtained by assigning
color $i$ to the sets $W_{i,a}$. Note that the hyperedges of color $i$ form a
partition of $W$. In practice, we will think of the first color as blue,
second color as green, and third color as pink. As an example, Fig. 1 shows
the landmark graph of a resolving set for $HG(3,3,3;3)$.

$(1,1,1)$$(1,2,2)$$(1,3,3)$$(2,2,1)$$(2,3,2)$$(2,1,3)$ Figure 1. Landmark
graph $\mathcal{G}(W)$ of a resolving set for $HG(3,3,3;3)$. The six landmarks
in $W$ are $(1,1,1)$, $(1,2,2)$, $(1,3,3)$, $(2,2,1)$, $(2,3,2)$, and
$(2,1,3)$. Landmarks in the same blue (solid) hyperedge have the same first
coordinate; landmarks connected by a green (dotted) edge have the same second
coordinate; and landmarks connected by a pink (dashed) edge have the same
third coordinate.

The following lemma tells us a necessary condition on the structure of the
landmark graph if a diagonal Hamming graph is to be resolved with the lower
bound of $2n-1$ landmarks. We use the phrase “plain edge” to emphasize an edge
with two endpoints (as opposed to a loop or larger hyperedge).

######  Lemma 3.1.

Let $n\geq 3$. If $W$ is a resolving set of $HG(n,n,n;3)$ of size $2n-1$, then
the landmark graph $\mathcal{G}(W)$ has exactly one loop of each color and
exactly $(n-1)$ plain edges of each color.

###### Proof.

Suppose $W$ is a resolving set of $HG(n,n,n;3)$ of size $2n-1$. First, note
that if the $n$ blocks of color $i$ all have size $2$ or greater, then
$|W|\geq 2n$, a contradiction. Hence there must be at least one block of size
$0$ or $1$. But if there is a block of color $i$ that has size $0$, then, by
Lemma 2.1, the other blocks of color $i$ all have size $3$ or greater, which
implies $|W|\geq 3(n-1)>2n-1$, also a contradiction. Thus there must be a
block $W_{i,a}$ of size $1$. Then, by Lemma 2.1, all other blocks $W_{i,b}$
with $b\neq a$ have size at least $2$. Moreover, to get exactly $2n-1$
elements in $W$, the sizes of $W_{i,b}$ for $b\neq a$ cannot exceed $2$. ∎

To optimally resolve the graphs in the diagonal family, we are interested in
subsets $W$ that will produce a graph $\mathcal{G}(W)$ with the structure
given in Lemma 3.1. Our strategy is to start with graphs that produce an equal
number of plain edges of each color and then add on loops. Though not
necessary, we attempt to put all loops at the same vertex to make the analysis
and constructions easier. This leads us to the following definition.

######  Definition 3.2.

Let $n\geq 3$ and $\mathbf{n}=(n,n,n)$. For $W$ a subset of vertices of the
graph $HG(\mathbf{n};3)$, we say $W$ is a 2-basic landmark system provided
that:

  1. (1)

$|W_{i,a}|=2$ for all $1\leq i\leq 3$ and $a\in[n]$; and

  2. (2)

$|W_{i,a}\cap W_{j,b}|\leq 1$ for all $1\leq i<j\leq 3$ and $a,b\in[n]$.

Letting $u=(n+1,n+1,n+1)$, we can extend a $2$-basic landmark system for
$HG(\mathbf{n};3)$ to a triple-looped landmark system $W\cup\\{u\\}$ for
$HG(\mathbf{n}+\mathbf{1};3)$.

Condition (1) ensures that $\mathcal{G}(W)$ only has edges with two endpoints,
and condition (2) ensures that $\mathcal{G}(W)$ has no double edges. Thus,
when $W$ is a $2$-basic landmark system, $\mathcal{G}(W)$ is a simple graph
with $n$ edges of each color. Note that the definition of a landmark system
makes no assertion as to whether $W$ is a resolving set. Our goal is to find
further conditions, based on subgraphs of $\mathcal{G}(W)$, which will allow
us to determine if $W$ is a resolving set.

###  3.2. Subgraphs

Before continuing, we establish notation and definitions for subgraphs. We
denote a path with $n$ vertices as $P_{n}$, a cycle with $n$ vertices as
$C_{n}$, and a complete bipartite graph with parts of size $m$ and $n$ as
$K_{m,n}$. Some of our graphs will have loops and multiple edges, so we denote
a vertex with $n$ loops as $L_{n}$ and a double edge between the same two
vertices as $D_{2}$. We write $G\cup H$ for the disjoint union of graphs $G$
and $H$.

We say edge $e$ covers vertex $u$ if $u\in e$. A subset of edges $E^{\prime}$
determines an edge-induced subgraph consisting of the edges in $E^{\prime}$
and the vertices they cover. In a graph with an edge-coloring, a rainbow
subgraph is a subgraph whose edges are all different colors. We can identify
(almost) every vertex in a Hamming graph with an edge-induced rainbow subgraph
of a landmark graph.

######  Definition 3.3.

Let $\mathbf{n}\in\mathcal{N}$ and let $W$ be a subset of vertices of the
Hamming graph $HG(\mathbf{n};3)$. Given a vertex $\alpha=(a_{1},a_{2},a_{3})$
of the Hamming graph, define the footprint of $\alpha$ (relative to $W$) to be
the subgraph of $\mathcal{G}(W)$ induced by the edges $W_{i,a_{i}}$. If
$W_{i,a_{i}}=\varnothing$ for all $1\leq i\leq 3$, then there is no edge-
induced subgraph and $\alpha$ has no footprint.

Figure 2. If $W$ is a $2$-basic landmark system, then there are four possible
footprints for a non-landmark: rainbow $C_{3}$, $P_{4}$, $P_{3}\cup P_{2}$,
and $3P_{2}$. If $W$ is a triple-looped landmark system, then there are three
additional possible footprints: rainbow $L_{2}\cup P_{2}$, $P_{3}\cup L_{1}$,
and $2P_{2}\cup L_{1}$. Different line styles correspond to different edge
colors.

In Fig. 2, we show the possible footprints of a non-landmark vertex in a
Hamming graph $HG(\mathbf{n};3)$. There are four possible footprints assuming
that $W$ is a $2$-basic landmark system, and three additional footprints
assuming $W$ is a triple-looped landmark system. The vertices of the footprint
of $\alpha$ are the landmarks that have a coordinate in common with $\alpha$,
i.e., the vertices in $W$ that have distance $2$ from $\alpha$ in
$HG(\mathbf{n};3)$. Notice that the footprint of a landmark has three
edges/loops that share a common vertex, which in the case of a triple-looped
landmark system can either be a $K_{1,3}$ or an $L_{3}$. We omit these from
Fig. 2 since landmarks are automatically resolved.

Because we are working with Hamming graphs of diameter two, the following
straightforward but important observation allows us to determine whether $W$
is resolving by examining how footprints overlap.

######  Remark 3.4.

Let $W$ be a subset of vertices of a Hamming graph $HG(\mathbf{n};3)$. Note
that in the Hamming graph, a vertex $(a_{1},a_{2},a_{3})\notin W$ has distance
two to the landmarks in $W_{1,a_{1}}\cup W_{2,a_{2}}\cup W_{3,a_{3}}$ and
distance one to the remaining landmarks in $W$. It follows that distinct
vertices $\alpha=(a_{1},a_{2},a_{3})$ and $\beta=(b_{1},b_{2},b_{3})$ not in
$W$ are resolved if and only if

$W_{1,a_{1}}\cup W_{2,a_{2}}\cup W_{3,a_{3}}\neq W_{1,b_{1}}\cup
W_{2,b_{2}}\cup W_{3,b_{3}},$

i.e., the footprints of $\alpha$ and $\beta$ cover different sets of vertices.

###  3.3. Forbidden configurations for two-basic landmark systems

We are now ready to characterize whether $W$ is resolving based on properties
of the landmark graph of $W$. In particular, we will find necessary and
sufficient conditions in terms of forbidden edge-colored subgraphs. We begin
with two examples of configurations that cannot occur in the landmark graph of
a resolving set.

######  Example 3.5 (Forbidden $4$-cycle).

Let $\mathbf{n}\in\mathcal{N}$ and let $W$ be a subset of vertices of the
graph $HG(\mathbf{n};3)$. Suppose the graph of $W$ contains a $4$-cycle, as
illustrated in Fig. 3, with opposite blue edges
$W_{1,a_{1}}=\\{w_{1},w_{2}\\}$ and $W_{1,b_{1}}=\\{w_{3},w_{4}\\}$, a green
edge $W_{2,a_{2}}=\\{w_{2},w_{3}\\}$, and a pink edge
$W_{3,a_{3}}=\\{w_{1},w_{4}\\}$. Then the vertices $(a_{1},a_{2},a_{3})$ and
$(b_{1},a_{2},a_{3})$ are unresolved in $HG(\mathbf{n};3)$ since neither is a
landmark and

$W_{1,a_{1}}\cup W_{2,a_{2}}\cup
W_{3,a_{3}}=\\{w_{1},w_{2},w_{3},w_{4}\\}=W_{1,b_{1}}\cup W_{2,a_{2}}\cup
W_{3,a_{3}}.$

Similarly, if the edge colors are permuted, there will be an unresolved pair
of vertices.

######  Example 3.6 (Forbidden $6$-cycle).

Let $\mathbf{n}\in\mathcal{N}$ and let $W$ be a subset of vertices of the
graph $HG(\mathbf{n};3)$. Suppose the graph of $W$ contains a $6$-cycle, as
illustrated in Fig. 3, with opposite blue edges
$W_{1,a_{1}}=\\{w_{1},w_{2}\\}$ and $W_{1,b_{1}}=\\{w_{4},w_{5}\\}$; opposite
green edges $W_{2,a_{2}}=\\{w_{5},w_{6}\\}$ and
$W_{2,b_{2}}=\\{w_{2},w_{3}\\}$; and opposite pink edges
$W_{3,a_{3}}=\\{w_{3},w_{4}\\}$ and $W_{3,b_{3}}=\\{w_{1},w_{6}\\}$. Then the
vertices $(a_{1},a_{2},a_{3})$ and $(b_{1},b_{2},b_{3})$ are unresolved in
$HG(\mathbf{n};3)$ since neither is a landmark and

$W_{1,a_{1}}\cup W_{2,a_{2}}\cup
W_{3,a_{3}}=\\{w_{1},w_{2},w_{3},w_{4},w_{5},w_{6}\\}=W_{1,b_{1}}\cup
W_{2,b_{2}}\cup W_{b_{3}}.$

Figure 3. The landmark graph of a resolving set must avoid forbidden
$4$-cycles and forbidden $6$-cycles. The landmark graph of a resolving triple-
looped landmark system must also avoid rainbow triangles. Solid edges are
blue, dashed edges are pink, and dotted edges are green.

When either the $4$-cycle from Example 3.5 (possibly with colors permuted) or
the $6$-cycle from Example 3.6 appear in a landmark graph, the Hamming graph
$HG(\mathbf{n};3)$ is unresolved. We next show that when $W$ is a $2$-basic
landmark system, these are in fact the only configurations we must avoid to
guarantee $W$ is a resolving set.

######  Theorem 3.7.

Let $\mathbf{n}\in\operatorname{diag}(\mathcal{N})$. If $W$ is a $2$-basic
landmark system for the Hamming graph $HG(\mathbf{n};3)$, then $W$ is a
resolving set if and only if the landmark graph $\mathcal{G}(W)$ avoids the
following forbidden subgraphs:

  1. (1)

a $4$-cycle that contains all three colors of edges

  2. (2)

a $6$-cycle with opposite edges of the same color.

###### Proof.

Using Example 3.5 and Example 3.6, we can see that $W$ is not resolving when
the landmark graph $\mathcal{G}(W)$ contains a $4$-cycle that contains all
three colors of edges or a $6$-cycle with opposite edges of the same color.

Conversely, suppose $W$ is a $2$-basic landmark system whose graph
$\mathcal{G}(W)$ avoids forbidden $4$-cycles and $6$-cycles. We will show that
$W$ is a resolving set. Suppose $\alpha=(a_{1},a_{2},a_{3})$ and
$\beta=(b_{1},b_{2},b_{3})$ are distinct vertices in $HG(\mathbf{n};3)$ and
that neither is a landmark. We will show the edges $W_{i,a_{i}}$ cannot cover
the same set of vertices as the edges $W_{i,b_{i}}$. We consider cases based
on the number of vertices covered. Throughout, we use the fact that
$\mathcal{G}(W)$ is a simple graph with a proper $3$-edge coloring.

Case 1 ($3$ vertices). If the edges $W_{i,a_{i}}$ and the edges $W_{i,b_{i}}$
cover the same set of three vertices, then we must have
$W_{i,a_{i}}=W_{i,b_{i}}$ for $i=1,2,3$ since it is not possible to have two
different edges of the same color in a subgraph with only three vertices. But
this contradicts our assumption that $\alpha$ and $\beta$ are distinct.

Case 2 ($4$ vertices). Suppose the edges $W_{i,a_{i}}$ and the edges
$W_{i,b_{i}}$ cover the same set of four vertices. Since $\alpha$ is not a
landmark, the edges $W_{i,a_{i}}$ cannot induce a $K_{1,3}$ and hence must
induce a rainbow path $P_{4}$. Likewise, the edges $W_{i,b_{i}}$ induce a
rainbow path $P_{4}$. The only way for two different rainbow paths to cover
all four vertices is to make a $4$-cycle with one set of opposite edges the
same color and the other two edges different colors, but we are assuming that
$\mathcal{G}(W)$ avoids this forbidden configuration.

Case 3 ($5$ vertices). Suppose the edges $W_{i,a_{i}}$ and the edges
$W_{i,b_{i}}$ cover the same set of five vertices. Then each set of edges
induces a rainbow $P_{2}\cup P_{3}$. Up to permuting colors, suppose the first
$P_{2}\cup P_{3}$ has blue edge $W_{1,a_{1}}=\\{x,y\\}$, green edge
$W_{2,a_{2}}=\\{u,v\\}$, and pink edge $W_{3,a_{3}}=\\{u,w\\}$, as in Fig.
4[A]. If the second rainbow $P_{2}\cup P_{3}$ also has blue edge $\\{x,y\\}$,
then since there are no double edges, the green and pink edges must also
coincide, i.e., $W_{2,a_{2}}=W_{2,b_{2}}$ and $W_{3,a_{3}}=W_{3,b_{3}}$,
contradicting $\alpha$ and $\beta$ being distinct. The only other option is
for the second rainbow $P_{2}\cup P_{3}$ to have blue edge
$W_{1,b_{1}}=\\{v,w\\}$ as in Fig. 4[B]. If the blue edge $vw$ is the $P_{2}$,
then the edges $W_{2,b_{2}}$ and $W_{3,b_{3}}$ would have to create a green-
pink path $xuy$ or $yux$, but this is not possible with a proper edge
coloring. If the blue edge $vw$ is part of the $P_{3}$, then the $P_{2}$ would
have to create a double edge between $x$ and $y$, which is not allowed.

Case 4 ($6$ vertices). Suppose the edges $W_{i,a_{i}}$ and the edges
$W_{i,b_{i}}$ cover the same set of six vertices. Then each set of edges
creates a rainbow matching $3P_{2}$. We will show the only way this can happen
is if the edges of the matchings together form a forbidden $6$-cycle. Suppose
the first rainbow matching has blue edge $W_{1,a_{1}}=\\{u,v\\}$, green edge
$W_{2,a_{2}}=\\{w,x\\}$, and pink edge $W_{3,a_{3}}=\\{y,z\\}$, as in Fig. 4[C
and D]. The two matchings must differ by at least one edge, so up to permuting
colors, suppose they have different pink edges. Then $W_{3,b_{3}}$ must
connect a vertex from the blue edge $W_{1,a_{1}}$ to a vertex from the green
edge $W_{2,a_{2}}$. Without loss of generality, say $W_{3,b_{3}}=\\{v,w\\}$.
Now, the blue edge $W_{1,b_{1}}$ and green edge $W_{2,b_{2}}$ must cover the
vertices $u$, $x$, $y$, and $z$. There are two ways to do this, leading to
either the $6$-cycle $uvwxyzu$ or $uvwxzyu$. Either way, the pattern of edge
colors around the cycle is blue, pink, green, blue, pink, green. But this is a
contradiction since we assumed that the graph of $W$ has no forbidden
$6$-cycles.

Thus, in all cases, the edges $W_{i,a_{i}}$ and the edges $W_{i,b_{i}}$ cannot
cover the same set of vertices and so $\alpha$ and $\beta$ are resolved. Hence
$W$ is a resolving set. ∎

$u$$w$ $v$$x$ $y$(A)

$u$$w$ $v$$x$ $y$(B)

$u$$v$ $w$$x$ $y$$z$(C)

$u$$v$ $w$$x$ $y$$z$(D)

Figure 4. Illustrations for Cases $3$ and $4$ in the proof of Theorem 3.7.
Line styles correspond to the edge colors blue (solid), green (dotted), and
pink (dashed). (A) and (B) It is not possible for two different rainbow
$P_{2}\cup P_{3}$ graphs to cover the same set of five vertices. (C) and (D)
If two different rainbow matchings cover the same set of six vertices, the
edges together form a forbidden $6$-cycle.

###  3.4. Forbidden configurations for triple-looped landmark systems

We next investigate conditions for when a triple-looped landmark system will
resolve a Hamming graph. We will use these conditions in Section 4 to
construct resolving sets for most of the Hamming graphs $HG(n,n,n;3)$ in
$2n-1$ landmarks.

Recall that the graph of a triple-looped landmark system is obtained from the
graph of a $2$-basic landmark system by adding a vertex with a triple loop.
The next example shows that if there is a rainbow triangle in the graph of a
$2$-basic landmark system, then the extension to a triple-looped landmark
system will not be a resolving set.

######  Example 3.8 (Triangle union triple loop).

Let $\mathbf{n}\in\mathcal{N}$ and let $W$ be a subset of vertices of the
graph $HG(\mathbf{n};3)$. Suppose the graph of $W$ contains a rainbow triangle
with blue edge $W_{1,a_{1}}=\\{w_{1},w_{2}\\}$, green edge
$W_{2,a_{2}}=\\{w_{2},w_{3}\\}$, and pink edge
$W_{3,a_{3}}=\\{w_{3},w_{1}\\}$, as in Fig. 3. Letting
$u=(n_{1}+1,n_{2}+1,n_{3}+1)$, the extension of $W$ to a triple-looped
landmark system $W\cup\\{u\\}$ does not resolve $HG(\mathbf{n}+\mathbf{1};3)$;
for instance, the vertices $(a_{1},a_{2},n_{3}+1)$ and $(a_{1},n_{2}+1,a_{3})$
are unresolved since neither is a landmark and

$W_{1,a_{1}}\cup W_{2,a_{2}}\cup
W_{3,n_{3}+1}=\\{w_{1},w_{2},w_{3},u\\}=W_{1,a_{1}}\cup W_{2,n_{2}+1}\cup
W_{3,a_{3}}.$

The next theorem is analogous to Theorem 3.7, but allows for a triple loop at
a single vertex. Furthermore this theorem allows us to construct minimum
resolving sets in the next section.

######  Theorem 3.9.

Let $\mathbf{n}\in\operatorname{diag}(\mathcal{N})$ and suppose $W$ is a
$2$-basic landmark system for $HG(\mathbf{n};3)$. Let $u=(n+1,n+1,n+1)$. Then
the triple-looped landmark system $W\cup\\{u\\}$ resolves
$HG(\mathbf{n}+\mathbf{1};3)$ if and only if the landmark graph
$\mathcal{G}(W)$ avoids the following forbidden subgraphs:

  1. (1)

a $4$-cycle that contains all three colors of edges,

  2. (2)

a $6$-cycle with opposite edges of the same color, and

  3. (3)

a rainbow triangle.

###### Proof.

Let $V_{n}$ and $V_{n+1}$ be the vertex sets of the Hamming graphs
$HG(\mathbf{n};3)$ and $HG(\mathbf{n}+\mathbf{1};3)$, respectively. If a
forbidden $4$-cycle or $6$-cycle exists in the graph of $W$, then $W$ does not
resolve $HG(\mathbf{n};3)$, and so $W\cup\\{u\\}$ does not resolve
$HG(\mathbf{n}+\mathbf{1};3)$. This is because the new landmark $u$ is
adjacent to all of the vertices in $V_{n}$, so vertices in $V_{n}$ can only be
resolved using a landmark from $W$. If a rainbow triangle exists in the graph
of $W$, then a rainbow triangle and triple loop exist in the graph of
$W\cup\\{u\\}$, so by Example 3.8, $W\cup\\{u\\}$ does not resolve
$HG(\mathbf{n}+\mathbf{1};3)$.

Conversely, suppose $W$ is a $2$-basic landmark system such that
$\mathcal{G}(W)$ avoids forbidden $4$-cycles, forbidden $6$-cycles, and
rainbow triangles. We will show that $W\cup\\{u\\}$ is a resolving set for
$HG(\mathbf{n}+\mathbf{1};3)$.

Suppose $\alpha=(a_{1},a_{2},a_{3})$ and $\beta=(b_{1},b_{2},b_{3})$ are
distinct vertices in $HG(\mathbf{n}+\mathbf{1};3)$ and that neither is a
landmark. Note that, by Theorem 3.7, $W$ is a resolving set for
$HG(\mathbf{n};3)$, so if $\alpha$ and $\beta$ are both in $V_{n}$, then they
are resolved by some landmark in $W$. If one vertex, say $\alpha$, is in
$V_{n}$ and the other vertex, $\beta$, is in $V_{n+1}-V_{n}$, then $u$
resolves $\alpha$ and $\beta$, as $u$ sees $\beta$ but not $\alpha$. The
remaining case, where $\alpha$ and $\beta$ are both in $V_{n+1}-V_{n}$,
requires the most work. We will show the edges $W_{i,a_{i}}$ cannot cover the
same set of vertices as the edges $W_{i,b_{i}}$. We consider cases based on
the number of vertices covered.

Note that the edges $W_{i,a_{i}}$ (likewise, $W_{i,b_{i}}$) must consist of
either a loop and two plain edges, or a double loop and a plain edge. Thus the
number of vertices covered ranges between three and five.

Case 1 ($3$ vertices). If the edges $W_{i,a_{i}}$ and the edges $W_{i,b_{i}}$
cover the same set of three vertices, then each set of edges induces a rainbow
$P_{2}\cup L_{2}$, where the $L_{2}$ must be at the same vertex. And then we
must have $W_{i,a_{i}}=W_{i,b_{i}}$ for $i=1,2,3$ since there are no double
edges. But this contradicts our assumption that $\alpha$ and $\beta$ are
distinct.

Case 2 ($4$ vertices). Suppose the edges $W_{i,a_{i}}$ and the edges
$W_{i,b_{i}}$ cover the same set of four vertices. Both edge sets induce a
rainbow $P_{3}\cup L_{1}$. Since the loops occur at the same vertex, the only
way for two different rainbow $P_{3}\cup L_{1}$ subgraphs to cover all four
vertices is if they together make a $C_{3}\cup L_{2}$, but we are assuming
that $\mathcal{G}(W)$ avoids rainbow triangles.

Case 3 ($5$ vertices). Suppose the edges $W_{i,a_{i}}$ and the edges
$W_{i,b_{i}}$ cover the same set of five vertices. Both edge sets induce a
rainbow $P_{2}\cup P_{2}\cup L_{1}$. Both sets must have their $L_{1}$ at the
same vertex (although possibly different colors). There is no way to make two
different rainbow $2P_{2}$’s cover the same set of $4$ vertices since once the
first rainbow $2P_{2}$ is placed, the only other possible $2P_{2}$ would have
edges of the same color instead of different colors. Hence we must have
$W_{i,a_{i}}=W_{i,b_{i}}$ for $i=1,2,3$, which contradicts $\alpha$ and
$\beta$ being distinct.

Thus in all cases, the edges $W_{i,a_{i}}$ and the edges $W_{i,b_{i}}$ cannot
cover the same set of vertices and so $\alpha$ and $\beta$ are resolved. Hence
$W\cup\\{u\\}$ is a resolving set. ∎

##  4\. Metric Bases for the Diagonal Family

Now that we know which configurations must be avoided in the landmark graph,
we are able to construct minimum resolving sets for the diagonal family of
Hamming graphs $HG(n,n,n;3)$. The graphs with $n\geq 5$ achieve the metric
dimension lower bound of $2n-1$, while the graphs for $n=3$ and $n=4$ require
$2n$ landmarks.

###  4.1. Construction of metric bases

For the main case of $n\geq 5$, our strategy will be to construct an order
$2(n-1)$ graph $G$ that avoids the configurations from Theorem 3.9 and define
a $2$-basic landmark system $W$ with $\mathcal{G}(W)=G$. We then extend $W$ to
a triple-looped landmark system that resolves $HG(n,n,n;3)$ in $2n-1$
landmarks.

######  Lemma 4.1.

For $k\geq 6$, there exists a cubic graph on $2k$ vertices with a proper
$3$-edge-coloring that avoids the forbidden edge-colored subgraphs from
Theorem 3.9:

  1. (1)

a $4$-cycle that contains all three colors of edges,

  2. (2)

a $6$-cycle with opposite edges of the same color, and

  3. (3)

a rainbow triangle.

###### Proof.

To construct a graph with the desired properties (see Fig. 5), we let $k\geq
6$ and start with an order $2k$ Hamiltonian cycle whose edge colors alternate,
say blue and pink. Next, we label the vertices of the cycle in a way that
helps us define green edges and avoid the forbidden configurations. Let
$m=k-4$. If $k$ is even, label the vertices of the cycle in the order

$(p_{1},p_{2},p_{3},p_{4},q_{1},\ldots,q_{m},p_{1}^{\prime},p_{3}^{\prime},p_{2}^{\prime},p_{4}^{\prime},q_{m}^{\prime},\ldots,q_{1}^{\prime}),$

and if $k$ is odd, label the vertices in the order

$(p_{1},p_{2},p_{3},p_{4},q_{1},\ldots,q_{m},p_{2}^{\prime},p_{4}^{\prime},p_{1}^{\prime},p_{3}^{\prime},q_{m}^{\prime},\ldots,q_{1}^{\prime}).$

To finish the graph, add green edges $p_{i}p_{i}^{\prime}$ (for $i=1,2,3,4$)
and $q_{i}q_{i}^{\prime}$ (for $i=1,\ldots,m$). We claim these graphs avoid
the forbidden triangles, $4$-cycles, and $6$-cycles of Theorem 3.9.

If there was a rainbow triangle, the outer Hamiltonian cycle would contain a
sequence of vertices $u,v,u^{\prime}$, which we don’t have.

If there was a forbidden $4$-cycle with two blue edges or two pink edges, then
we would have a path $uvwu^{\prime}$ along the outer Hamiltonian cycle, but
this does not occur ($u$ and $u^{\prime}$ are always at least five edges
apart). If there was a forbidden $4$-cycle with two green edges, then there
would exist edges $uv$ and $u^{\prime}v^{\prime}$ of different colors, but
this does not occur in our construction.

Lastly, if there was a forbidden $6$-cycle, then it would include a path $uvw$
on the outer Hamiltonian cycle such that $u^{\prime}$ and $w^{\prime}$ are
distance two apart on the Hamiltonian cycle. This would imply $u$ and $w$ are
both $q$’s, but then we see that the coloring of the $6$-cycle is not a
forbidden coloring. ∎

$p_{1}$$p_{2}$$p_{3}$$p_{4}$$q_{1}$$q_{2}$$p_{1}^{\prime}$$p_{3}^{\prime}$$p_{2}^{\prime}$$p_{4}^{\prime}$$q_{2}^{\prime}$$q_{1}^{\prime}$
$p_{1}$$p_{2}$$p_{3}$$p_{4}$$q_{1}$$q_{2}$$p_{1}^{\prime}$$p_{3}^{\prime}$$p_{2}^{\prime}$$p_{4}^{\prime}$$q_{2}^{\prime}$$q_{1}^{\prime}$$q_{m}$$q_{m-1}$$\vdots$$q_{m}^{\prime}$$q_{m-1}^{\prime}$$\vdots$
$p_{1}$$p_{2}$$p_{3}$$p_{4}$$q_{1}$$q_{2}$$p_{1}^{\prime}$$p_{3}^{\prime}$$p_{2}^{\prime}$$p_{4}^{\prime}$$q_{2}^{\prime}$$q_{1}^{\prime}$$q_{3}$$q_{3}^{\prime}$
$p_{1}$$p_{2}$$p_{3}$$p_{4}$$q_{1}$$q_{2}$$p_{1}^{\prime}$$p_{3}^{\prime}$$p_{2}^{\prime}$$p_{4}^{\prime}$$q_{2}^{\prime}$$q_{1}^{\prime}$$q_{m}$$q_{m-1}$$\vdots$$q_{m}^{\prime}$$q_{m-1}^{\prime}$$\vdots$

Figure 5. Cubic graph on $2k$ vertices with a proper $3$-edge-coloring for
even $k\geq 6$ (top row images) and odd $k\geq 7$ (bottow row images). Edges
of outer Hamiltonian cycle alternate blue (solid) and pink (dashed). All other
edges are green (dotted). Forbidden $4$-cycles, forbidden $6$-cycles, and
rainbow triangles are avoided.

######  Remark 4.2.

Note that Lemma 4.1 is not true for $k=5$. Using GraphData in Mathematica
[Inc], we find that, of the $21$ cubic graphs with $10$ vertices ($19$ of
which are connected [BvCS77]), there are only five that are triangle-free and
have edge-chromatic number $3$. Moreover, it can be verified that all possible
proper edge-colorings of these graphs lead to a forbidden configuration.

In Proposition 4.3, we show that for $n\geq 5$, the diagonal family
$HG(n,n,n;3)$ achieves the metric dimension lower bound $2n-1$. To prove the
cases $n\geq 7$, we make use of the graphs from Lemma 4.1, and to prove the
cases $n=5$ and $n=6$ we use ad hoc constructions.

######  Proposition 4.3.

For $n\geq 5$, the Hamming graph $HG(n,n,n;3)$ has metric dimension $2n-1$.

###### Proof.

For $n\geq 7$, let $k=n-1$ and let $G$ be the graph constructed as in Lemma
4.1. Label the blue edges $1,\ldots,n-1$ and likewise for the green and pink
edges. If the blue, green, and pink edges incident to a vertex are labeled
$a_{1}$, $a_{2}$, and $a_{3}$, respectively, then we create a landmark
$(a_{1},a_{2},a_{3})$. Do this for each vertex in $G$ to get a landmark set
$W$ with graph $\mathcal{G}(W)=G$. The order $2(n-1)$ graph $G$ avoids
forbidden $4$-cycles and $6$-cycles and rainbow triangles, so by Theorem 3.9,
if we let $u=(n,n,n)$, then the set $W\cup\\{u\\}$ is a resolving set of size
$2n-1$ for $HG(n,n,n;3)$. By the lower bound in Theorem 2.2, $W\cup\\{u\\}$ is
a minimum resolving set.

For $n=5$, note that Lemma 4.1 is also true for $k=4$. As illustrated in Fig.
6, there is a proper $3$-edge coloring of the order $8$ Möbius ladder that
avoids rainbow triangles, forbidden $4$-cycles, and forbidden $6$-cycles. Thus
we can resolve $HG(5,5,5;3)$ in the style of the previous paragraph, taking
$G$ to be the colored Möbius ladder.

For $n=6$, we take a different approach, as Lemma 4.1 is not true for $k=5$
(see Remark 4.2). In this case, rather than concentrating all loops at the
same vertex, we spread them throughout the landmark graph. Letting symbol $k$
in row $i$, column $j$ correspond to a landmark $(i,j,k)$, we can verify by
computer that the partial Latin square

$\begin{array}[]{|c|c|c|c|c|c|}\hline\cr&1&&&&\\\ \hline\cr 1&2&&&&\\\
\hline\cr&&2&3&&\\\ \hline\cr&&3&4&&\\\ \hline\cr&&&&4&5\\\
\hline\cr&&&&5&6\\\ \hline\cr\end{array}$

represents a resolving set of size $11$ for $HG(6,6,6;3)$.111Incidentally, our
approach to constructing this resolving set of size $11$ was to attempt to
prove there was none. We failed and found this one! Our code for checking
resolving sets with SageMath [The22] is available at
https://github.com/fostergreenwood/metric-dimension. ∎

Figure 6. Proper $3$-edge coloring of the order eight Möbius ladder $M_{4}$.
Edges of outer Hamiltonian cycle alternate blue (solid) and pink (dashed),
while green (dotted) edges join antipodal points on the cycle. All forbidden
configurations are avoided.

###  4.2. Small exceptions

In contrast to the diagonal cases $n\geq 5$, which can be resolved in $2n-1$
landmarks, we will show that for $n=3$ and $n=4$, the metric dimension of
$HG(n,n,n;3)$ is $2n$.

To show that $HG(n,n,n;3)$ cannot be resolved in $2n-1$ landmarks for $n=3,4$,
we need to consider all possible subsets of $2n-1$ vertices, not only triple-
looped landmark systems. With fewer constraints on $W$, there are more
possible footprints than shown in Fig. 2—in general, a footprint may have
double edges, and loops do not all have to be at the same vertex. In turn,
there are more ways for two different footprints to cover the same set of
vertices in the landmark graph, and such configurations indicate pairs of
unresolved vertices in the Hamming graph.

In addition to the forbidden $4$-cycles and $6$-cycles in Fig. 3, the landmark
graph of a resolving set has to avoid the configurations in Fig. 7. The list
is not exhaustive but includes what we need in order to prove Lemma 4.4 and
Lemma 4.5. Of the configurations we require, we only show one representative
coloring, with the understanding that the colors may be permuted. Note that
which edges are the same color is significant; for example, in the long
$2$-headed snake, it is important that the middle two colors match the loop
colors on the end, but in the opposite order.

Snake

Short 2-Headed Snake

Medium 2-Headed Snake

Long 2-Headed Snake

Short Snake $\cup$ Double Edge

Triangle $\cup$ Double Loop

Loopy Triangle

ORTwo Double Edges

Triangle $\cup$ Double Edge

ORDouble Edge $\cup$ Double Loop

Figure 7. Some configurations of two different footprints covering the same
set of vertices. Different line styles correspond to different edge colors.
Configurations with only two colors imply the addition of any edge of the
third color will cause an issue.

######  Lemma 4.4.

The Hamming graph $HG(3,3,3;3)$ has metric dimension $6$.

###### Proof.

Letting symbol $k$ in row $i$, column $j$ corresponds to a landmark $(i,j,k)$,
we can verify by computer that the partial Latin square

$\begin{array}[]{|c|c|c|}\hline\cr 1&2&3\\\ \hline\cr 3&1&2\\\
\hline\cr\phantom{2}&\phantom{1}&\phantom{3}\\\ \hline\cr\end{array}$

represents a resolving set of size $6$ (whose landmark graph is in Fig. 1).

To show there is no smaller resolving set, suppose, towards a contradiction,
that we have a resolving set $W$ with only $5$ vertices. Then by Lemma 3.1,
the graph of $W$ has 2 plain edges and a loop for each of three colors (say
blue, green, pink). We will show that all possible placements of the edges and
loops lead to a forbidden configuration.

Case 1 (no double edges). First suppose the graph of $W$ has no double edges.

Case 1.1 (blue and green loop on same vertex). If the blue and green loops are
on the same vertex, say $u$, then the remaining two blue edges and two green
edges are forced to create an alternating $4$-cycle. Note that distinct
vertices in the $4$-cycle cannot be joined by a pink edge since that would
create either a double edge or a forbidden $C_{3}\cup L_{2}$. Thus every pink
plain edge must have $u$ as one of its endpoints. But this means we can only
have one pink plain edge instead of the two required.

Case 1.2 (blue and green loop on different vertices). Suppose the graph of $W$
has a blue loop at vertex $b$ and a green loop at vertex $g$. Now there must
be a green edge, say $bu$, and a blue edge, say $gv$. Note that if we had
$u=v$, then the remaining blue and green edges would create a double edge.
Thus we have $u\neq v$. Now, if the remaining vertex is labeled $w$, we are
forced to have a blue edge $wu$ and a green edge $wv$. We claim there is no
way to place a pink at $w$. A loop at $w$ gives short two-headed snakes ($buw$
and $gvw$). A plain pink edge from $w$ causes a double edge ($uw$ or $vw$) or
a snake ($buwg$ or $gvwb$).

Case 2 (double edge exists). Next, suppose the graph of $W$ has a double edge.
Without loss of generality, say it is a blue-green double edge between
vertices $u$ and $v$. Then, to avoid a forbidden configuration, the blue and
green loops must be on different vertices, say $b$ and $g$. If we label the
final vertex as $w$, the only way to place the remaining blue and green edges
is with a green edge $bw$ and a blue edge $gw$. We claim there is no way to
place a pink at $b$. A plain pink edge $bu$ or $bv$ give us a snake with head
$g$. A pink edge $bw$ creates a second double edge. A pink loop at $b$ creates
a $D_{2}\cup L_{2}$. A pink edge $bg$ creates a forbidden $D_{2}\cup C_{3}$.

Since all possibilities lead to forbidden configurations, there is no way to
resolve the Hamming graph $HG(3,3,3;3)$ using only five landmarks. ∎

######  Lemma 4.5.

The Hamming graph $HG(4,4,4;3)$ has metric dimension $8$.

###### Proof.

To construct a resolving set, let $M_{4}$ be the order $8$ edge-colored Möbius
ladder in Fig. 6. Number the blue (likewise, green and pink) edges
$1,\ldots,4$. If the blue, green, and pink edges incident to a vertex are
labeled $a_{1}$, $a_{2}$, and $a_{3}$, respectively, then we create a landmark
$(a_{1},a_{2},a_{3})$. Do this for each vertex in $M_{4}$ to get a landmark
set $W$ with graph $\mathcal{G}(W)=M_{4}$. By Theorem 3.7, the set $W$ is a
resolving set of size $8$ for $HG(4,4,4;3)$.

To show there is no smaller resolving set, suppose, towards a contradiction,
that we have a resolving set $W$ with only $7$ vertices. Then by Lemma 3.1,
the graph of $W$ has for each color three plain edges and a loop.

Case 1 (no double edges). First suppose the graph of $W$ has no double edges.

Case 1.1 (blue and green loop on same vertex). Suppose the blue and green
loops are on the same vertex, say $u$. Covering the six remaining vertices, we
have three blue edges that make a perfect matching and three green edges that
make a perfect matching. Since we are in the case of no double edges, it is
straightforward to verify that the edges of the two matchings must combine to
create an alternating blue-green $6$-cycle.

Now we try to determine the pink edges. Note that distinct vertices in the
$6$-cycle cannot be joined by a pink edge since that would create either a
double edge, a $C_{3}\cup L_{2}$, or a forbidden $4$-cycle. Thus every pink
plain edge must have $u$ as one of its endpoints. But this means we can only
have one pink plain edge instead of the three required.

Case 1.2 (blue and green loops on different vertices). Suppose the graph of
$W$ has a blue loop at vertex $b$ and a green loop at vertex $g$. Now there
must be a green edge, say $bu$, and a blue edge, say $gv$.

Case 1.2.1 ($u=v$). If $u=v$, then the remaining blue and green edges create
an alternating $4$-cycle. Note that we cannot have a pink edge from $b$ or $g$
to a vertex on the $4$-cycle, since that would create a snake with head $g$ or
$b$. We also cannot have a pink loop at $b$ or $g$ since that creates a short
two-headed snake $bug$. To avoid double edges, the only remaining option is a
pink edge $bg$. Now, we cannot have a pink loop at $u$ (since it would create
a triangle with a loop at each vertex), so there must be a pink edge from $u$
to a vertex, say $w$, on the blue-green $4$-cycle. Since we can’t have a
double edge, the pink loop is forced to be at the vertex $w^{\prime}$ on the
$4$-cycle that is nonadjacent to $w$. But now there is a long two-headed snake
(with heads $b$ and $w^{\prime}$).

Case 1.2.2 ($u\neq v$). If $u\neq v$, then we have a blue edge, say
$uu^{\prime}$ and a green edge $vv^{\prime}$. Note that $u^{\prime}\neq
v^{\prime}$ since $u^{\prime}=v^{\prime}$ would force a double edge with the
remaining blue and green edges. There is only one vertex remaining, call it
$w$, and we are forced to have a green edge $wu^{\prime}$ and a blue edge
$wv^{\prime}$.

Now we consider pink edges at $u^{\prime}$ and $v^{\prime}$. Due to the path
$buu^{\prime}$, we cannot have a pink loop at $u^{\prime}$ (would create a
short two-headed snake), and the only way to avoid a double edge or a snake
with head $b$ is to put a pink edge $u^{\prime}b$. Similarly, we must have a
pink edge $v^{\prime}g$. But now we have a long two-headed snake
$bu^{\prime}wv^{\prime}g$.

Case 2 (there exists a double edge). By symmetry of permuting colors, it
suffices to consider the case of a blue-green double edge, say between
vertices $u$ and $v$. Then the blue and green loops must be at distinct
vertices, say $b$ and $g$ (otherwise we obtain $D_{2}\cup L_{2}$). Now, there
is a green edge from $b$ to some vertex $u^{\prime}$ and a blue edge from $g$
to some vertex $v^{\prime}$. If $u^{\prime}=v^{\prime}$, we would be forced to
make a blue-green double edge on the remaining two vertices which gives two
double edges which is forbidden, so it must be that $u^{\prime}\neq
v^{\prime}$. Similar to Case 1.2.2, there is only one vertex remaining, call
it $w$, and we are forced to create a blue edge $u^{\prime}w$ and a green edge
$v^{\prime}w$.

Now we consider pink edges. Note that at $w$, we cannot have a pink loop since
we would get a short two-headed snake $bu^{\prime}w$. We also cannot have a
pink edge $wu$ or $wv$ since that would create a snake with head $b$ or $g$. A
pink edge $wu^{\prime}$ or $wv^{\prime}$ would create two double edges.
Lastly, a pink edge $wb$ or $wg$ would create a $C_{3}\cup D_{2}$. Thus there
is no way to place a pink at $w$. This completes the case where the graph of
$W$ has a double edge.

Since all possibilities lead to forbidden configurations, there is no way to
resolve the Hamming graph $HG(4,4,4;3)$ using only seven landmarks. ∎

###  4.3. Conclusion and further directions

Compiling the results of the previous two subsections, we now have the metric
dimension for all graphs in the diagonal family $HG(n,n,n;3)$ for $n\geq 3$.

######  Theorem 4.6.

For $n\geq 3$, the metric dimension of the Hamming graph $HG(n,n,n;3)$ is

$\dim HG(n,n,n;3)=\begin{cases}2n&\text{if $n\in\\{3,4\\}$}\\\ 2n-1&\text{if
$n\geq 5$.}\end{cases}$

###### Proof.

This is a corollary of Proposition 4.3, Lemma 4.4, and Lemma 4.5. ∎

We are currently working to generalize the results of Section 3 and construct
minimum resolving sets for non-diagonal graphs $HG(n_{1},n_{2},n_{3};3)$.
These graphs are of special interest because when the $n_{i}$’s are distinct
odd primes, the graphs are isomorphic to unitary Cayley graphs [San10]. We
know that at least some of these graphs also achieve the lower bound of
Theorem 2.2, as illustrated in our final example.

######  Example 4.7.

Letting symbol $k$ in row $i$, column $j$ correspond to a landmark $(i,j,k)$,
we can check by computer that the partial Latin rectangle

$\begin{array}[]{|c|c|c|c|c|c|c|}\hline\cr 1&2&3&10&&&\\\ \hline\cr
4&5&6&1&2&3&\\\ \hline\cr 7&8&9&4&5&6&\\\ \hline\cr 10&&&7&8&9&\phantom{10}\\\
\hline\cr\phantom{10}&\phantom{10}&\phantom{10}&\phantom{10}&\phantom{10}&\phantom{10}&11\\\
\hline\cr\end{array}$

represents a minimum resolving set of size $21$ for the graph $HG(5,7,11;3)$.

## References

  * [BGKT19] Boštjan Brešar, Nicolas Gastineau, Sandi Klavžar, and Olivier Togni.  Exact distance graphs of product graphs.  Graphs Combin., 35(6):1555–1569, 2019.  doi:10.1007/s00373-019-02089-0.
  * [BvCS77] F. C. Bussemaker, S. Čobeljić, D. M. Cvetković, and J. J. Seidel.  Cubic graphs on $\leq 14$ vertices.  J. Combinatorial Theory Ser. B, 23(2-3):234–235, 1977.  doi:10.1016/0095-8956(77)90034-x.
  * [CHM+07] José Cáceres, Carmen Hernando, Mercè Mora, Ignacio M. Pelayo, María L. Puertas, Carlos Seara, and David R. Wood.  On the metric dimension of Cartesian products of graphs.  SIAM J. Discrete Math., 21(2):423–441, 2007.  doi:10.1137/050641867.
  * [CM66] David G. Cantor and W. H. Mills.  Determination of a subset from certain combinatorial properties.  Canadian J. Math., 18:42–48, 1966.  doi:10.4153/CJM-1966-007-2.
  * [ER63] Paul Erdős and Alfréd Rényi.  On two problems of information theory.  Magyar Tud. Akad. Mat. Kutató Int. Közl., 8:229–243, 1963\.
  * [HM76] Frank Harary and Robert A. Melter.  On the metric dimension of a graph.  Ars Combin., 2:191–195, 1976.
  * [Inc] Wolfram Research, Inc.  Mathematica, Version 12.0.  Champaign, IL, 2019.
  * [JLL19] Ville Junnila, Tero Laihonen, and Tuomo Lehtilä.  On a conjecture regarding identification in Hamming graphs.  Electron. J. Combin., 26(2):Paper No. 2.45, 25, 2019.  doi:10.37236/7828.
  * [JP19] Zilin Jiang and Nikita Polyanskii.  On the metric dimension of cartesian powers of a graph.  Journal of Combinatorial Theory, Series A, 165:1–14, 2019.  URL: https://www.sciencedirect.com/science/article/pii/S0097316519300032, doi:https://doi.org/10.1016/j.jcta.2019.01.002.
  * [KY21] Dorota Kuziak and Ismael G. Yero.  Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results, 2021.  URL: https://arxiv.org/abs/2107.04877, doi:10.48550/ARXIV.2107.04877.
  * [Lin64] Bernt Lindström.  On a combinatory detection problem. I.  Magyar Tud. Akad. Mat. Kutató Int. Közl., 9:195–207, 1964\.
  * [LTBL20] Lucas Laird, Richard C. Tillquist, Stephen Becker, and Manuel E. Lladser.  Resolvability of Hamming graphs.  SIAM J. Discrete Math., 34(4):2063–2081, 2020.  doi:10.1137/19M1274511.
  * [LY22] Changhong Lu and Qingjie Ye.  A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem.  Discrete Applied Mathematics, 309:147–159, 2022.  URL: https://www.sciencedirect.com/science/article/pii/S0166218X21004686, doi:https://doi.org/10.1016/j.dam.2021.11.016.
  * [San10] Torsten Sander.  Eigenspaces of Hamming graphs and unitary Cayley graphs.  Ars Math. Contemp., 3(1):13–19, 2010.  doi:10.26493/1855-3974.100.7f8.
  * [Sla75] Peter J. Slater.  Leaves of trees.  In Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), pages 549–559. Congressus Numerantium, No. XIV, 1975.
  * [TFL21] Richard C. Tillquist, Rafael M. Frongillo, and Manuel E. Lladser.  Getting the lay of the land in discrete space: A survey of metric dimension and its applications, 2021.  URL: https://arxiv.org/abs/2104.07201, doi:10.48550/ARXIV.2104.07201.
  * [The22] The Sage Developers.  SageMath, the Sage Mathematics Software System (Version 9.6), 2022.  https://www.sagemath.org.  doi:https://doi.org/10.5281/zenodo.593563.