In this article, we obtain the determining number and the metric dimension of the zero-divisor graph of the ring of integers modulo \(n\) and of non-Boolean semisimple rings. For Boolean rings, an upper bound for these parameters is established. While the determining number and metric dimension of \(\Gamma(\mathbb{Z}_n)\) are known in the literature, we provide an alternative derivation based on a structural decomposition of the graph via generalized join. This approach offers a direct and unified method to compute these parameters. Further, we determine these parameters for joins of vertex-transitive graphs and investigate certain questions concerning the relationship between determining number and metric dimension.
In 1988, the concept of zero-divisor graph of a commutative ring was introduced by Beck [5] and redefined by Anderson and Livingston [2]. They established several important structural properties of the zero-divisor graph of commutative rings. The term zero-divisor graph was first used by Anderson and Livingston. Through the zero-divisor graph, they investigated the interplay between the the structure of rings and the corresponding graphs. Interestingly, one can find two non-isomorphic rings, which have the same zero-divisor graph. Fundamental properties of the zero-divisor graph, such as whether it is finite, complete, bipartite, or a star graph, were studied by Anderson and Livingston [2]. Akbari et al. [1], Belshoff and Chapman [7], and Smith [23] have established several important structural properties of zero-divisor graphs.
In 2006, Boutin [8] introduced the concept of determining number of a graph, and in the same year, an equivalent graph parameter, namely the fixing number of a graph was studied independently by Erwin and Harary [9]. In 1975, Slater [22] introduced the concept of metric dimension of a graph and independently studied by Harary and Melter [12] in 1976. It was Harary and Melter [12], who coined the term “metric dimension” for the same. The metric dimension is also termed the distance-determining number as well as the locating number of a graph. Throughout this article, the definition of zero-divisor graph by Anderson and Livingston [2] is adopted.
The main object of this article is to study the interplay of ring-theoretic properties of commutative rings \(R\) with graph-theoretic properties such as the determining number and the metric dimension of the zero-divisor graph of \(R\). The study of metric dimension in zero-divisor graphs has already been studied by Pirzada et al. [16] and many results have been proved in this direction. Apart from the usual approach, we are looking at the problem of finding metric dimension via its relationship with determining number. For this, we represent the zero-divisor graph of different classes of graphs as a generalized join of certain graphs and utilize the structure to identify the determining number and hence to find the metric dimension. In [16], Pirzada et al. determined the metric dimension of the zero-divisor graph of the ring \(\mathbb{Z}_n\) when \(n=2p\) or \(n=p^k\) for a prime \(p\). In this article, the determining number of the zero-divisor graph of \(\mathbb{Z}_n\) is determined, for all integers \(n\).
We note that the determining number and the metric dimension of the zero-divisor graph \(\Gamma(\mathbb{Z}_n)\) have been previously obtained by Ou et al. [14] and, for the metric dimension, by Basak et al. [4]. The approach adopted in this paper is different and is based on expressing \(\Gamma(\mathbb{Z}_n)\) as a generalized join of graphs, which provides a structural and direct derivation of these parameters. In Section 2, we discuss the same for semisimple commutative rings and obtain certain interesting results regarding the finiteness of determining number of zero-divisor graphs of an infinite ring. In Section 4, we prove some miscellaneous results regarding the determining number of simple graphs, which are not the zero-divisor graph of a commutative ring.
In this article, we consider commutative rings \(R\) with unity \(1\) and use \(\mathcal{Z}(R)\) and \(Ann(R)\) to represent the set of all non-zero zero-divisors of \(R\) and the set of non-zero ideals with non-zero annihilator, respectively. It is noted that in this article, neither the zero-ideal \(\bf{0}\) nor the zero-element \(0\) are included in \(Ann(R)\) and \(\mathcal{Z}(R)\), respectively. A commutative ring \(R\) is Boolean if \(x^2=x\) for any \(x\in R\). A commutative ring is Noetherian if it satisfies the ascending chain condition of ideals. A prime ideal \(\mathfrak{p}\) of \(R\) is an associated prime if \(\mathfrak{p}=ann(x)\) for some \(x\in R\). The set of all associated primes ideals in \(R\) is denoted \(Ass(R)\). In this article, by a ring, we mean a commutative ring unless otherwise mentioned.
For an element \(a\) of a group \(G\), \(\langle a \rangle\) denotes the subgroup generated by \(a\). For any non-empty set \(X\), \(S_X\) denotes the group of all permutations of \(X\), and \(S_n\) denotes the symmetric group on \(n\) symbols. For any finite set \(X\), \(|X|\) denotes the cardinality of \(X\) and \(X^c\) represents the complement of the set \(X\) with respect to the appropriate superset of \(X\). We use \([1,k]\) to denote the set \(\{1,2,\cdots,k\}\). For any real number \(\alpha\), \(\lfloor \alpha\rfloor\) denotes the greatest integer function of \(\alpha\).
We now recall important definitions, notation, and terminology from graph theory. We consider only simple undirected graphs. A graph \(\Gamma\) is an ordered pair \((V(\Gamma), E(\Gamma))\), where the vertex set \(V(\Gamma)\) is non-empty and the edge set \(E(\Gamma)\) is a subset of the set of all two-element subsets of \(V(\Gamma)\). For any vertex \(v\) of a graph \(\Gamma\), \(N_{\Gamma}(v)\) or shortly, \(N(v)\) is the neighborhood of \(v\) in \(\Gamma\), which is the set of all vertices adjacent to \(v\) in \(\Gamma\), and \(\deg_{\Gamma}(v)\) or shortly, \(\deg(v)\) is the degree of \(v\) in \(\Gamma\) and is equal to \(|N_{\Gamma}(v)|\). For any two distinct vertices, \(u\) and \(v\) in \(\Gamma\), the distance between \(u\) and \(v\) is the length of the shortest path connecting \(u\) and \(v\). A complete graph on \(n\) vertices is denoted by \(K_n\), whereas an empty graph on \(n\) vertices is denoted by \(\overline{K}_n\). If \(S\) is a subset of the vertex set of \(\Gamma\), then the subgraph induced by \(S\), denoted by \(\langle S \rangle\), is the subgraph of \(\Gamma\) with vertex set \(S\) and two vertices \(u\) and \(v\) are adjacent in \(\langle S\rangle\) if and only if \(u\) and \(v\) are adjacent in \(\Gamma\). A subset \(S\) of vertices of \(\Gamma\) is a clique of \(\Gamma\) if the subgraph \(\langle S\rangle\) induced by \(S\) is a complete graph and \(S\) is an independent set if the subgraph \(\langle S\rangle\) of \(\Gamma\) induced by \(S\) is an empty graph. An automorphism of a graph \(\Gamma\) is a bijection \(\sigma\) from the vertex set of \(\Gamma\) to itself in such a way that \(u\) is adjacent to \(v\) in \(\Gamma\) if and only if \(\sigma(u)\) is adjacent to \(\sigma(v)\) in \(\Gamma\). For any graph \(\Gamma\), \(Aut(\Gamma)\) stands for the group of all automorphisms of \(\Gamma\). For a graph \(\Gamma\), a non-empty subset \(\mathcal{O}\) of \(V(\Gamma)\) is said to be a vertex orbit of \(\Gamma\) if \(\mathcal{O}=\{\sigma(u): \sigma \in Aut(\Gamma)\}\) for some \(u\) in \(V(\Gamma)\). A graph \(\Gamma\) is vertex-transitive if \(V(\Gamma)\) is the only vertex orbit of \(\Gamma\). The stabilizer of a vertex \(v\) of a graph \(\Gamma\), is \(stab(v)=\{\sigma \in Aut(\Gamma):\sigma(v) =v\}\). The vertex stabilizer of a set of vertices \(S\) of a graph \(\Gamma\) is \(stab(S) =\{\sigma \in Aut(\Gamma):\sigma(v) =v, \forall v \in S\}\). We proceed to define two important parameters, which we discuss in the main results.
Definition 2.1. [8] Let \(\Gamma=(V(\Gamma),E(\Gamma))\) be a graph. A subset \(S \subseteq V(\Gamma)\) is said to be a determining set of \(\Gamma\) if whenever \(\sigma_1, \sigma_2 \in Aut(\Gamma)\) such that \(\sigma_1(u) = \sigma_2(u)\) for all \(u\in S\), then \(\sigma_1(v) = \sigma_2(v)\) for all \(v\in V (\Gamma)\). The determining number of a graph \(\Gamma\) is defined as \[Det(\Gamma)=\min_{S \subset V(\Gamma)}\{|S| : S \text{ is a determining set of } \Gamma\}.\]
For any graph \(\Gamma\), it is obvious that \(V(\Gamma)\) is a determining set of \(\Gamma\). Also any set of vertices \(S\) with \(|S|=|V(\Gamma)|-1\) is a determining set of \(\Gamma\). Therefore \(0\le Det(\Gamma)\le |V(\Gamma)|-1\).
The notion of fixing set and fixing number are analogous to the concept of determining set and determining number.
Definition 2.2. [9] A vertex \(v\) of a graph \(\Gamma\) is said to be fixed by an automorphism \(\sigma \in Aut(\Gamma)\) if \(\sigma \in stab(v)\). A set, \(S\) of vertices of \(\Gamma\) is a fixing set of \(\Gamma\) if \(stab(S)\) is trivial, and we say that \(S\) fixes \(\Gamma\). The fixing number of \(\Gamma\) is \[\text{fix}(\Gamma)=\min_{S \subset V(\Gamma)}\{|S| : S \text{ is a fixing set of } \Gamma\}.\]
Gibbons and Laison [11] proved that the notions of determining set and the fixing set are equivalent.
Lemma 2.3. [11] A set of vertices is a fixing set if and only if it is a determining set.
Also, the metric dimension of a graph and the resolving number of a graph are equivalent notions.
Definition 2.4. [22] Let \(\Gamma=(V(\Gamma),E(\Gamma))\) be a graph and \(W =\{w_1,\ldots, w_k\}\) be an ordered subset of \(V(\Gamma)\). Then for a vertex \(v\) of \(\Gamma\), the metric representation of \(v\) with respect to \(W\) is the \(k\)-vector \(D_W(v) = (\zeta_1, \zeta_2, \ldots,\zeta_k)\), where \(\zeta_i\) is the distance between \(v\) and \(w_i\) in \(\Gamma\).
Definition 2.5. [22] Let \(\Gamma\) be a graph. A set of vertices \(S\) is said to be a resolving set or distance-determining set of \(\Gamma\) if every vertex of \(\Gamma\) is uniquely determined by the metric representation of the vertices with respect to \(S\), that is, \(D_S(u) \ne D_S(v)\) for all \(u, v\in V(\Gamma)\) with \(u\ne v\), where \(S\) is assumed to be ordered. The metric dimension of \(\Gamma\) is the minimum cardinality of a resolving set of \(\Gamma\), denoted by \(dim_M(\Gamma)\).
Lemma 2.6. [8] If \(S \subseteq V(\Gamma)\) is a resolving set of a graph \(\Gamma\), then \(S\) is a determining set of \(\Gamma\). In particular, \(Det(\Gamma) \le dim_M(\Gamma)\).
We first discuss the determining number and the metric dimension of some important graphs. For the complete graph \(K_n\), any set \(S\) with \(|S|=n-1\) is a determining set of \(K_n\), we have \(Det(K_n)=n-1=dim_M(K_n)\). For a path \(P_n\), a single pendant vertex of \(P_n\) forms a determining set of \(P_n\) and therefore \(Det(P_n)=1=dim_M(P_n)\). For a cycle \(C_n\), \(Det(C_n)=2=dim_M(C_n)\), because any pair of two vertices in \(C_n\) form a determining set and a resolving set.
In this article, the following graph operation namely, the generalized join of graphs [20] is often used.
Definition 2.7. [20] Let \(\Gamma\) be a given graph and \(\{\Lambda_{\alpha}\}_{\alpha \in V(\Gamma)}\) be a collection of graphs indexed \(V(\Gamma)\). Then the generalized join of \(\Gamma\) with \(\{\Lambda_{\alpha}\}_{\alpha \in V(\Gamma)}\) is a graph \(\tilde{\Gamma}\) with vertex set \(V(\tilde{\Gamma})=\{(x,y):x\in V(\Gamma) ~\text{and}~ y\in V(\Lambda_x) \}\) and two vertices \((x,y)\) and \((x’,y’)\) are adjacent if and only if either \(x\) is adjacent to \(x’\) in \(E(\Gamma)\) and \(y\) is adjacent to \(y’\) in \(E(\Lambda_x)\) or \(x=x’\) and \(y\) is adjacent to \(y’\) in \(E(\Lambda_x)\). If \(\Gamma\) has \(m\) vertices, then \(\Gamma\)-join of the collection \(\{\Lambda_1,\Lambda_2, \ldots,\Lambda_m\}\) is denoted by \(\Gamma[\Lambda_1,\Lambda_2,\ldots,\Lambda_m]\).
Example 2.8. The graph in Figure 1, illustrates the generalized join, that is, the \(P_3\)-join of \(\{K_4,K_1,K_2\}\).
In this article, we follow the definition of zero-divisor graph of a commutative ring by Anderson and Livingston [2].
Definition 2.9. [2] Let \(R\) be a ring. The zero-divisor graph \(\Gamma(R)\), of \(R\), is a simple graph having the vertex set \(\mathcal{Z}(R)\) and two distinct elements, \(x\) and \(y\) of \(\mathcal{Z}(R)\) are adjacent if and only if \(xy=0\).
The following result emphasizes, under what condition the zero-divisor graph of a ring, is finite.
Lemma 2.10. [10] For any ring \(R\), \(\mathcal{Z}(R)\) is finite if and only if either \(R\) is finite or is an integral domain.
Define an equivalence relation ‘\( \sim\)’ on \(\mathcal{Z}(R)\) in such a way that for any \(x,y \in \mathcal{Z}(R)\), we define \(x\sim y\) if and only if \(ann(x)=ann(y)\). With respect to this equivalence relation ‘\(\sim\)’, if \(R_E\) denotes the set of all equivalence classes \([x]\) in \(\mathcal{Z}(R)\), then \(R_E\) forms a partition of \(\mathcal{Z}(R)\).
Definition 2.11. [24] For a ring, \(R\) the compressed zero-divisor graph of \(\Gamma_E(R)\) of \(R\) is a simple graph with the vertex set \(R_E\) and two distinct vertices \([x]\) and \([y]\) of \(R_E\) are adjacent if and only if \(xy=0\). This equivalence relation forms the basis of the compressed zero-divisor graph.
Another interesting graph structure associated with a ring is the annihilating ideal graph.
Definition 2.12. [6] Let \(R\) be a ring and \(Ann(R)\) be the set of ideals with a non-zero annihilator. The annihilating-ideal graph \(\Gamma_{Ann}(R)\) of \(R\) is the graph with the vertex set \(Ann(R)\), and two distinct vertices \(I\) and \(J\) are adjacent if and only if \(IJ=\langle\bf{0}\rangle\).
There are several structural properties of the zero-divisor graph, the compressed zero-divisor graph, and the annihilating ideal graph, that have been identified by various authors, who have proved many interesting relationship among these graphs [2, 24, 6, 21].
In this article, we analyze certain structural properties of the zero-divisor graph of \(\mathbb{Z}_n\), that helps to predict the determining number and the metric dimension of \(\Gamma(\mathbb{Z}_n)\). For a positive integer \(n>1\), \(\phi(n)\) denotes the Euler totient function of \(n\). We use \(\Upsilon(n)\) to denote the set of all proper divisors of \(n\) and \(\tau(n)\) denotes the number of proper divisors of \(n\). Note that \(1\) and \(n\) are not included as the elements of \(\Upsilon(n)\).
Definition 3.1. Let \(n>1\) be any positive integer and let \(d\) be any divisor of \(n\) such that \(1<d<n\). We define \(\Omega_d\) to be the set of all \(x \in \mathbb{Z}_n\) such that the greatest common divisor of the corresponding integer \(x\) and \(n\) is \(d\).
Remark 3.2. Since \(d \in {\Omega}_d\), \({\Omega}_d\) is always non-empty. Also, for any divisor \(d\) of \(n\), \({\Omega}_d\) is a subset of \(\mathcal{Z}(\mathbb{Z}_n)\) and moreover \({\Omega}_{d_1} \cup { \Omega}_{d_2}\cup \cdots \cup { \Omega}_{d_{\tau{(n)}}}= \mathcal{Z}(\mathbb{Z}_n)\). If \(d\) and \(d’\) are any two distinct divisors of \(n\), then \(\Omega_d\cap\Omega_{d’}=\{\}\). In addition, if \(\mathcal{V}=\{{ \Omega}_d\): \(d\in \Upsilon(n)\}\), then \(\mathcal{V}\) forms a partition of \(\mathcal{Z}(\mathbb{Z}_n)\). For any divisor \(d\) of \(n\), it can be verified that \({\Omega}_d=\{du: u \text{ is a unit in } \mathbb{Z}_n\}\).
From the following lemmas, we can see that, the sets \(\Omega_d\)’s guarantee to explore several structural properties of the zero-divisor graph of \(\mathbb{Z}_n\). First, we prove that the set \(\Omega_d\) is a clique or an independent set in \(\Gamma(\mathbb{Z}_n)\), where \(d\in \Upsilon(n)\).
Lemma 3.3. Suppose \(d\) is a divisor of \(n\).
If \(n\) divides \(d^2\), then \(\Omega_d\) is a clique in \(\Gamma(\mathbb{Z}_n)\) and if \(n\) is not a divisor of \(d^2\), then \(\Omega_d\) is an independent set in \(\Gamma(\mathbb{Z}_n)\).
The number of elements in \(\Omega_d\) is \(\phi(\frac{n}{d})\).
If \(x\in \Omega_d\), then
\[\deg_{\Gamma(\mathbb{Z}_n)}({x})= \begin{cases} d-2 & \text{ if } n\mid d^2,\\ d-1 & \text{ if } n\nmid d^2 .\\ \end{cases}\]
Proof. (i) If \(x,y\in \Omega_d\), then there exist two units \(u, v\in \mathbb{Z}_n\) such that \(x=du\) and \(y=dv\) and hence \(xy=d^2uv\), where \(uv\) is a unit in \(\mathbb{Z}_n\). Thus \(x\) and \(y\) are adjacent in \(\Gamma(\mathbb{Z}_n)\) if and only if \(n|d^2\).
(ii) One can see that \(\Omega_d\) is a collection of all generators of the additive subgroup \(\langle d \rangle\) of \(\mathbb{Z}_n\) and hence \(|\Omega_d|\) is the number of generators of \(\langle d \rangle\). But \(\langle d \rangle\) is isomorphic to \(\mathbb{Z}_{\frac{n}{d}}\) and we have \(|\Omega_d|=\phi(\frac{n}{d})\).
(iii) If \(x\in \Omega_d\), then \(x=du\) for some unit \(u\) in \(\mathbb{Z}_n\). Now if \(y\in \Omega_m\), where \(m\in \Upsilon(n)\) and \(m\) is a multiple of \(\frac{n}{d}\), then \(xy=0\). Suppose that \(xw=0\) for some \(w \in \Omega_k\), where \(k\in \Upsilon(n)\). Then \(dk=0\) and hence \(k\) is a multiple of \(\frac{n}{d}\). If \(n \nmid d^2\), then by Lemma 3.3(ii), we have \[\deg_{\Gamma(\mathbb{Z}_n)}(x)=\sum\limits_{ \substack{\frac{n}{d}|m\\ m\in \Upsilon(n)}}|{\Omega}_m|=\sum\limits_{\substack{\frac{n}{d}|m\\ m\in \Upsilon(n)}}\phi\biggl(\frac{n}{m}\biggr)=\sum\limits_{\substack{i|d\\ i\ne 1}}\phi(i)=d-1.\]
If \(n| d^2\), then \(d\) is a multiple of \(\frac{n}{d}\). Therefore, when the counting is done as above, \(x\) is be included in the \(d-1\) number of adjacent vertices of the vertex \(x\). Since the zero-divisor graph has no loop, \(\deg_{\Gamma(\mathbb{Z}_n)}(x)=d-2\). ◻
We proceed to give an example, which illustrates all the statements of Lemma 3.3.
Example 3.4. Consider the zero-divisor graph \(\Gamma(\mathbb{Z}_{12})\).
The set of all non-zero zero-divisors of \(\mathbb{Z}_{12}\) is \(Z(\mathbb{Z}_{12}) = \{2,3,4,6,8,9,10\}\) and the proper divisors of \(12\) are \(2,3,4,6\), and the corresponding sets are \[\Omega_2 = \{2,10\}, \quad \Omega_3 = \{3,9\}, \quad \Omega_4 = \{4,8\}, \quad \Omega_6 = \{6\}.\]
When the divisor \(d\) is \(2\) or \(3\) or \(4\), \(12\) does not divide \(d^2\) and hence \(\Omega_d\) is an independent set in \(\Gamma(\mathbb{Z}_{12})\). However, \(12\) divides \(36\) and hence \(\Omega_6\) forms a clique in \(\Gamma(\mathbb{Z}_{12})\).
We now verify the degree formula in Lemma 3.3(iii):
If \(x \in \Omega_2\), then \(d=2\) and \(12 \nmid 4\), and hence \(\deg(x) = d-1 = 1\). Indeed, \(2\) is adjacent only to \(6\), and thus \(\deg(2)=1\).
If \(x \in \Omega_3\), then \(d=3\) and \(12 \nmid 9\), and hence \(\deg(x) = d-1 = 2\). Indeed, \(3\) is adjacent to \(4\) and \(8\) and thus \(\deg(3)=2\).
If \(x \in \Omega_4\), then \(d=4\) and \(12 \nmid 16\), and hence \(\deg(x) = d-1 = 3\). Indeed, \(4\) is adjacent to \(3,6,\) and \(9\), and thus \(\deg(4)=3\).
If \(x \in \Omega_6\), then \(d=6\) and \(12 \mid 36\), hence \(\deg(x) = d-2 = 4\). Indeed, \(6\) is adjacent to \(2,4,8,\) and \(10\), and thus \(\deg(6)=4\).
Note that, if \(n\) is not a divisor of \(d^2\), then \(\Omega_d\) is an independent set of the zero-divisor graph of the ring \(\mathbb{Z}_n\).
Lemma 3.5. Let \(x\) and \(y\) be any two vertices in the zero-divisor graph of the ring \(R=\mathbb{Z}_n\). Then the degrees of \(x\) and \(y\) in \(\Gamma(R)\) are equal if and only if there exists \(d\in \Upsilon(n)\) such that \(x, y \in \Omega_d\).
Proof. Let \(x,y \in \Omega_d\). Then \(x=du\) and \(y=dv\), for some units \(u\) and \(v\) in \(R\). Therefore, for any \(w\in \mathcal{Z}(R)\), \(xw=0\) if and only if \(dw=0\) if and only if \(yw=0\). Therefore, \(ann(x)=ann(y)\). By Lemma 3.3\((i)\), if \(n|d^2\), then \(\deg_{\Gamma(R)}(x)=|ann(x)\setminus\{0,x,y\}|=|ann(y)\setminus\{0,x,y\}|=\deg_{\Gamma(R)}(y)\) and if \(n\nmid d^2\), then \(\deg_{\Gamma(R)}(x)=|ann(x)|-2=|ann(y)|-2 =\deg_{\Gamma(R)}(y)\). Conversely, if \(\deg_{\Gamma(R)}(x)=\deg_{\Gamma(R)}(y)\) for \(x\in \Omega_{d_1}\) and \(y\in \Omega_{d_2}\), then by Lemma 3.3\((iii)\), either \(d_1-1=d_2-1\) or \(d_1-1=d_2-2\) and hence \(d_1=d_2\) or \(d_2=d_1+1\); but if \(d_2=d_1+1\), then \(n|(d_1+1)^2\). On the other hand, we have \(d_1|n,(d_1+1)|n\) and \(\gcd(d_1,d_1+1)=1\) and hence \(d_1(d_1+1)|n\). Consequently, \(d_1|d_1+1\), which is a contradiction. Therefore, \(d_1=d_2\). ◻
An outline of the above argument also appears in [2]. Since \(ann(x)=ann(y)\) if and only if \(x,y\in \Omega_d\) for some \(d\in \Upsilon(n)\), the set \(\mathcal{V}=\{\Omega_d: d\in \Upsilon(n)\}\) is precisely the vertex set of \(\Gamma_E(\mathbb{Z}_n)\).
Lemma 3.6. For the ring \(R=\mathbb{Z}_n\), \(\Gamma_E(R)\cong\Gamma_{Ann}(R)\).
Proof. The proof follows from any isomorphism from \(\mathcal{V}\) to \(Ann(\mathbb{Z}_n)\) that maps each \(\Omega_d\) to \(\langle d\rangle\). ◻
The structure of the zero-divisor graph of \(\mathbb{Z}_n\) can be expressed as a generalized join of elementary classes of graphs such as complete graphs and empty graphs. Note that all the non-trivial ideals of \(\mathbb{Z}_n\) are principal and that \(\langle x \rangle \langle y \rangle = \langle xy \rangle\), where \(x,y \in \mathbb{Z}_n\). The following lemma formalizes this.
Lemma 3.7. Let \(R=\mathbb{Z}_n\). If \(Ann(R)=\{ \langle d_1\rangle,\langle d_2\rangle,\cdots,\langle d_{\tau(n)}\rangle\}\), where \(d_i\)’s are divisors of \(n\), then \(\Gamma(R)\) is isomorphic to \(\Gamma_{Ann}(R)\big[\Lambda_{d_1},\Lambda_{d_2}\cdots,\Lambda_{d_{\tau(n)}}\big]\), where \(\Lambda_{d_i}= K_{\phi(\frac{n}{d_i})}\) if \(n|d_i^2\) and \(\Lambda_{d_i}=\overline{K}_{\phi(\frac{n}{d_i})}\) if \(n \nmid d_i^2\).
Proof. If the vertex set of \(\Lambda_{d_i}\) is \(\{y_i^j: j\in[1,\phi(\frac{n}{d_i})]\}\), then define the vertex set of \(\Gamma_{Ann}(R)\big[\Lambda_{d_1},\cdots ,\Lambda_{d_{\tau(n)}}\big]\) to be \[U=\bigcup_{i=1}^{\tau(n)} \{(\langle d_i \rangle,y_i^j): y_i^j\in \Lambda_{d_i}, i\in [1,\tau(n)]\}.\]
Consider a mapping \(\psi:V(\Gamma(R))\longrightarrow U\) in such a way that, if \(x_j\) is the \(j\)-th vertex in \(\Omega_{d_i}\) with respect to some order and if \(j \in [1,\phi(\frac{n}{d_i})]\), then define \(\psi(x_j)=(\langle d_i \rangle,y_i^j)\). We claim that \(\psi\) is a graph isomorphism. Suppose \(x\) and \(y\) are adjacent in \(\Gamma(R)\). If both \(x\) and \(y\) are in \(\Omega_{d_j}\), for some \(j\), then \(d_i^2|n\) and \(\Lambda_{d_i} \cong K_{\phi(\frac{n}{d_i})}\) and hence by definition of generalized join, \(\psi(x)\) will be adjacent to \(\psi(y)\). If \(x\in \Omega_{d_i}\) and \(y\in \Omega_{d_j}\), where \(i\ne j\), then \(n\) divides \(d_id_j\). Hence \(\langle d_i \rangle\) and \(\langle d_j \rangle\) are adjacent in \(\Gamma_{Ann}(R)\) and again by definition of generalized join of graphs, \(\psi(x)\) is adjacent to \(\psi(y)\). This completes the proof. ◻
Note that the above lemmas were proved in [19] with a different approach.
Lemma 3.8. [2] If \(R=\mathbb{Z}_n\), then \[Aut(\Gamma(R))=\prod_{d\in \Upsilon(n)} S_{\Omega_d}\cong \prod_{d\in \Upsilon(n)} S_{\phi(\frac{n}{d})}.\]
Lemma 3.9. [8] Let \(\mathcal{O}_1,\mathcal{O}_2,\cdots,\mathcal{O}_k\) be the vertex orbits of a graph \(\Gamma\) and \(\Lambda_1,\Lambda_2,\cdots,\\ \Lambda_k\) respectively be their associatedinduced subgraphs in \(\Gamma\). If \(S_1,S_2, \cdots, S_k\) are the respective determining sets of \(\Lambda_1,\Lambda_2,\cdots, \Lambda_k\), then \(\bigcup_{i=1}^k S_i\) is a determining set of the graph \(\Gamma\).
The determining number and the metric dimension of the zero–divisor graph of \(\mathbb{Z}_n\) are obtained.
Theorem 3.10. For the ring \(R=\mathbb{Z}_n\), \(Det(\Gamma(R))=n-\phi(n)-\tau(n)-1\).
Proof. The case \(n = 4\) is immediate, since \(\Gamma(\mathbb{Z}_4)\) is a single vertex graph and hence \(\mathrm{Det}(\Gamma(R)) = 0\), which agrees with the formula. For \(n\ne 4\), let \(\Upsilon(n)=\{d_1,d_2,\cdots,d_{\tau(n)}\}\). Suppose \(\Lambda_i\) is the subgraph of \(\Gamma(R)\) induced by \(\Omega_{d_i}\) and \(S_i\) is a minimum determining set of \(\Lambda_i\), that is, \(Det(\Lambda_i)=|S_i|\). By Lemma 3.3, each \(\Lambda_i\) is either a complete graph or an empty graph. In both cases, \(S_i\) contains all the elements of \(\Omega_{d_i}\), except for exactly one vertex of it. Hence \(|S_i|=|\Omega_{d_i}|-1\).
Suppose that \(S = \bigcup_{i=1}^{\tau(n)} S_i\). We first prove \(S\) is a determining set of \(\Gamma(R)\). Using Lemma 3.8, each \(\Omega_{d_i}\) is a vertex orbit of \(\Gamma(R)\). Again, by Lemma 3.9, the union \(S\) of determining sets from each orbit is a determining set of \(\Gamma(R)\). To prove minimality, let \(S’\) be a set of vertices of \(\Gamma(R)\) with \(|S’| <|S|\). Then there exists a \(d_j\in \Upsilon(n)\) such that \(S’\) omits at least two vertices \(x\) and \(y\) of \(\Omega_{d_j}\). Now, by Lemma 3.8, there exists a non-trivial automorphism of \(\Gamma(R)\), which fixes all the vertices of \(S’\) other than \(x\) and \(y\), and interchanges \(x\) and \(y\). Thus \(S’\) is not a fixing set of \(\Gamma(R)\) and hence by Lemma 2.3, \(S’\) is not a determining set of \(\Gamma(R)\). Hence the number of elements in \(S\) is \(|\mathcal{Z}(R)|-|\Upsilon(n)|=n-\phi(n)-\tau(n)-1\). ◻
Theorem 3.11. For the ring \(R=\mathbb{Z}_n\), \(dim_M(\Gamma(R))=n-\phi(n)-\tau(n)-1\).
Proof. Let \(n=p^2\), where \(p\) is a prime. Then by Lemma 3.7, \(\Gamma(R)\) is a complete graph on \(p-1\) vertices and hence \(dim_M(\Gamma(R))=p^2-(p^2-p)-1-1=p-2\).
Suppose that \(n\ne p^2\), for any prime \(p\). By Proposition 2.6, \(dim_M(\Gamma(R))\ge n-\phi(n)-\tau(n)-1.\) For the reverse inequality, it is enough to prove that the determining set \(S\) defined in the proof of Theorem 1, is a resolving set. We claim that \(D_S(x)\ne D_S(y)\), whenever \(x\) and \(y\) are any two vertices of \(\Gamma(R)\) that are not in \(S\). By the definition of \(S\), we can find \(i\ne j\) such that \(x \in \Omega_{d_i}\) and \(y\in \Omega_{d_j}\). Then \(\deg_{\Gamma(R)}(x) \ne \deg_{\Gamma(R)}(y)\). Without loss of generality, we assume that \(\deg_{\Gamma(R)}(x) >\deg_{\Gamma(R}(y)\), then there exist a vertex \(w\in \mathcal{Z}(R)\), \(x \ne w\), and \(y\ne w\) such that \(wx=0\) and \(wy\ne 0\). Let \(\Omega_d\) be the partite set containing \(w\).
If \(|\Omega_d| \ne 1\), then there exists \(w’\in S\cap \Omega_d\) such that \(d(x,w’)=1\) and \(d(y,w’)\ne 1\) and hence \(D_S(x)\ne D_S(y)\).
Now, if \(|\Omega_d|=1\), then by Lemma 3.3(ii), \(d=\frac{n}{2}\). Hence \(n\) must be even in this case and thus \(2\) divides \(n\) and \(|\Omega_2|>1\). Therefore it is possible to choose \(w’\in S\cap \Omega_2\) such that \(d(x,w’)=2\) and \(d(y,w’)>2\). Thus \(D_S(x)\ne D_S(y)\) and consequently, \(S\) is a resolving set of \(\Gamma(R)\). ◻
Remark 3.12. After completing this work, we became aware that the determining number and the metric dimension of the zero-divisor graph \(\Gamma(\mathbb{Z}_n)\) were obtained by Ou et al. [14]. Further, we note that Theorem \(2\) was established earlier by Basak, Saha, and Tiwary \((2019)\) [4] by using a different method. The proofs of the results in Theorems \(1\) and \(2\) were obtained independently in this work. Although these results are not new, the approach adopted here is entirely different and is based on expressing \(\Gamma(\mathbb{Z}_n)\) as a generalized join of graphs, which leads to a direct derivation of these parameters. This viewpoint may be useful in extending such results to broader classes of graphs arising from algebraic structures.
The structural description of \(\Gamma(\mathbb{Z}_n)\) as a generalized join plays a key role in the above derivations and offers a unified framework for analyzing related graph parameters.
The apparent difference in the formula \(a+1\) in [14] and a \(-1\) in our expression is due to a difference in convention. In this paper, trivial divisors are excluded from the divisor set, whereas they are included in [14]. With consistent conventions, the expressions agree.
Now, the zero-divisor graph of \(\mathbb{Z}_{315}\) is given in Figure 3. This graph has the determining number 160 as well as the metric dimension 160. Note that the grey color connecting \(\overline{K}_i\) and \(\overline{K}_j\) represents every vertex of \(\overline{K}_i\) is adjacent to every vertex of \(\overline{K}_j\).
In this section, the determining number and the metric dimension of the zero-divisor graph of semisimple rings are discussed. We use the following notations and results for the same.
Definition 4.1. [3] Let\(R\) be a finite ring, Then \(R\) is said to be semisimple if \(R\) is a direct product of a finite number of finite fields.
Therefore, whenever \(R\) is semisimple ring, then \(R\cong \prod_{i=1}^k F_i\), where all \(F_i\)’s are finite field and \(k>1\).
Definition 4.2. [15] Let \(R\cong \prod_{i=1}^k F_i\). For any zero-divisor \(x=(x_1, \cdots,x_k)\) of \(R\), we define a non-empty subset \(\Theta_x\) of \([1,k]\) such that \(x_i=0\), whenever \(i \in \Theta_x\). Equivalently, \(\Theta_x\) is the complement of the support of \(x\).
For any ideal \(\mathcal{I}=\prod_{i=1}^kI_i\) of \(R\), we define a non-empty subset \(\Theta_{\mathcal{I}}\) of \([1,k]\) such that \(I_i= \bf{0}\), whenever \(i\in \Theta_{\mathcal{I}}\). Also, we define a subset \(\mathcal{I}’= \{x\in \mathcal{I}: \Theta_x=\Theta_{\mathcal{I}}\}\) of \(\mathcal{I}\).
Lemma 4.3. [15] Let \(R\cong \prod_{i=1}^k F_i\) be a finite semisimple ring with \(Ann(R)=\{\mathcal{I}_1,\mathcal{I}_2,\cdots,\\ \mathcal{I}_m\}\), where \(m=2^{k}-2\) and \(k>1\). For all \(i\in[1,m]\), if \(\Lambda_i\) is a totally disconnected graph on \(|\mathcal{I}’_i|\) vertices, then \(\Gamma(R)\) is isomorphic to \(\Gamma_{Ann}(R)\bigl[\Lambda_1,\Lambda_2,\cdots,\Lambda_m \bigr]\).
Lemma 4.4. Let \(\Gamma\cong \Lambda[\Lambda_1,\cdots \Lambda_k]\), where \(\Lambda\) and \(\Lambda_i\)’s are any graphs. Then \(Aut(\Lambda_i)\times\cdots \times Aut(\Lambda_k)\) can be embedded in \(Aut(\Gamma)\).
Proof. Suppose that the vertex set of \(\Lambda\) is \([1, k]\) and the vertex set of \(\Gamma\) is \(\{(x_i,y_i^j):y_i^j\in V(\Lambda_i)\}\). Consider \(\psi:Aut(\Lambda_1)\times\cdots \times Aut(\Lambda_k) \longrightarrow Aut(\Gamma)\) such that \(\psi(\sigma_1,\cdots,\sigma_k)(i,y_i^j)=\sigma_i(y_i^j)\). Now if \(\psi(\sigma \circ \rho)=\psi(\sigma_1\circ \rho_1,\cdots ,\sigma_k\circ \rho_k)=\mu\), then \(\mu(i,y_i^j)=\sigma_i(\rho_i(y_i^j))\). Therefore \(\psi(\sigma \circ \rho )=\psi(\sigma)\circ\psi(\rho)\). Hence \(\psi\) is a homomorphism. Since each automorphism \(\sigma_i\)’s is one-one, we have \(ker(\psi)=ker(\sigma_1)\times\cdots \times ker(\sigma_k)=\{e\}\). Hence \(\psi\) is an embedding. ◻
Lemma 4.5. [15] Let \(R\cong \prod_{i=1}^k F_i\) be a semisimple ring, Then \(\Gamma_E(R)\cong \Gamma_{Ann}(R)\).
Theorem 4.6. Suppose \(R\cong \prod_{i=1}^{k} F_i\), where \(F_i\) is a finite field and \(F_i \ncong \mathbb{Z}_2\) for some \(i\). Then \(Det(\Gamma(R))=|\mathcal{Z}(R)|-2^k+2\).
Proof. From Lemma 4.3, \(\Gamma(R)\) is the generalized join of a collection of complete graphs. Let \(S\) be a subset of the vertex set of \(\Gamma(R)\) such that \(S\) contains all but one vertex from each of the partite set \(\mathcal{I}’\). Since there are \(2^k-2\) different partite sets, we have \(|S|=|\mathcal{Z}(R)|-2^k+2\). We claim that \(S\) is a minimum determining set of \(\Gamma(R)\). We show that any automorphism fixing \(S\) must be the identity. Suppose \(\psi\) is an automorphism of \(\Gamma(R)\) that fixes all the vertices of \(S\) and let \(x \in S^c\) be such that \(\psi(x) =y\) for some \(y\ne x\). Also, assume that \(x\) is in \(\mathcal{I}’\) of the partition.
Now, suppose \(|\mathcal{I}’|\)=1. Since there is at least one \(j\) such that \(F_j\not \cong \mathbb{Z}_2\), there exists \(w\in S\) such that \(w\) is adjacent to \(x\) and \(w\) is not adjacent to \(y\). Therefore \(\psi(x)\) is not adjacent to \(w=\psi(w)\). Hence \(\psi\) is not an automorphism of \(\Gamma(R)\), which is a contradiction. Thus \(\psi\) fixes all the vertices of \(\Gamma(R)\) and \(S\) is a determining set of \(\Gamma(R)\).
Similarly, if \(|\mathcal{I}’|>1\), by the procedure that \(S\) is defined we must have \(y\not \in \mathcal{I}’\). Then there exists a vertex \(w\) either in \(S\) or in \(\mathcal{I}’\) of the partition with \(|\mathcal{I}’|=1\) such that \(w\) is adjacent to \(x\), but not to \(y\) in \(\Gamma(R)\). From above, every vertex in \(S\) and in \(\mathcal{I}’\) of the partition with \(|\mathcal{I}’|=1\) are fixed by \(\psi\), therefore \(\psi(w)=w\) and hence \(\psi\) is not an automorphism. Considering both the cases together, \(\psi(x)=x\) for all \(x\in V(\Gamma(R))\). Therefore, \(S\) is a determining set of \(\Gamma(R)\).
To prove minimality, suppose \(S_1\) is any subset of the vertex set of \(\Gamma(R)\) such that \(|S_1|<|\mathcal{Z}(R)|-2^k+2\), then there exist \(x,y\in S_1^c\) such that, \(x,y \in \mathcal{J}’\) for some ideal \(\mathcal{J}\) of \(R\). Then, by Theorem 4.4, there exists an automorphism of \(\Gamma(R)\), which fixes all vertices in \(S’\); but maps \(x\) and \(y\) each other. Hence \(S_1\) is not a determining set of \(\Gamma(R)\). ◻
The next two results give the determining number of the semisimple ring \(R\cong \prod_{i=1}^k F_i\), where each \(F_i\) is a finite field. The result appeared in [14]; however our approaches are different.
Theorem 4.7. Suppose \(R\cong \prod_{i=1}^{k} F_i\), where \(F_i\) is a finite field and \(F_i \ncong \mathbb{Z}_2\) for some \(i\). Then \(dim_M (\Gamma(R))=|\mathcal{Z}(R)|-2^k+2\).
Proof. Let \(S\) be the same as in the proof of Theorem 4.6; Since \(R\) is not a Boolean ring, \(S\) is non-empty. It is enough to prove that, above determining set \(S\) is a resolving set as well. Suppose, \(x,y\) are distinct vertices from \(S^c\), using the definition of \(S\) we have \(\Theta_x\ne \Theta_y\). Then it is possible to find a vertex \(w\) in \(S\), which is adjacent to either \(x\) or \(y\) but not both. For, if \(\Theta_x\cap \Theta_y=\emptyset\) , choose \(w\) such that, \(\Theta_x^c\subseteq \Theta_w\) and if \(\Theta_x\cap \Theta_y\ne \emptyset\), choose \(w\) such that, \((\Theta_x\setminus\Theta_y)^c \subseteq \Theta_w\). Hence, the set \(S\) is a resolving set as well, and \(dim_M(R)=|\mathcal{Z}(R)|-2^k+2\). ◻
Theorem 4.8. If \(R=\mathbb{Z}_2^n\), then \(Det(\Gamma(R))< \frac{n}{2}+1\), where \(n>1\).
Proof. First we consider the cases, when \(n=2,3\) and \(4\) separately. If \(n=2\), then \(\Gamma(R)\cong K_2\) and hence \(Det(\Gamma(R)=1\).
For \(n=3\), we have \(\Gamma(R)\cong K_3\odot K_2\), which is given in Figure 4. Clearly, \(\{u_1,u_2\}\) is a minimum determining set of \(\Gamma(R)\) and hence the determining number of \(\Gamma(R)\) is 2. If \(n=4\), then \(\{v_6,v_{10}\}\) is a minimum determining set of \(\Gamma(R)\) and thus the determining number of \(\Gamma(R)\) is \(2\). If \(n\ge 5\), then consider the set \(U=\{v\in R : |\Theta_v|=1\}\). Since every vertex of \(\Gamma(R)\) is adjacent to at least one of the vertex in \(U\), \(U\) itself is a determining set of \(\Gamma(R)\). In addition, \(U\) is precisely the set of the central vertices of \(\Gamma(R)\).
For the rest of the proof, we consider two cases (i) \(n=2t, t\geq 3\) and (ii) \(n=2s+1, s\geq 2\). Consider the portion of the graph \(\Gamma(\mathbb{Z}_2^{2t})\), which is given in Figure 5. Let \(U=\{v_1,v_2,\cdots, v_{2t}\}\) be the set of central vertices of \(\Gamma(\mathbb{Z}_2^{2t})\). Then, choose the vertices \(u_1,u_2,\cdots, u_{t}\) such that for each \(i\in[1,t]\), the vertex \(u_i\) is adjacent to exactly three of the central vertices \(v_{2i-1},v_{2i}\) and \(v_{2i+1}\) as given in Figure 3. Note that it is considered \(v_{2k+1}\) is the same as that of \(v_1\). Let \(S=\{u_1,u_2,\cdots u_t\}\) be set of the vertices of \(\Gamma(\mathbb{Z}_2^{2k} )\), as shown in Figure 5. Suppose an automorphism of \(\Gamma(\mathbb{Z}_2^{2k})\) fixes all of the vertices of \(S\), then it forces all the central vertices to be fixed. Hence \(S\) constitutes a determining set of \(\Gamma(\mathbb{Z}_2^{2k})\).
Similarly, for the case \(n=2k+1\), Figure 5 illustrates a portion of \(\Gamma(\mathbb{Z}_2^{2k+1})\). Choose a set of vertices \(S=\{u_1,u_2,\cdots ,u_k\}\) of \(\Gamma(R)\) as shown in Figure 4, with the property that \(u_i\) is adjacent to exactly three of the central vertices, namely \(v_{2i-1},v_{2i}\) and \(v_{2i+1}\) for \(i=1,2,\cdots,k\). Then fixing all the vertices of \(S\) forces to fix all the central vertices and hence fixes all the vertices of \(\Gamma(\mathbb{Z}_2^{2k+1})\). By combining the above cases, we have \(Det(\Gamma(\mathbb{Z}_2^n))=\lfloor \frac{n}{2} \rfloor< \frac{n}{2}+1\), where \(n>1\). ◻
One can conclude that if \(R\) is either \(\mathbb{Z}_n\) or any non-Boolean reduced ring, then the determining number and metric dimension of \(\Gamma(R)\) are same. A natural question is whether there exists a ring \(R\) for which the determining number and the metric dimension of \(\Gamma(R)\) are not same. The question is answered in the affirmative.
For the ring \(R=\mathbb{Z}_2^5\), the determining number of \(\Gamma(R)\) is less than or equal to \(2\). However Raja et al. [18] proved that the metric dimension of \(\Gamma(R)\) is \(5\). Hence, \(Det(\Gamma(R))\ne dim_M(\Gamma(R))\). The following problem remains open and presents several interesting avenues for future research
Problem 4.9. Characterize all rings \(R\) for which \(\operatorname{Det}(\Gamma(R)) \ne \dim_M(\Gamma(R))\).
In this section, a comparison of the finiteness of the determining number of the zero-divisor graph, with respect to the size of the ring, is analyzed. In 2014, Pirzada et al. [17] proved that the metric dimension of the zero-divisor graph of an arbitrary commutative ring is finite if and only if the ring itself is finite. In the case of determining number, a detailed investigation is required.
Problem 5.1. Does there exist an infinite ring \(R\), which is not an integral domain, such that \(\operatorname{Det}(\Gamma(R)) < \infty\)?
To the best of our knowledge, this problem remains open.
In 2011, Spiroff and Wickam [24] associated the vertices of a compressed zero-divisor graph and associated prime ideals of a Noetherian ring. In [24], there is a natural injective map from \(Ass(R)\) to the vertex set of \(\Gamma_E(R)\) which maps each annihilator of an element \(x\) to the equivalence class \([x]\), where \([x]\) is the set of \(y\) in \(R\) such that \(ann(x)=ann(y)\). The following theorem guarantees the size of the determining number of certain zero-divisor graphs, is not finite.
Theorem 5.2. Let \(R\) be any infinite ring, which is not an integral domain. If \(\Gamma_E(R)\) is a finite, then \(Det(\Gamma(R))\) is not finite.
Proof. If \(R\) is an infinite ring and not an integral domain, then by Lemma 2.10, \(\mathcal{Z}(R)\) is also an infinite set. If \(V(\Gamma_E(R))\) is a finite graph, then at least one of the equivalence class \([x]\) contains an infinite number of zero-divisors. Note that for any two distinct vertices \(u\) and \(v\) in \([x]\), \(N(u)\setminus\{v\}=N(v)\setminus\{u\}\) in \(\Gamma(R)\). Therefore, any determining set of \(\Gamma_E(R)\) includes all but one vertex from \([x]\). Thus, all but a finite number of vertices of \(V(\Gamma(R))\) are included in any of the determining sets of \(\Gamma(R)\). Hence, \(Det(\Gamma(R))\) is not a finite number. ◻
The converse of the above theorem need not be true. The determining number of the zero-divisor graph of an infinite ring \(R\) need not be finite, even if \(\Gamma_E(R)\) is not a finite graph. For example, consider \(R=\mathbb{Z}_2[x,y,z]/(x^2,y^2)\) is an infinite ring and \(\Gamma_E(R)\) is infinite, but \(Det(\Gamma(R))\) is not finite.
Theorem 5.3. [13] Let \(R\) be a Noetherian ring and suppose all the equivalence classes \([x]\) with respect to the relation \(\sim\) has finite cardinality. Then \(R\) is a finite ring.
The following theorem settles the above problem, when the ring is Noetherian and the problem is still open for a non-Notherian ring.
Theorem 5.4. Let \(R\) be Noetherian. Then \(Det(\Gamma(R))\) is finite if and only if \(R\) is finite.
Proof. By Theorem 5.3, if \(R\) is infinite, then at least one of the equivalence class \([x]\) has infinite elements. Therefore, any determining set of \(\Gamma(R)\) contains all but one vertex of that class \([x]\) and thus \(Det(\Gamma(R))\) is not finite. ◻
The determining number of a graph is closely related to parameters that measure the ability to distinguish vertices, such as the metric dimension, strong metric dimension, and upper dimension. While the metric dimension is defined via resolving sets that distinguish vertices by distances, the determining number is concerned with breaking graph automorphisms. In general, these parameters capture different structural aspects of a graph: metric-type parameters depend on distance structure, whereas the determining number reflects symmetry properties.
For zero-divisor graphs of rings, these parameters may exhibit significantly different behaviour, as illustrated in this paper. Understanding the relationship between the determining number and other variants of metric dimension, such as strong metric dimension and upper dimension, remains an interesting direction for further study.
In this section, we discuss certain interesting results in connection with determining number and metric dimension of general graphs. When we write \(\Gamma\) is isomorphic to \(\Lambda \bigl[\Lambda_{1},\Lambda_{2},\cdots ,\Lambda_{k} \bigr]\), we mean \(\Lambda\) is a finite graph with the vertices \(1,2,\cdots, k\) and \(\Lambda_{1},\Lambda_{2},\cdots, \Lambda_{k}\) are finite graphs. Also, if \(S\) is any subset of \(V(\Lambda_i)\), then we use \(S^{\dagger}\) to denote the corresponding subset \(\{(i,v):v\in S\}\) of \(V(\Gamma)\). We also note that the number of elements in \(S\) and \(S^{\dagger}\) are the same.
Theorem 6.1. Let \(\Gamma \cong \Lambda \bigl[\Lambda_{1},\Lambda_{2},\cdots , \Lambda_{k} \bigr]\), where \(\Lambda\) is any graph with the vertices \(1,2,\cdots, k\) and each \(\Lambda_i\) is either a complete graph or an empty graph and \(\deg_{\Gamma}((i,u))\ne \deg_{\Gamma}((j,v))\) whenever \(i\ne j\). Then \(Det(\Gamma)=|V(\Lambda_{1})^\dagger|+|V(\Lambda_{2})^\dagger|+\cdots+|V(\Lambda_{k})^\dagger|-k\).
Proof. As per the notation defined above, we have \(V(\Gamma)=\cup_{i=1}^kV(\Lambda_i)^\dagger\). Clearly by the hypothesis, \(\{V(\Lambda_i)^\dagger\}_{i=1}^k\) are the vertex orbits of \(\Gamma\). Let \(S\) be a subset of \(V(\Gamma)\) such that for each \(i\), the cardinality of the set \(S\cap V(\Lambda_i)^{\dagger}\) is equal to one less than the cardinality of the set \(V(\Lambda_i)\) that is, \(|S\cap V(\Lambda_i)^{\dagger}|=|V(\Lambda_i)|-1\). Since \(|S\cap V(\Lambda_i)^{\dagger}|=|V(\Lambda_i)|-1\), we have \(S\cap V(\Lambda_i)\) is a determining set of the subgraph of \(\Gamma\) induced by \(V(\Lambda_i)^{\dagger}\). Therefore by Lemma 3.9, \(S=\cup_{i=1}^k(S\cap V(\Lambda_i)^{\dagger})\) is a determining set of \(\Gamma\). Now, we claim that \(S\) is a minimum determining set of \(\Gamma\). Let \(S’\) be any determining set of \(\Gamma\) with smaller cardinality than \(S\). Then there exists \(j\in [1,k]\) such that \(|V(\Lambda_j)^{\dagger}\setminus S’|\ge2\). Let \((j,u)\) and \((j,v)\) be two vertices in \(V(\Lambda_j)^{\dagger}\setminus S’\). Then by Theorem 4.4, there exists an automorphism, which fixes all the vertices except \((j,u)\) and \((j,v)\). Thus \(S’\) is not a determining set of \(\Gamma\) and hence \(S\) is a minimum determining set of \(\Gamma\). Therefore \(Det(\Gamma)=\left(\sum\limits_{i=1}^{k} |V(\Lambda_{i})|\right)-k\) ◻
Theorem 6.2. Suppose that \(\Gamma \cong \Lambda \bigl[\Lambda_{1},\Lambda_{2},\cdots , \Lambda_{k} \bigr]\), where \(\Lambda\) is any graph with the vertices \(1,2,\cdots, k\) and each \(\Lambda_i\) is a vertex-transitive graph. Then \(Det(\Gamma)=Det(\Lambda_{1})+Det(\Lambda_{2})+\cdots+Det(\Lambda_{k})\).
Proof. Since \(\Lambda_{i}\) is a vertex-transitive graph, the set, \(V(\Lambda_{i})^{\dagger}=\{(i,v):v\in V(\Lambda_{i})\}\) will be a vertex orbit of the graph \(\Gamma\). Suppose \(S_i\) is a minimum determining set of \(\Lambda_{i}\), that is, \(|S_i|=Det(\Lambda_{i})\). Then the set \(S_i^{\dagger}\) is a minimum determining set of the subgraph of \(\Gamma\) induced by \(V(\Lambda_i)^{\dagger}\). Now using Lemma 3.9, \(S=\bigcup_{i=1}^kS_i^{\dagger}\) is a determining set of \(\Gamma\).
To prove that \(S\) is a minimum determining set, assume that \(S’\) is a determining set of \(\Gamma\) such that \(|S’|<|S|\). Then there exists a vertex \(j\) of \(\Lambda\) such that \(|V(\Lambda_{j})^{\dagger}\cap S’|<|S_i^{\dagger}|\). Then the corresponding set \(\{v\in V(\Lambda_j): (j,v)\in V(\Lambda_{j})^{\dagger}\cap S’\}\) forms a determining set of \(\Lambda_i\). This contradicts the fact \(Det(\Lambda_{j})=|S_j|\). Hence, \(Det(\Gamma)=|S|=\sum\limits_{i=1}^{k} Det(\Lambda_{i})\). ◻
We know that \(Det(\Gamma)\le dim_M(\Gamma)\), for any graph \(\Gamma\). It is quite natural to ask how large this difference is. In 2006, Boutin [8] posed the following problem.
Problem 6.3. [8] Can the difference between the determining number of a graph and the size of a smallest resolving set of a graph be arbitrarily large?
Consider the infinite graph \(\Gamma\) in Figure 6, The graph \(\Gamma\) has the automorphism group isomorphic to \(C_2\), the cyclic group with two elements. Therefore, \(Det(\Gamma)=1\). Now, if \(S\) is any resolving set of \(\Gamma\) with a finite number of vertices, then one can find a positive integer \(n\) such that \(v_i\notin S\) whenever \(|i|\ge n\). Therefore, \(D_S(v_{-k})=D_S(v_{k})\) with \(k=n+1\) and hence, \(S\) not a resolving set. Thus, \(dim_M(\Gamma)\) can not be finite. The above example guarantees that the determining number of an infinite graph can be finite. One may think that for an infinite graph \(\Gamma\), the finiteness of \(Aut(\Gamma)\) enforces the determining number of \(\Gamma\) to be finite.
Remark 6.4. We note that the above example provides an affirmative answer to the question of whether the difference between the determining number and the metric dimension can be arbitrarily large, in the case of infinite graphs.
However, the problem posed by Boutin [8] concerns finite graphs. In this context, the question remains open, and it would be of interest to identify a class of finite graphs exhibiting such behaviour.
The following example illustrates that there may exist an infinite graph with an infinite automorphism group having finite determining number.
Consider an infinite graph having vertex set \(N\) and \(E(\Lambda)=\{(n,n+1):n\in \mathbb{N}\}\). Note that \(\Lambda\) does not have any non-trivial automorphism. Now we can take infinitely many copies of this graph, namely the graph \(\Lambda_1=(V_1,E_1)\) with \(V_1=\mathbb{N}\times\mathbb{N},E_1=\{((i,j),(i,j+1)):i,j\in \mathbb{N}\}\). As we do not have any non-trivial automorphisms inside the connected components, we have that the automorphisms are exactly the permutations that permute the connected components while keeping each of these components unaltered, and thus \(Aut(\Lambda_1)\cong S_{\mathbb{N}}\).
Now, add the set of vertices \(V_2=\{v_{\sigma}:\sigma\in S_{\mathbb{N}}\}\) and the set of edges \(E_2=\{(v_{\sigma},(i,j)):v_{\sigma}\in V_2,j\le \sigma^{-1}(i)\}\) to the existing graph. Basically, what we do here is, add a new vertex corresponding to each permutation on \(\mathbb{N}\), and for each such vertex \(v_{\sigma}\), we order the connected components by \(\sigma(1),\sigma(2),\cdots,\) and this vertex \(v_{\sigma}\) is made adjacent to the \(i-\)th components (after ordering with respect to \(\sigma\)) with \(i\) new edges, where the edges go to the first \(i\) vertices in the component.
Again define two sets \(V_3\) and \(E_3\), where \(V_3=\{u,u^{‘}\}, E_3=\{(u,u^{‘})\}\cup\{(u,v):v\in V_2\}\). This creates a new vertex and is connected by an edge to all of the \(v_\sigma\)’s and then yet a new vertex to connect to that vertex.
Finally, define a graph \(\Gamma\) with the vertex set \(V= V_1 \bigcup V_2 \bigcup V_3\) and the edge set \(E=E_1 \bigcup E_2 \bigcup E_3\). The above step by step construction of \(\Gamma\) is summarized below.
| Stage | Set of vertices | Set of edges |
|---|---|---|
| I | \(V_1=\mathbb{N}\times \mathbb{N}\) | \(E_1=\{((i,j),(i,j+1)):i,j\in \mathbb{N}\}\) |
| II | \(V_1\cup V_2\),\(V_2=\{v_{\sigma}:\sigma\in S_{\mathbb{N}}\}\) | \(E_1\cup E_2\),\(E_2=\{(v_{\sigma},(i,j)):v_{\sigma}\in V_2,j\le \sigma^{-1}(i)\}\) |
| III | \(V_1\cup V_2 \cup V_3\),\(V_3=\{u,u^{‘}\}\) | \(E_1\cup E_2\cup E_3\),\(E_3=\{(u,u^{‘})\}\cup\{(u,v):v\in V_2\}\) |
Now, let \(\psi\) be an automorphism of \(\Gamma\). Since \(u’\) is the only vertex of degree 1, \(\psi(u^{‘})=u^{‘}\). Also we must have \(\psi(u)=u\). As \(N(u)=N(\psi(u))=V_2\), we must have \(\psi(V_2)=V_2\). Consequently, \(w\in V_2\) implies \(\psi(w)\in V_2\) and therefore, \(w\in V_1\) if and only if \(\psi(w)\in V_1.\)
Note that \(\psi\) again permutes the connected components in \(V_1\). On contrary, if \(\psi(i,1)=(i’,j)\) with \(j>1\), then \(\psi(i,1)\) has two neighbors in \(V_1\). Therefore, \((i,1)\) must have 2 neighbors in \(V_1\), which is not true. Therefore, \(\psi(i,1)=\psi(i’,1)\) for some \(i’\in \mathbb{N}\) and it easily follows by induction that \(\psi(i,j)=\psi(i’,j’)\implies j=j’\). Hence every automorphism of \(\Gamma\) permutes the connected components of \(V_1\). Thus the group of automorphisms of \(\Gamma\) restricted to the domain \(V_1\) is isomorphic to \(S_{\mathbb{N}}\).
Let \(\sigma \in S_{\mathbb{N}}\), which maps \(\Gamma_i\) to \(\Gamma_{\sigma(i)}\), where \(\Gamma_i\) is a component of \(\Lambda_1\), which is a subgraph of \(\Gamma\) by taking only the vertices \(\{(i,j):j\in \mathbb{N}\}\), and \(\psi\) be an automorphism of \(\Gamma\) whose restriction to \(V_1\) is \(\sigma\).
We claim that \(\Gamma\) is unique. The number of edges from \(v_{\rho}\) of \(V_2\) to \(\Gamma_i\) must be the same as the number of edges between \(\psi(v_{\rho})\) and \(\Gamma_{\sigma(i)}\). Since there are \(\rho^{-1}(i)\) number of edges from \(v_{\sigma}\) to \(\Gamma_i\), we have no choice, except to fix \(\psi(v_{\rho})=v_{\sigma \circ \rho}\).
Therefore, \(Aut(\Gamma)\cong S_{\mathbb{N}}\), and notice that the automorphism \(\psi\) corresponding to \(\sigma\in S_{\mathbb{N}}\), maps \(v_{id}\) to \(v_{\sigma}\). That is, every automorphism of \(\Gamma\), can be represented uniquely by a \(\sigma\in S_{\mathbb{N}}\), and the vertex \(v_{id}\in V_2\subset V\) has the unique image \(v_{\sigma}\). Thus, by the definition of determining set, \(S=\{v_{id}\}\) is a determining set of \(\Gamma\). Therefore, a graph with automorphism group of infinite order, can have finite determining number.
The following open problem will be an interesting one to work with.
Problem 6.5. Determine necessary conditions for an infinite graph to have finite determining number.
In this article, we adopt a different approach to understanding the structure of zero-divisor graphs and a larger \(\Gamma(\mathbb{Z}_n)\) is expressed as a generalized join of smaller \(\Gamma_{Ann}(\mathbb{Z}_n)\) with a collection of complete and empty graphs. By using this structural identification, the determining number and the metric dimension of the zero-divisor graph of the ring \(\mathbb{Z}_n\), is determined and found both to be equal. Further, the determining number and metric dimension of the zero-divisor graph of finite non-Boolean semisimple rings, and Boolean rings are obtained. It is proved that there are rings, in which the determining number and the metric dimension of corresponding zero-divisor graphs, are distinct. The question: does there exist an infinite zero-divisor graph with a finite determining number? is taken up and is partially settled for Noetherian rings. We emphasize problems related to the determining number of general graphs. Moreover, we consider a problem posed by Boutin [8] and provide an affirmative answer in the setting of infinite graphs. We emphasize that our results provide an affirmative answer to Boutin’s question in the setting of infinite graphs, while the corresponding problem for finite graphs remains open and is of independent interest. In addition, we construct a graph with an infinite automorphism group having finite determining number.
The authors sincerely thank the Editor and the anonymous referees for their valuable comments and constructive suggestions. Their insightful feedback has significantly improved the quality, clarity, and presentation of this paper.
Data sharing is not applicable to this article as no datasets were generated or analysed during the current study.
The authors state that there is no conflict of interest.