# The metric dimension of the total graph of a semiring

David Dolžan  D. Dolžan: Department of Mathematics, Faculty of Mathematics and
Physics, University of Ljubljana, Jadranska 19, SI-1000 Ljubljana, Slovenia,
and Institute of Mathematics, Physics and Mechanics, Jadranska 19, SI-1000
Ljubljana, Slovenia; e-mail<EMAIL_ADDRESS>
(Date: August 28, 2024)

###### Abstract.

We calculate the metric dimension of the total graph of a direct product of
finite commutative antinegative semirings with their sets of zero-divisors
closed under addition.

###### Key words and phrases:

semiring, zero-divisor, graph, metric dimension

###### 2010 Mathematics Subject Classification:

16Y60, 05C25

The author acknowledges the financial support from the Slovenian Research
Agency (research core funding No. P1-0222)

##  1\. Introduction

Of the many ways one can prescribe a graph to an algebraic structure, one of
the most important ones is the total graph. The total graph of a ring or a
semiring $S$ is a graph with all elements of $S$ as vertices, and for distinct
$x,y\in S$, the vertices $x$ and $y$ are adjacent if and only if $x+y$ is a
zero-divisor in $S$. Total graph has been firstly studied in [2] for
commutative rings and in [9] for non-commutative rings. Later, it has been
studied in [10, 11] in the setting of commutative semirings and in [15] in the
case of matrices over the Boolean semiring.

In a simple undirected graph, there exist a couple of natural ways to
distinguish the vertices from one another - such ideas appear already in
Sumner [26] and Entringer and Gassman [12]. Among them, one of the most
important ones is the metric dimension of a graph. Let us explain the
definition. Choose an ordered subset $W=\\{w_{1},w_{2},\ldots,w_{k}\\}$ of the
vertex set of graph $G$. Then, for a vertex $v$ in $G$, the vector
$(d(v,w_{1}),d(v,w_{2}),\ldots,d(v,w_{k}))$ is called the _representation_ of
$v$ with respect to $W$. A set $W$ is called a _resolving set_ for $G$ if
distinct vertices of $G$ have distinct representations with respect to $W$. A
resolving set of minimal cardinality for $G$ is called a _basis_ of $G$ and
the cardinality of the basis is defined as the _metric dimension_ of $G$, and
denoted by $\dim(G)$.

The metric dimension was studied by Slater [24], while trying to determine the
location of an intruder in a network. The notion was then also studied by
Harary and Melter [13]. The metric dimension has later been used in many
applications, for example in pharmaceutical chemistry [4], robot navigation in
space [16], combinatorial optimization [23] and sonar and coast guard long
range navigation [24, 25].

In view of studying the metric dimensions of graphs corresponding to different
algebraic structures, the metric dimension of a zero-divisor graph of a
commutative ring was studied in [18, 19, 20, 21, 22], a zero-divisor graph of
a matrix semiring in [8], a total graph of a finite commutative ring in [6],
an annihilating-ideal graph of a finite ring in [7], and a commuting graph of
a dihedral group in [1].

In this paper, we study the metric dimension of the total graph of a direct
product of finite commutative antinegative semirings. A _semiring_ is a set
$S$ equipped with binary operations $+$ and $\cdot$ such that $(S,+)$ is a
commutative monoid with identity element 0 and $(S,\cdot)$ is a monoid with
identity element 1, while both operations in $S$ are connected by
distributivity. We also assume that $0$ annihilates $S$. Semiring $S$ is
called _commutative_ if we have $ab=ba$ for all $a,b\in S$ and _antinegative_
or _zero-sum-free_ (or simply, an _antiring_), if $a+b=0$ for $a,b\in S$
implies $a=b=0$. Commutative semirings often arise naturally, since the set of
nonnegative integers (or reals) with the usual operations of addition and
multiplication forms a commutative semiring. But there are many more examples,
as distributive lattices, tropical semirings, dioids, fuzzy algebras, inclines
and bottleneck algebras are all different examples of commutative semirings.
The simplest semiring is the Boolean semiring $\mathcal{B}=\\{0,1\\}$, where
$1+1=1$. The theory of semirings also provides many applications, for example
in optimization theory, automatic control, models of discrete event networks
and graph theory ([3, 5, 17, 27]).

This paper is organized as follows. In the next section, we deal with the
preliminary concepts and lemmas that come useful later, while we also make an
argument as to why it makes more sense to study the total graph of the
semiring, where the vertex set is limited to the set of all zero-divisors. In
the main section, we determine the metric dimension of a direct product of
antinegative finite commutative semirings, with their set of zero-divisors
closed under addition. Such semirings for example contain the Boolean
semiring, all finite distributive lattices with zero and exactly one atom, all
finite semifields, all polynomial semirings over finite antirings modulo a
monome, etc. It turns out that the metric dimension behaves somewhat
differently in different settings, with the exceptions consting of semifields
and semirings such that all their elements except the identity are zero
divisors. The main results of this paper are Proposition 3.2, Theorem 3.3 and
Theorem 3.6, which together cover all possible cases. It is perhaps
interesting to compare these results with [6, Theorem 3.5 and Theorem 3.7],
where even for the direct product of two finite fields, the metric dimension
of its total graph is not completely determined.

##  2\. Preliminaries

Throughout this paper, we shall suppose that $S$ is a semiring, and that
$Z(S)$ denotes the set of all zero-divisors in $S$, $Z(S)=\\{x\in S;$ there
exists $0\neq y\in S\text{ such that }xy=0\text{ or }yx=0\\}$. We denote by
$\Gamma(S)$ the _total graph_ of $S$. The vertex set $V(\Gamma(S))$ of
$\Gamma(S)$ is the set of all elements in $S$ and an unordered pair of
vertices $x,y\in V(\Gamma(S))$, $x\neq y$, is an edge $x-y$ in $\Gamma(S)$ if
$x+y\in Z(S)$. The sequence of edges $x_{0}-x_{1}$, $x_{1}-x_{2}$, …,
$x_{k-1}-x_{k}$ in $\Gamma$ is called _a path of length $k$_. The _distance_
between vertices $x$ and $y$ is the length of the shortest path between them,
denoted by $d(x,y)$, while the _diameter_ ${\rm diam}(\Gamma)$ of the graph
$\Gamma$ is the longest distance between any two vertices of the graph.

We shall need the following definition.

######  Definition 2.1.

Let $v$ be a vertex of a graph $G$. Then the _open neighbourhood_ of $v$ is
$N(v)=\\{u\in V(G);\text{ there exists an edge }uv\text{ in G}\\}$ and the
_closed neighbourhood_ of $v$ us $N[v]=N(v)\cup\\{v\\}$. Two distinct vertices
$u$ and $v$ of $G$ are _twins_ if $N(u)=N(v)$ or $N[u]=N[v]$.

Twins turn out to be a very important notion when studying the metric
dimension of a graph due to the following lemma.

######  Lemma 2.2 ([14]).

Suppose $u$ and $v$ are twins in a connected graph $G$ and the set $W$ is a
resolving set for $G$. Then $u$ or $v$ is in $W$.

The next lemma shows that in order to study the metric dimension, it makes
sense to limit ourselves to the subgraph with the vertex set equal to the set
of all zero-divisors.

######  Lemma 2.3.

Let $S$ be an antinegative semiring. Then $\Gamma(S)$ is a disconnected graph
(where the set of all non zero-divisors are isolated vertices). The subgraph
$\Gamma_{1}(S)$ with the vertex set equal to $Z(S)$ is connected with ${\rm
diam}(\Gamma_{1}(S))\leq 2$.

###### Proof.

Choose and $s\in S$ such that $s\notin Z(S)$ and suppose that $s-w$ is an edge
in $\Gamma(S)$ for some $w\in S$. This implies that $s+w\in Z(S)$, so there
exists $z\neq 0$ such that $(s+w)z=0$. Since $S$ is antinegative, this yields
$sz=0$, a contradiction. On the other hand, if $s\in Z(S)$, then $0-s$ is an
edge in $\Gamma_{1}(S)$. ∎

Therefore, we shall limit ourselves to studying the subgraph $\Gamma_{1}(S)$
from here onwards. We shall now investigate twins in the graph
$\Gamma_{1}(S)$.

######  Lemma 2.4.

Let $n\geq 1$ and $S=S_{1}\times S_{2}\times\ldots\times S_{n}$, where $S_{i}$
is a finite antinegative commutative semiring with $Z(S_{i})$ closed under
addition for every $i=1,2,\ldots,n$. Choose
$a=(a_{1},a_{2},\ldots,a_{n}),b=(b_{1},b_{2},\ldots,b_{n})\in Z(S)$. Then $a$
and $b$ are twins in $\Gamma_{1}(S)$ if and only if either $a_{i},b_{i}\in
Z(S_{i})$ or $a_{i},b_{i}\notin Z(S_{i})$ for every $i=1,2,\ldots,n$.

###### Proof.

Choose any $1\leq i\leq n$. Notice that the fact that $S_{i}$ is antinegative
implies that $a_{i}+b_{i}\in Z(S_{i})$ yields $a_{i},b_{i}\in Z(S_{i})$: if
there exists $x\in S_{i}$ such that $0=(a_{i}+b_{i})x=a_{i}x+b_{i}x$, we have
$a_{i}x=b_{i}x=0$. Since $Z(S_{i})$ closed under addition for every
$i=1,2,\ldots,n$, we also have that $a_{i},b_{i}\in Z(S_{i})$ implies
$a_{i}+b_{i}\in Z(S_{i})$. So, there is an edge between
$a=(a_{1},a_{2},\ldots,a_{n})$ and $c=(c_{1},c_{2},\ldots,c_{n})$ in
$\Gamma_{1}(S)$ if and only if there exists $1\leq i\leq n$ such that $a_{i}$
and $c_{i}$ are both in $Z(S_{i})$. Thus, the neighbourhood of any vertex is
completely determined by which of its components belong to the set of zero-
divisors. Therefore, two elements $a=(a_{1},a_{2},\ldots,a_{n})$ and
$b=(b_{1},b_{2},\ldots,b_{n})$ in $S$ are twins if and only if either
$a_{i},b_{i}\in Z(S_{i})$ or $a_{i},b_{i}\notin Z(S_{i})$ for every
$i=1,2,\ldots,n$. ∎

##  3\. Metric dimension

In this section, we examine the metric dimension of a total graph of a direct
product of antinegative commutative semirings. Firstly, let us establish the
lower bound for the metric dimension.

######  Lemma 3.1.

Let $n\geq 1$ and $S=S_{1}\times S_{2}\times\ldots\times S_{n}$, where $S_{i}$
is a finite antinegative commutative semiring with $Z(S_{i})$ closed under
addition for every $i=1,2,\ldots,n$. Then
$\dim(\Gamma_{1}(S))\geq|Z(S)|-2^{n}+1$.

###### Proof.

Suppose that $W$ is a resolving set for $\Gamma_{1}(S)$ and choose a subset
$\emptyset\neq X\subseteq\\{1,2,\ldots,n\\}$. Define $M_{X}=M_{1}\times
M_{2}\times\ldots\times M_{n}\subset Z(S)$, where $M_{i}=Z(S_{i})$ if $i\in X$
and $M_{i}=S_{i}\setminus Z(S_{i})$ if $i\notin X$. By Lemma 2.4, all elements
of $M_{x}$ are twins, so by Lemma 2.2, $W$ contains all but perhaps one
element of the set $M_{X}$. Observe that $a=(a_{1},a_{2},\ldots,a_{n})\in S$
is a vertex in $\Gamma_{1}(S)$ if and only if there exists
$i\in\\{1,2,\ldots,n\\}$ such that $a_{i}\in Z(S_{i})$. Therefore, every
vertex in $\Gamma_{1}(S)$ lies in exactly one of the sets $M_{X}$ for a chosen
set $X\neq\emptyset$. So, $W$ contains all elements of $Z(S)$ apart from
perhaps as many as there are nontrivial subsets of the set
$\\{1,2,\ldots,n\\}$. Since there are exactly $2^{n}-1$ such nontrivial
subsets, we have $|W|\geq|Z(S)|-2^{n}+1$. Because this is true for any
resolving set $W$, we have $\dim(\Gamma_{1}(S))\geq|Z(S)|-2^{n}+1$ as stated.
∎

Let us examine the interesting special case of the metric dimension of the
total graph of the direct product of a number of Boolean semirings.

######  Remark.

If $S$ is an antinegative finite commutative semiring with $|S|\geq 3$ and
$|Z(S)|=1$, then $\Gamma_{1}(S)$ is a trivial graph (since it has only one
vertex) - obviously, $\dim(\Gamma_{1}(S))=0$ in this case. We shall therefore
from here onwards always limit ourselves to the case where $\Gamma_{1}(S)$ is
non-trivial.

######  Proposition 3.2.

Let $n\geq 2$ and $S=S_{1}\times S_{2}\times\ldots\times S_{n}$, where
$S_{i}=\mathcal{B}$ for every $i=1,2,\ldots,n$. Then $\dim(\Gamma_{1}(S))=n$
for $n\neq 2$ and $\dim(\Gamma_{1}(S))=n-1$ for $n=2$.

###### Proof.

Assume first that $n\geq 3$. For every $i=1,2,\ldots,n$, let us denote by
$\overline{e_{i}}$ the element with $1$ at every component, except the $i$-th
component, which is equal to $0$. Let
$W=\\{\overline{e_{1}},\overline{e_{2}},\ldots,\overline{e_{n}}\\}$. Now,
choose distinct $x=(x_{1},x_{2},\ldots,x_{n})$ and
$y=(y_{1},y_{2},\ldots,y_{n})$ in $S$. There exists $i\in\\{1,2,\ldots,n\\}$
such that $x_{i}\neq y_{i}$. Without loss of generality, we can assume
$x_{i}=0$ and $y_{i}=1$. Then $x-\overline{e_{i}}$ is an edge in
$\Gamma(S_{1})$ and $y-\overline{e_{i}}$ is not, therefore $x$ and $y$ have
different representations with respect to $W$. Thus, $W$ is a resolving set,
which proves that $\dim(\Gamma_{1}(S))\leq n$. On the other hand, Lemma 2.3
tells us that ${\rm diam}(\Gamma_{1}(S))\leq 2$, so any representation of a
vertex that is not a member of a resolving set, has to be a vector with every
component in $\\{1,2\\}$. Assume that $W$ is a resolving set and denote
$w=|W|$. Since there are at most $2^{w}$ different representations of vertices
that are not in $W$ and there are $2^{n}-1$ vertices in $\Gamma_{1}(S)$, we
have $2^{w}+w\geq 2^{n}-1$. Obviously, $w\mapsto 2^{w}+w$ is an increasing
function, and $2^{n-1}+n-1\geq 2^{n}-1$ implies $n\geq 2^{n-1}$, which further
implies $n\leq 2$. Therefore for $n\geq 3$, we can conclude that $w\geq n$.
So, we have proved that $\dim(\Gamma_{1}(S))\geq n$ for all $n\geq 3$ and thus
$\dim(\Gamma_{1}(S))=n$. Finally, let us examine the case $n=2$. Then
$S=\mathcal{B}\times\mathcal{B}$ and one can easily check that $w=\\{(1,0)\\}$
is a resolving set, so $\dim(\Gamma_{1}(S))=1$. ∎

We can now prove the following theorem.

######  Theorem 3.3.

Let $n\geq 1$ and $S=S_{1}\times S_{2}\times\ldots\times S_{n}$, where $S_{i}$
is a finite antinegative commutative semiring with $Z(S_{i})$ closed under
addition for every $i=1,2,\ldots,n$. Furthermore, assume that for every
$i=1,2,\ldots,n$ the following condition holds: $|Z(S_{i})|\geq 2$ or there
exists $j\neq i$ such that $|S_{j}\setminus Z(S_{j})|\geq 2$. Then
$\dim(\Gamma_{1}(S))=|Z(S)|-2^{n}+1$.

###### Proof.

By Lemma 3.1, we already know that $\dim(\Gamma_{1}(S))\geq|Z(S)|-2^{n}+1$.
Choose any subset $\emptyset\neq X\subseteq\\{1,2,\ldots,n\\}$ and define
$M_{X}=M_{1}\times M_{2}\times\ldots\times M_{n}\subset Z(S)$, where
$M_{i}=Z(S_{i})$ if $i\in X$ and $M_{i}=S_{i}\setminus Z(S_{i})$ if $i\notin
X$. Now, choose $t_{X}\in M_{X}$ and denote
$M^{\prime}_{X}=M_{X}\setminus\\{t_{X}\\}$. If $M^{\prime}_{X}\neq\emptyset$,
choose $s_{X}\in M^{\prime}_{X}$. Define $W=\bigcup_{\emptyset\neq
X\subseteq\\{1,2,\ldots,n\\}}M^{\prime}_{X}$ and let us prove that $W$ is a
resolving set for $\Gamma_{1}(S)$. Choose any distinct elements
$u=(u_{1},u_{2},\ldots,u_{n}),v=(v_{1},v_{2},\ldots,v_{n})\in Z(S)$ such that
$u,v\notin W$. By the construction of $W$ and Lemma 2.4, there exists
$i\in\\{1,2,\ldots,n\\}$ such that $u_{i}\in Z(S_{i})$ and $v_{i}\notin
Z(S_{i})$ or vice versa. Without any loss of generality, we can assume that
$u_{i}\in Z(S_{i})$ and $v_{i}\notin Z(S_{i})$. Define $Y=\\{i\\}$ and observe
$M^{\prime}_{Y}$ is nonempty by our assumption. Therefore, $u-s_{Y}$ is an
edge in $\Gamma(S_{1})$ since $Z(S_{i})$ closed under addition, while
$v-s_{Y}$ is not an edge in $\Gamma(S_{1})$ since $S_{i}$ is an antiring for
every $i=1,2,\ldots,n$. Thus, $u$ and $v$ have different representations with
respect to $W$ and therefore $W$ is a resolving set. We can use the same proof
as in the proof of Lemma 3.1, to see that $|W|=|Z(S)|-2^{n}+1$, which now
implies that $\dim(\Gamma_{1}(S))=|Z(S)|-2^{n}+1$. ∎

Let us illustrate the above with an example.

######  Example 3.4.

Suppose $S=S_{1}\times S_{2}\times\ldots\times S_{n}$, where $n\geq 2$ and
$S_{i}$ is a finite antinegative semifield for every $i=1,2,\ldots,n$. Suppose
that at least two of the semifields $S_{i}$ are not isomorphic to
$\mathcal{B}$. Then all the assumptions of Theorem 3.3 are satisfied, so
$\dim(\Gamma_{1}(S))=|Z(S)|-2^{n}+1=|S_{1}||S_{2}|\ldots|S_{n}|-(|S_{1}|-1)(|S_{2}|-1)\ldots(|S_{n}|-1)-2^{n}+1$.

On the other hand, if $S=S_{1}\times S_{2}\times\ldots\times S_{n}$, where
$S_{i}=\mathcal{B}$ for every $i=1,2,\ldots,n$. Then by Proposition 3.2,
$\dim(\Gamma_{1}(S))=n$ for $n\neq 2$ and $\dim(\Gamma_{1}(S))=n-1$ for $n=2$.

Compare these results with results in [6, Theorem 3.5 and Theorem 3.7], where
even for the direct product of two finite fields, the metric dimension of the
total graph is not known in all cases. Also, it is interesting to compare
these results with results in [21, Theorem 6.1], where similar results have
been obtained, but in a different setting of the zero-divisor graphs of finite
commutative rings, where again the field with two elements is an exception to
the rule.

Let us further investigate the other possible cases that are not covered by
Proposition 3.2 and Theorem 3.3. Before we do that, we need the following
definition.

######  Definition 3.5.

Let $S=S_{1}\times S_{2}\times\ldots\times S_{n}$ a semiring. Then for every
$i=1,2,\ldots,n$, define $W_{i}=\\{0,1\\}\subseteq S_{i}$. Then ${\rm
supp}(S)=W_{1}\times W_{2}\times\ldots\times W_{n}\subseteq S$ is a _support_
of $S$.

######  Theorem 3.6.

  1. (1)

Let $S=B_{1}\times B_{2}\times\ldots\times B_{m}\times Z_{1}\times
Z_{2}\times\ldots\times Z_{n}$, where $m,n\geq 1$, $B_{i}=\mathcal{B}$ for
$i=1,2,\ldots,m$, and $Z_{i}$ is an antinegative finite commutative semiring
with $Z(Z_{i})$ closed under addition, $|Z_{i}|\geq 3$, $|Z_{i}\setminus
Z(Z_{i})|=1$ for every $i=1,2,\ldots,n$. Then
$\dim(\Gamma_{1}(S))=|S|+m-2^{m+n}=|Z(S)|-2^{m+n}+m+1$.

  2. (2)

Let $S=R\times B_{1}\times B_{2}\times\ldots\times B_{m}\times Z_{1}\times
Z_{2}\times\ldots\times Z_{n}$, where $m,n\geq 0$ and $mn\neq 0$, $R$ is an
antinegative finite commutative semiring with $|R|\geq 3$ and $|Z(R)|=1$,
$B_{i}=\mathcal{B}$ for $i=1,2,\ldots,m$, and $Z_{i}$ is an antinegative
finite commutative semiring with $Z(Z_{i})$ closed under addition,
$|Z_{i}|\geq 3$, $|Z_{i}\setminus Z(Z_{i})|=1$ for every $i=1,2,\ldots,n$.
Then $\dim(\Gamma_{1}(S))=|S|-2^{m+n+1}-|R|+3=|Z(S)|-2^{m+n+1}+2$.

###### Proof.

Define $T=\\{v\in Z(S);$ there exists $v\neq u\in Z(S)$ such that $u$ and $v$
are twins in $\Gamma_{1}(S)\\}$, $N=Z(S)\setminus T$ and
$T^{\prime}=T\setminus{\rm supp}(S)$. Now, let us look at both cases
separately.

  1. (1)

Obviously, $N$ contains exactly all elements from $S$ that have no twins. It
follows from Lemma 2.4 that $N$ contains exactly all elements from $Z(S)$ of
the form $(b_{1},b_{2},\ldots,b_{m},1,1,\ldots,1)$ for every $i=1,2,\ldots,m$.
Since $T$ is a complement of $N$ in $Z(S)$, observe that then $T^{\prime}$
contains exactly all elements of the form
$(b_{1},b_{2},\ldots,b_{m},z_{1},z_{2},\ldots,z_{2})$ for all $b_{i}\in B_{i}$
($1\leq i\leq m$) and all $z_{j}\in Z_{j}$ ($1\leq j\leq n$), except for those
that have $z_{j}\in\\{0,1\\}$ for every $j$. Therefore
$|T^{\prime}|=|S|-2^{n+m}$.

By Lemma 2.2, every resolving set $W$ has to contain at least $|T^{\prime}|$
elements (and we can limit ourselves to the case where $W$ contains
$T^{\prime}$ without any loss of generality, since in every $Z_{i}$ any zero-
divisor is interchangeable with $0$ in the sense that it has the same
neighbourhood).

Now, define $X=\\{(b_{1},b_{2},\ldots,b_{m},0,0,\ldots,0);b_{i}\in B_{i}$ for
every $i=1,2,\ldots,m\\}$ and observe that $|X|=2^{m}$. Note that by
definition, $X\cap T^{\prime}=\emptyset$ and also that
$d(x,t)=d(x^{\prime},t)=1$ for every $x,x^{\prime}\in X$ and every $t\in
T^{\prime}$. If we want to have different representations for different
elements from $X$, we therefore have to add some elements of the form
$(b_{1},b_{2},\ldots,b_{m},1,1,\ldots,1)$ to $T^{\prime}$, since only these
kind of elements can be at distance more than one from elements in $X$. We now
reason similarly, as in the proof of Proposition 3.2. Suppose we add $w$
elements to $T^{\prime}$. By Lemma 2.3, this means that we have at most
$2^{w}$ possible different new representations of vertices from $X$. There are
$2^{m}$ vertices in $X$, which implies $2^{w}+w\geq 2^{m}$. Obviously,
$w\mapsto 2^{w}+w$ is an increasing function, and $2^{m-1}+m-1\geq 2^{m}$
implies $m-1\geq 2^{m}$, which is a contradiction, so $w\geq m$. We have
therefore proved that $\dim(\Gamma_{1}(S))\geq|S|+m-2^{n+m}$.

On the other hand, for every $i=1,2,\ldots,n+m$ denote by
$\overline{e_{i}}(x)$ the element of $S$ with $1$ at every component, except
the $i$-th component, which is equal to $x$. Define
$T^{\prime\prime}=\\{\overline{e_{1}}(0),\overline{e_{2}}(0),\ldots,\overline{e_{m}}(0)\\}$
and $W=T^{\prime}\cup T^{\prime\prime}$ for $T^{\prime}$ as above. Observe
that $|W|=|S|+m-2^{n+m}$. Let us prove that $W$ is a resolving set. Choose
$b=(b_{1},b_{2},\ldots,b_{m},z_{1},z_{2},\ldots,z_{n})\neq
b^{\prime}=(b_{1}^{\prime},b_{2}^{\prime},\ldots,b_{m}^{\prime},z_{1}^{\prime},z_{2}^{\prime},\ldots,z_{n}^{\prime})\in
Z(S)\setminus W$ for some $b_{i},b_{i}^{\prime}\in B_{i}$ and some
$z_{j},z,j^{\prime}\in Z_{j}$ for every $1\leq i\leq m,1\leq j\leq n$. Suppose
firstly that there exists $1\leq j\leq n$ such that $z_{j}\neq
z_{j}^{\prime}$. Since $b,b^{\prime}\notin W$, we know that $z_{j}=0$ and
$z_{j}^{\prime}=1$ or vice versa. Without loss of generality, we can assume
the former. Now, choose $x\in Z(S_{j})\setminus\\{0\\}$ and note that
$\overline{e_{j}}(x)\in T^{\prime}$. This now implies that
$d(b,\overline{e_{j}}(x))=1$, while $d(b^{\prime},\overline{e_{j}}(x))>1$.
Suppose now that $z_{j}=z_{j}^{\prime}$ for all $1\leq j\leq n$. Since $b\neq
b^{\prime}$, there exists $1\leq i\leq m$ such that $b_{i}\neq
b_{i}^{\prime}$. Then we have $d(b,\overline{e_{i}}(0))\neq
d(b^{\prime},\overline{e_{i}}(0))$. This implies that $W$ is indeed a
resolving set, so $\dim(\Gamma_{1}(S))\leq|S|+m-2^{n+m}$, which now proves our
assertion. Note also that every element of $S$ except for $(1,1,\ldots,1)$ is
a zero divisor, so $|S|+m-2^{n+m}=|Z(S)|-2^{m+n}+m+1$.

  2. (2)

Since $N$ consists of exactly all those elements from $Z(S)$ that have no
twins, Lemma 2.4 this time shows that $N$ contains exactly all the elements
from $Z(S)$ of the form $(0,b_{1},b_{2},\ldots,b_{m},1,1,\ldots,1)$, where
$b_{i}\in B_{i}$ for every $i=1,2,\ldots,m$. Again, $T$ is the complement of
$N$ in $Z(S)$, so we can reason similarly as above that
$|T^{\prime}|=|S|-2^{m+n+1}-(|R|-2)$, since in this case we have to exclude
from $S$ all the elements of the form
$(r,b_{1},b_{2},\ldots,b_{m},z_{1},z_{2},\ldots,z_{2})$ for all
$r\in\\{0,1\\}$, all $b_{i}\in B_{i}$ and all $z_{j}\in\\{0,1\\}$, as well as
$|R|-2$ elements of the form $(r,1,1,\ldots,1)$ for $r\notin\\{0,1\\}$ since
they are not zero-divisors at all.

Suppose now that $W$ is a resolving set. Using Lemma 2.2, we can reason that
$W$ has to contain at least $|T^{\prime}|$ elements. We can also limit
ourselves to the case where $W$ contains $T^{\prime}$ without any loss of
generality, since in every $Z_{i}$ any zero-divisor is interchangeable with
$0$ and in $R$ every non-zero element is interchangeable with $1$ in the sense
that they have the same neighbourhood.

Let us assume that $W=T^{\prime}$ and choose $b=(1,0,0,\ldots,0)$ and
$b^{\prime}=(0,0,\ldots 0)$ in $S$. Since $m$ and $n$ are not both equal to
zero, $b$ and $b^{\prime}$ are zero-divisors. By the construction of
$T^{\prime}$, we know that $b,b^{\prime}\notin W$. However, for every
$w=(w_{1},w_{2},\ldots,w_{n+m+1})\in W$, we have one of the following two
possible cases.

    1. (a)

We have $w_{1}=0$ and thus (since $w\notin{\rm supp}(S)$) there exists $1\leq
j\leq n$ such that $w_{1+m+j}\notin\\{0,1\\}$. But since all elements of
$S_{1+m+j}$ except $1$ are zero-divisors, we have $w_{1+m+j}\in Z(S_{1+m+j})$,
so in this case $d(b,w)=d(b^{\prime},w)=1$.

    2. (b)

We have $w_{1}\neq 0$. Since $w$ is a zero divisor there exists $2\leq j\leq
n+m+1$ such that $w_{j}$ is a zero-divisor. Again, we have
$d(b,w)=d(b^{\prime},w)=1$.

So, we have proved that $b$ and $b^{\prime}$ have the same representations
with respect to $W$, which is a contradiction with the fact that $W$ is a
resolving set. Therefore $T^{\prime}\subsetneq W$, so
$|W|\geq|T^{\prime}|+1=|S|-2^{m+n+1}-(|R|-2)+1=|S|-2^{m+n+1}-|R|+3$. This
implies that we have $\dim(\Gamma_{1}(S))\geq|S|-2^{n+m+1}-|R|+3$.

Let us now prove that we also have
$\dim(\Gamma_{1}(S))\leq|S|-2^{n+m+1}-|R|+3$. For every $i=1,2,\ldots,n+m+1$
denote by $\overline{e_{i}}(x)$ the element of $S$ with $1$ at every
component, except the $i$-th component, which is equal to $x$. Let us define
$W=T^{\prime}\cup\\{e_{1}(0)\\}$ for the set $T^{\prime}$ defined as above.
Observe that $|W|=|S|-2^{m+n+1}-(|R|-2)+1=|S|-2^{m+n+1}-|R|+3$. Also, Let us
prove that $W$ is a resolving set. Choose
$b=(r_{1},b_{1},b_{2},\ldots,b_{m},z_{1},z_{2},\ldots,z_{n})\neq
b^{\prime}=(r_{1}^{\prime},b_{1}^{\prime},b_{2}^{\prime},\ldots,b_{m}^{\prime},z_{1}^{\prime},z_{2}^{\prime},\ldots,z_{n}^{\prime})\in
Z(S)\setminus W$ for some $r_{1},r_{1}^{\prime}\in R$, some
$b_{i},b_{i}^{\prime}\in B_{i}$ and some $z_{j},z_{j}^{\prime}\in Z_{j}$ for
every $1\leq i\leq m,1\leq j\leq n$. Suppose firstly that there exists $1\leq
j\leq n$ such that $z_{j}\neq z_{j}^{\prime}$. Since $b,b^{\prime}\notin W$,
we know that $z_{j}=0$ and $z_{j}^{\prime}=1$ or vice versa. Without loss of
generality, we can assume the former. Now, choose $x\in
Z_{j}\setminus\\{0,1\\}$ and note that $\overline{e_{j}}(x)\in T^{\prime}$ by
the construction of the set $T^{\prime}$. This now implies that
$d(b,\overline{e_{j}}(x))=1$, while $d(b^{\prime},\overline{e_{j}}(x))>1$.
Suppose now that $z_{j}=z_{j}^{\prime}$ for all $1\leq j\leq n$. Since $b\neq
b^{\prime}$, we have $r_{1}\neq r_{1}^{\prime}$ or there exists $1\leq i\leq
m$ such that $b_{i}\neq b_{i}^{\prime}$. Suppose firstly that $b_{i}\neq
b_{i}^{\prime}$ for some $1\leq i\leq m$. Without any loss of generality, we
can assume that $b_{i}=0$ and $b_{i}^{\prime}=1$. Choose $r\in
R\setminus\\{0\\}$ and define $s=e_{1}(r)e_{i}(0)$. Again, note that $s\in
T^{\prime}$ and that we now have $d(b,s)=1$ and $d(b^{\prime},s)>1$. Finally,
suppose $b_{i}=b_{i}^{\prime}$ and $z_{j}=z_{j}^{\prime}$ for all $1\leq i\leq
m$ and $1\leq j\leq n$. Then we have $r_{1}\neq r_{1}^{\prime}$ and since
$b,b^{\prime}\notin W$ we either have $r_{1}=0$ or $r_{1}^{\prime}=1$ or vice
versa. Again, without loss of generality, assume the former. Observe that
$d(b,e_{1}(0))=1$ and $d(b^{\prime},e_{1}(0))>1$. This implies that $W$ is
indeed a resolving set, so $\dim(\Gamma_{1}(S))\leq|S|-2^{n+m+1}-|R|+3$. Note
also that all elements of $S$ except for elements of the form $(r,1,\ldots,1)$
for some $r\in R\setminus\\{0\\}$ are zero-divisors, so $|S|=|Z(S)|+|R|-1$ and
thus $\dim(\Gamma_{1}(S))=|S|-2^{n+m+1}-|R|+3=|Z(S)|-2^{m+n+1}+2$, which now
proves our assertion.

∎

Observe that Proposition 3.2, Theorem 3.3 and Theorem 3.6 now cover all
possible cases of direct product of antinegative finite commutative semirings
with their sets of zero-divisors closed under addition, so we have completely
determined the metric dimension in this setting.

Statements and Declarations

The author states that there is no conflict of interest.

## References

  * [1] Faisal Ali, Muhammad Salman, and Shuliang Huang, _On the commuting graph of dihedral group_ , Comm. Algebra 44 (2016), no. 6, 2389–2401. MR 3492163
  * [2] David F. Anderson and Ayman Badawi, _The total graph of a commutative ring_ , J. Algebra 320 (2008), no. 7, 2706–2719. MR 2441996
  * [3] François Baccelli and Jean Mairesse, _Ergodic theorems for stochastic operators and discrete event networks_ , Idempotency (Bristol, 1994), Publ. Newton Inst., vol. 11, Cambridge Univ. Press, Cambridge, 1998, pp. 171–208. MR 1608402
  * [4] P. J. Cameron and J. H. van Lint, _Designs, graphs, codes and their links_ , London Mathematical Society Student Texts, vol. 22, Cambridge University Press, Cambridge, 1991. MR 1148891
  * [5] Raymond Cuninghame-Green, _Minimax algebra_ , Lecture Notes in Economics and Mathematical Systems, vol. 166, Springer-Verlag, Berlin-New York, 1979. MR 580321
  * [6] David Dolžan, _The metric dimension of the total graph of a finite commutative ring_ , Canad. Math. Bull. 59 (2016), no. 4, 748–759, [Paging previously given as 1–12]. MR 3563754
  * [7] by same author, _The metric dimension of the annihilating-ideal graph of a finite commutative ring_ , Bull. Aust. Math. Soc. 103 (2021), no. 3, 362–368. MR 4255540
  * [8] by same author, _The Metric Dimension of the Zero-Divisor Graph of a Matrix Semiring_ , Bull. Malays. Math. Sci. Soc. 46 (2023), no. 6, 201. MR 4656836
  * [9] David Dolžan and Polona Oblak, _The total graphs of finite rings_ , Comm. Algebra 43 (2015), no. 7, 2903–2911. MR 3354069
  * [10] by same author, _The total graphs of finite commutative semirings_ , Results Math. 72 (2017), no. 1-2, 193–204. MR 3684424
  * [11] Shahabaddin Ebrahimi Atani and Fatemeh Esmaeili Khalil Saraei, _The total graph of a commutative semiring_ , An. Ştiinţ. Univ. “Ovidius” Constanţa Ser. Mat. 21 (2013), no. 2, 21–33. MR 3096881
  * [12] R. C. Entringer and Larry D. Gassman, _Line-critical point determining and point distinguishing graphs_ , Discrete Math. 10 (1974), 43–55. MR 347680
  * [13] Frank Harary and Robert A. Melter, _On the metric dimension of a graph_ , Ars Combin. 2 (1976), 191–195. MR 457289
  * [14] Carmen Hernando, Mercè Mora, Ignacio M. Pelayo, Carlos Seara, and David R. Wood, _Extremal graph theory for metric dimension and diameter_ , Electron. J. Combin. 17 (2010), no. 1, Research Paper 30, 28. MR 2595490
  * [15] L. John and Harita Vijay, _On the total graph of the semiring of matrices over the Boolean semiring_ , Bull. Kerala Math. Assoc. 13 (2016), no. 2, 199–207. MR 3585523
  * [16] Samir Khuller, Balaji Raghavachari, and Azriel Rosenfeld, _Landmarks in graphs_ , Discrete Appl. Math. 70 (1996), no. 3, 217–229. MR 1410574
  * [17] P. Li, _A heuristic method to compute the approximate postinverses of a fuzzy matrix_ , IEEE Transactions on Fuzzy Systems 22 (2014), 1347–1351.
  * [18] Shikun Ou, Dein Wong, Fenglei Tian, and Qi Zhou, _Fixing number and metric dimension of a zero-divisor graph associated with a ring_ , Linear Multilinear Algebra 69 (2021), no. 10, 1789–1802. MR 4279157
  * [19] S. Pirzada, M. Aijaz, and S. P. Redmond, _Upper dimension and bases of zero-divisor graphs of commutative rings_ , AKCE Int. J. Graphs Comb. 17 (2020), no. 1, 168–173. MR 4145403
  * [20] S. Pirzada and Rameez Raja, _On the metric dimension of a zero-divisor graph_ , Comm. Algebra 45 (2017), no. 4, 1399–1408. MR 3576665
  * [21] Rameez Raja, S. Pirzada, and Shane Redmond, _On locating numbers and codes of zero divisor graphs associated with commutative rings_ , J. Algebra Appl. 15 (2016), no. 1, 1650014, 22. MR 3393943
  * [22] Shane Redmond and Steve Szabo, _When metric and upper dimensions differ in zero divisor graphs of commutative rings_ , Discrete Math. Lett. 5 (2021), 34–40. MR 4227399
  * [23] András Sebő and Eric Tannier, _On metric generators of graphs_ , Math. Oper. Res. 29 (2004), no. 2, 383–393. MR 2065985
  * [24] Peter J. Slater, _Leaves of trees_ , Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congressus Numerantium, No. XIV, Utilitas Math., Winnipeg, Man., 1975, pp. 549–559. MR 0422062
  * [25] by same author, _Fault-tolerant locating-dominating sets_ , vol. 249, 2002, Combinatorics, graph theory and computing (Louisville, KY, 1999), pp. 179–189. MR 1898670
  * [26] David P. Sumner, _Point determination in graphs_ , Discrete Math. 5 (1973), 179–187. MR 316319
  * [27] Shan Zhao and Xue-ping Wang, _Invertible matrices and semilinear spaces over commutative semirings_ , Inform. Sci. 180 (2010), no. 24, 5115–5124. MR 2726681