# Metric Dimension, Minimal Doubly Resolving Sets, and the Strong Metric Dimension for Jellyfish Graph and Cocktail Party Graph

Authors: Jia-Bao Liu; Ali Zafari; Hassan Zarei
Journal: Complexity
 (2020)

---

## Abstract

LetΓ be a simple connected undirected graph with vertex set VΓ and edge set EΓ. The metric dimension of a graph Γ is the least number of vertices in a set with the property that the list of distances from any vertex to those in the set uniquely identifies that vertex. For an ordered subset W=w1,w2,…,wk of vertices in a graph Γ and a vertex v of Γ, the metric representation of v with respect to W is the k-vector rvW=dv,w1,dv,w2,…,dv,wk. If every pair of distinct vertices of Γ have different metric representations, then the ordered set W is called a resolving set of Γ. It is known that the problem of computing this invariant is NP-hard. In this paper, we consider the problem of determining the cardinality ψΓ of minimal doubly resolving sets of Γ and the strong metric dimension for the jellyfish graph JFGn,m and the cocktail party graph CPk+1.


---

## Body

## 1. Introduction

In this paper, we consider finite, simple, and connected graphs. The vertex and edge sets of a graphΓ are denoted by VΓ and EΓ, respectively. For u,v∈VΓ, the length of a shortest path from u to v is called the distance between u and v and is denoted by dΓu,v, or simply du,v. The adjacency and nonadjacency relations are denoted by ∼and ≁, respectively. The size of the largest clique in the graph Γ is denoted by ωΓ and the size of the largest independent sets of vertices by αΓ. A vertex x∈VΓ is said to resolve a pair u,v∈VΓ, if dΓu,x≠dΓv,x. For an ordered subset W=w1,w2,…,wk of vertices in a connected graph Γ and a vertex v of Γ, the metric representation of v with respect to W is the k-vector rvW=dv,w1,dv,w2,…,dv,wk. If every pair of distinct vertices of Γ have different metric representations, then the ordered set W is called a resolving set of Γ. Indeed, the set W is called a resolving set for Γ if ruW=rvW which implies that u=v for all pairs u,v of vertices of Γ. If the set W is as small as possible, then it is called a metric basis of the graph Γ. We recall that the metric dimension of Γ, denoted by βΓ, is defined as the minimum cardinality of a resolving set for Γ. If βΓ=k, then Γ is said to be k-dimensional. Chartrand et al. [1] determined the bounds of the metric dimensions for any connected graphs and determined the metric dimensions of some well-known families of graphs such as trees, paths, and complete graphs. Bounds on βΓ are presented in terms of the order and the diameter of Γ. All connected graphs of order n having metric dimension 1,n−1, or n−2 are determined. The concept of resolving the set and that of metric dimension date back to the 1950s. They were defined by Bluementhal [2] in the context of metric space. These notions were introduced to graph theory by Harary and Melter [3] and Slater [4] in the 1970s. For more results related to these concepts see [5–10]. These concepts have different applications in the areas of network discovery and verification [11], robot navigation [12], chemistry [1], and combinatorial optimization [13]. Notice for each connected graph Γ and each ordered set W=w1,w2,…,wk of vertices of Γ that the ith coordinate of rwiW is 0 and that the ith coordinate of all other vertex representations is positive. Thus, certainly ruW=rvW implies that u=v for u∈W. Therefore, when testing whether an ordered subset W of VΓ is a resolving set for Γ, we need only be concerned with the vertices of VΓ−W.Cáceres et al. [14] define the notion of a doubly resolving set as follows. Vertices x,y of the graph Γ of order at least 2 are said to doubly resolve vertices u,v of Γ if du,x−du,y≠dv,x−dv,y. A set Z=z1,z2,…,zl of vertices of Γ is a doubly resolving set of Γ if every two distinct vertices of Γ are doubly resolved by some two vertices of Z. The minimal doubly resolving set is a doubly resolving set with minimum cardinality. The cardinality of the minimum doubly resolving set is denoted by ψΓ. The minimal doubly resolving sets for Hamming and prism graphs have been obtained in [15,16], respectively. Other researchers in [17] determined the minimal doubly resolving sets for the necklace graph. Since if x,y doubly resolve u,v, then du,x−dv,x≠0 or du,y−dv,y≠0, and hence x or y resolve u,v. Therefore, a doubly resolving set is also a resolving set, and βΓ≤ψΓ.The strong metric dimension problem was introduced by Sebö and Tannier [13] and further investigated by Oellermann and Peters-Fransen [18]. Recently, the strong metric dimension of distance hereditary graphs has been studied by May and Oellermann [19]. For more results related to this concept see [20]. A vertex w strongly resolves two vertices u and v if u belongs to a shortest v−w path or v belongs to a shortest u−w path. A set N=n1,n2,…,nm of vertices of Γ is a strong resolving set of Γ if every two distinct vertices of Γ are strongly resolved by some vertex of N. A strong metric basis of Γ is a strong resolving set of the minimum cardinality. Now, the strong metric dimension of Γ, denoted by sdimΓ, is defined as the cardinality of its strong metric basis. It is easy to see that if a vertex w strongly resolves vertices u and v, then w also resolves these vertices. Hence, every strong resolving set is a resolving set, and βΓ≤sdimΓ.All three previously defined problems are NP-hard in general case. The proofs of NP-hardness are given for the metric dimension problem in [12], for the minimal doubly resolving set problem in [21], and for the strong metric dimension problem in [18]. Intrinsic metrics on a graph have become of interest, as generally discussed in [5,16,22–25], for some classes of graphs. In this paper, we consider the problem of determining the cardinality ψΓ of minimal doubly resolving sets of Γ and the strong metric dimension for the jellyfish graph JFGn,m and the cocktail party graph CPk+1. In fact, we find the minimum cardinality of the resolving set, doubly resolving set, and strong resolving set of the jellyfish graph JFGn,m. In particular, we show that the minimum cardinality of the resolving set, doubly resolving set, and strong resolving set of the cocktail party graph CPk+1 is k+1.


## 2. Definitions and Preliminaries

Definition 1.
(see [26]). Let Γ be a graph with automorphism group AutΓ. We say that Γ is a vertex transitive graph if, for any vertices x,y of Γ, there is some φ in AutΓ, such that φx=y. Also, we say that Γ is symmetric if, for all vertices u,v,x,y of Γ such that u and v are adjacent, and also, x and y are adjacent, there is an automorphism φ such that φu=x and φv=y. Finally, we say that Γ is a distance transitive if, for all vertices u,v,x,y of Γ such that du,v=dx,y, there is an automorphism φ such that φu=x and φv=y.Definition 2.
(see [26]). Let G be a finite group and Ω a subset of G that is closed under taking inverses and does not contain the identity. A Cayley graph Γ=CayG,Ω is a graph whose vertex set and edge set are defined as follows:(1)VΓ=G;EΓ=x,yx−1y∈Ω.Remark 1.
(see [26]). Let Γ be a graph. It is clear that we have a hierarchy of the conditions as follows:(2)distance transitive⇒symmetric⇒vertex transitive.Proposition 1.
(see [27]). Let Γ=Cayℤn,Sk be the Cayley graph on the cyclic group ℤnn≥4, where S1=1,n−1,…,Sk=Sk−1∪k,n−k are the inverse closed subsets of ℤn−0 for any k∈ℕ, 1≤k≤n/2−1. Then, χΓ=ωΓ=k+1 if and only if k+1n, where the chromatic number χΓ of Γ is the minimum number k such that Γ is k colorable.Definition 3.
(see [23]). Let Γ be a graph, and let W=w1,…,wk⊆VΓ. For each vertex v∈VΓ, the adjacency representation of v with respect to W is the k-vector:(3)r^vW=aΓv,w1,…,aΓv,wk,where(4)aΓv,wi=0,ifv=wi,1,ifv∼wi,2,ifv≁wi.
The setW is an adjacency resolving set for Γ if the vectors r^vW for v∈VΓ are distinct. The minimum cardinality of an adjacency resolving set is the adjacency dimension of Γ, denoted by β^Γ. An adjacency resolving set of cardinality β^Γ is an adjacency basis of Γ.Lemma 1.
(see [23]). Let Γ be a graph of order n.(1)
IfdiamΓ=2, then β^Γ=βΓ.(2)
IfΓ is connected, then β^Γ=βΓ.(3)
1≤β^Γ≤n−1.


## 3. Main Results

### 3.1. Metric Dimension, Minimal Doubly Resolving Sets, and the Strong Metric Dimension of the Jellyfish GraphJFGn,m

For an integern≥3, the n-cycle is the graph Cn with vertex set VCn=v1,v2,…,vn or simply 1,2,…,n and edge set ECn=vivi+1:1≤i≤n, where vn+1=v1. An interesting family of graphs of order nm+n is defined as follows. Let Γ be a graph with a vertex set V1∪V2, where V1=VCn and V2=A1j,A2j,…,Anj, and let Aij=∪j=1mvij, 1≤i≤n. Suppose that every vertex i∈V1 is adjacent to vertices vi1,vi2,…,vim∈Aij and degvij=1 for every vertex vij∈Aij, then the resulting graph is called the jellyfish graph JFGn,m with parameters m and n. In particular, if n is an even integer, then the jellyfish graph JFGn,m is a bipartite graph. In this paper, we consider the problem of determining the cardinality ψJFGn,m of minimal doubly resolving sets of the jellyfish graph JFGn,m. First, we find the metric dimension of the jellyfish graph JFGn,m, in fact we prove that if n≥3 and m≥2, then the metric dimension of the jellyfish graph JFGn,m is nm−n. Also, we consider the problem of determining the cardinality ψJFGn,m of minimal doubly resolving sets of JFGn,m and the strong metric dimension of the jellyfish graph JFGn,m. Moreover, we find an adjacency dimension of the jellyfish graph JFGn,m.Theorem 1.
Letn,m be integers such that n≥3 and m≥2. Then, the metric dimension of the jellyfish graph JFGn,m is nm−n.Proof.
LetVJFGn,m=V1∪V2, where V1=VCn=1,2,…,n and V2=A1j,A2j,…,Anj, and let Aij=∪j=1mvij, 1≤i≤n. Suppose that every vertex i∈V1 is adjacent to vertices vi1,vi2,…,vim∈Aij. We can show that the diameter of the jellyfish graph JFGn,m is n/2+2. In the following cases, we show that the metric dimension of the jellyfish graph JFGn,m is nm−n.Case 1. Let W be an ordered subset of V1 in the jellyfish graph JFGn,m such that W≤n. It is easy to prove that if W≤n, then W is not a resolving set of the jellyfish graph JFGn,m. In particular, if W=n, then we show that W is not a resolving set of the jellyfish graph JFGn,m. We may assume without loss of generality that an ordered subset is W=1,2,…,n. Hence, VJFGn,m−W=A1j,A2j,…,Anj. Therefore, the metric representation of the vertices v11,v12,…,v1m∈A1j with respect to W is the same as the n-vector. Thus, W is not a resolving set of the jellyfish graph JFGn,m.Case 2. Let W be an ordered subset of V2 in the jellyfish graph JFGn,m such that W=A2j,A3j,…,Anj. Hence, VJFGn,m−W=1,2,…,n,A1j. We know that W=nm−m. Therefore, the metric representation of the vertices v11,v12,…,v1m∈A1j with respect to W is the same as the nm−m-vector. Thus, W is not a resolving set of jellyfish graph JFGn,m.Case 3. Let W be an ordered subset of V2 in the jellyfish graph JFGn,m such that W=A1j,A2j,A3j,…,Anj−vn1,vn2. Hence, VJFGn,m−W=1,2,…,n,vn1,vn2. We know that W=nm−2. Therefore, the metric representation of the vertices vn1,vn2∈Anj with respect to W is the same as the nm−2-vector. Thus, W is not a resolving set of the jellyfish graph JFGn,m.Case 4. Let W be an ordered subset of V2 in the jellyfish graph JFGn,m such that W=nm−1. We show that W is a resolving set of the jellyfish graph JFGn,m. We may assume without loss of generality that an ordered subset is W=A1j,A2j,…,Anj−vnm. Hence, VJFGn,m−W=1,2,…,n,vnm. We can show that all the vertices 1,2,…,n,vnm∈VJFGn,m−W have different representations with respect to W. For every k∈VJFGn,m−W, 1≤k≤n and vij∈Aij, 1≤i≤n, and 1≤j≤m, if k=i, then we have dk,vij=1, otherwise dk,vij>1. Also, for the vertex vnm∈VJFGn,m−W with vnm≠vij∈Aij, 1≤i≤n, and 1≤j≤m, if i=n, then we have dvnm,vij=2, otherwise dvnm,vij>2. Therefore, all the vertices 1,2,…,n,vnm∈VJFGn,m−W have different representations with respect to W. This implies that W is a resolving set of the jellyfish graph JFGn,m.Case 5. Let W be an ordered subset of V2 in the jellyfish graph JFGn,m such that W=A1j−v1m,A2j−v2m,…,Anj−vnm. Hence, VJFGn,m−W=1,2,…,n,v1m,v2m,…,vnm. We know that W=nm−n. In a similar fashion which is done in Case 4, we can show that all the vertices 1,2,…,n,v1m,v2m,…,vnm∈VJFGn,m−W have different representations with respect to W. This implies that W is a resolving set of the jellyfish graph JFGn,m.Case 6. In particular, let W be an ordered subset of V2 in the jellyfish graph JFGn,m such that W=nm. We show that W is a resolving set of the jellyfish graph JFGn,m. We may assume without loss of generality that an ordered subset is W=A1j,A2j,…,Anj. Hence, VJFGn,m−W=1,2,…,n. We can show that all the vertices 1,2,…,n∈VJFGn,m−W have different representations with respect to W. This implies that W is a resolving set of the jellyfish graph JFGn,m.
From the above cases, we conclude that the minimum cardinality of a resolving set of the jellyfish graphJFGn,m is nm−n.Lemma 2.
Letnandm be integers such that n≥3 and m≥2. Then, the subset Z=A1j−v1m,A2j−v2m,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is not a doubly resolving set of the jellyfish graph JFGn,m.Proof.
We know that the ordered subsetZ=A1j−v1m,A2j−v2m,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is a resolving set of the jellyfish graph JFGn,m of size nm−n. Also by Theorem 1, the metric dimension of the jellyfish graph JFGn,m is βJFGn,m=nm−n. Moreover, BJFGn,m≤ψJFGn,m. We show that the subset Z=A1j−v1m,A2j−v2m,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is not a doubly resolving set of the jellyfish graph JFGn,m. If u=vim and v=i and 1≤i≤n, then for every x,y∈Z, we have du,x−du,y=dv,x−dv,y.Lemma 3.
Letnandm be integers such that n≥3 and m≥2. Then, the subset Z=A1j,A2j,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is not a doubly resolving set of the jellyfish graph JFGn,m.Proof.
We show that the subsetZ=A1j,A2j,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is not a doubly resolving set of the jellyfish graph JFGn,m. If u=vnm and v=n, then for every x,y∈Z, we have du,x−du,y=dv,x−dv,y.Theorem 2.
Letnandm be integers such that n≥3 and m≥2. Then, the cardinality of the minimum doubly resolving set of the jellyfish graph JFGn,m is nm.Proof.
LetVJFGn,m=V1∪V2, where V1=VCn=1,2,…,n and V2=A1j,A2j,…,Anj, and let Aij=∪j=1mvij, 1≤i≤n. Suppose that every vertex i∈V1 is adjacent to vertices vi1,vi2,…,vim∈Aij. We know that the ordered subset vi1,vi2,…,vim∈Aij of vertices in the jellyfish graph JFGn,m is a resolving set of the jellyfish graph JFGn,m of size nm. Also by Theorem 1, the metric dimension of the jellyfish graph JFGn,m is JFGn,m. Moreover, BJFGn,m≤ψJFGn,m. We show that the subset Z=A1j,A2j,…,Anj of vertices in the jellyfish graph JFGn,m is a doubly resolving set of the jellyfish graph JFGn,m. It is sufficient to show that for two vertices u and v of the jellyfish graph JFGn,m there are vertices x,y∈Z such that du,x−du,y≠dv,x−dv,y. Consider two vertices u and v of the jellyfish graph JFGn,m. Then, we have the following:Case 1. Let u∉Z and v∉Z. Hence, u,v∈V1=VCn=1,2,…,n. We can assume without loss of generality that u=i and v=j, 1≤i,j≤n, and i≠j. Therefore, if x=vi1 and y=vj1, and then we have du,x−du,y≠dv,x−dv,y because du,x−du,y<0 and dv,x−dv,y>0.Case 2. Let u∈Z and v∈Z. Hence, u,v∈V2=A1j,A2j,…,Anj. Therefore, if x=u and y=v, then we have du,x−du,y≠dv,x−dv,y because du,x−du,y<0 and dv,x−dv,y>0.Case 3. Finally, let u∉Z and v∈Z. Hence, u∈V1=VCn=1,2,…,n and v∈V2=A1j,A2j,…,Anj. We can assume without loss of generality that u=k, 1≤k≤n, and v=v11∈A11. Therefore, if x=vk2 and y=v11, then we have du,x−du,y≠dv,x−dv,y because du,x−du,y≤0 and dv,x−dv,y>0.
Thus, by Lemmas2 and 3 and the above cases, we conclude that the cardinality of the minimum doubly resolving set of the jellyfish graph JFGn,m is nm.Lemma 4.
Letnandm be integers such that n≥3 and m≥2. Then, the subset N=A1j−v1m,A2j−v2m,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is not a strong resolving set of the jellyfish graph JFGn,m.Proof.
LetM=V2−N=v1m,v2m,…,vnm, where V2 is the set which is defined already. It is not hard to see that for every two distinct vertices u,v∈M, there is not a vertex w∈N such that u belongs to a shortest v−w path or v belongs to a shortest u−w path. So, the subset N=A1j−v1m,A2j−v2m,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is not a strong resolving set of the jellyfish graph JFGn,m. We conclude that if N is a strong resolving set of the jellyfish graph JFGn,m, then N≥nm−1 because M must be less than 2.Theorem 3.
Letnandm be integers such that n≥3 and m≥2. Then, the strong metric dimension of the jellyfish graph JFGn,m is nm−1.Proof.
By Lemma4, we know that if N is a strong resolving set of the jellyfish graph JFGn,m, then N≥nm−1. We show that the subset N=A1j,A2j,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is a strong resolving set of the jellyfish graph JFGn,m. It is sufficient to prove that every two distinct vertices u,v∈VJFGn,m−N=1,2,…,n,vnm are strongly resolved by a vertex w∈N. In the following cases, we show that the strong metric dimension of the jellyfish graph JFGn,m is nm−1.Case 1. Let u and v be two distinct vertices in VJFGn,m−N such that u,v∈V1=VCn=1,2,…,n. So, there is i,j∈V1 such that u=i and v=j. Therefore, i and j will be strongly resolved by some vij∈Aij because i and vij are adjacent, and hence i belongs to a shortest vij−j path.Case 2. Now, let u and v be two distinct vertices in VJFGn,m−N such that u∈V1=1,2,…,n and v=vnm. Without loss of generality we may assume u=i, where i∈V1. Therefore, i and vnm will be strongly resolved by some vij∈Aij because i and vij are adjacent, and hence i belongs to a shortest vij−vnm path.
From the above cases, we conclude that the minimum cardinality of a strong metric dimension of the jellyfish graphJFGn,m is nm−1.Lemma 5.
Letnandm be integers such that n≥3 and m≥2. Then, an ordered subset W=A1j−v1m,A2j−v2m,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is not the adjacency resolving set of the jellyfish graph JFGn,m.Proof.
LetΓ=JFGn,m and M=V2−W=v1m,v2m,…,vnm, where V2 is the set which is defined already. Thus, the adjacency representation of the vertices v1m,v2m,…,vnm∈VJFGn,m−W with respect to W is the nm−n-vector r^v1mW=r^v2mW=…=r^vnmW=2,2,…,2. For every vertex w∈W, we have aΓw,v1m=aΓw,v1m=…=aΓw,vnm=2. We conclude that if W is an adjacency resolving set of the jellyfish graph JFGn,m, then W≥nm−1 because M must be less than 2.Theorem 4.
Letnandm be integers such that n≥3 and m≥2. Then, the adjacency dimension of the jellyfish graph JFGn,m is nm−1.Proof.
By Lemma5, we know that if W is an adjacency resolving set of the jellyfish graph JFGn,m, then W≥nm−1. Now, let Γ=JFGn,m and W be an ordered subset of V2 in the jellyfish graph JFGn,m such that W=nm−1. We show that W is an adjacency resolving set of the jellyfish graph JFGn,m. We may assume without loss of generality that an ordered subset is W=A1j,A2j,…,Anj−vnm. Hence, VJFGn,m−W=1,2,…,n,vnm. We can show that all the vertices 1,2,…,n,vnm∈VJFGn,m−W have different adjacency representations with respect to W. For every k∈VJFGn,m−W, 1≤k≤n and vij∈Aij, 1≤i≤n, and 1≤j≤m, if k=i, then we have aΓk,vij=1, otherwise aΓk,vij=2. Also, for the vertex vnm∈VJFGn,m−W with vnm≠vij∈Aij, 1≤i≤n, and 1≤j≤m, we have aΓvnm,vij=2. Therefore, all the vertices 1,2,…,n,vnm∈VJFGn,m−W have different adjacency representations with respect to W. This implies that W is an adjacency resolving set of the jellyfish graph JFGn,m. We now conclude that the minimum cardinality of the adjacency resolving set of the jellyfish graph JFGn,m is nm−1.


### 3.2. Metric Dimension, Minimal Doubly Resolving Sets, and the Strong Metric Dimension of the Cocktail Party GraphCPk+1

LetΓ=Cayℤn,Sk be the Cayley graph on the cyclic additive group ℤn, where S1=1,n−1,…,Sk=Sk−1∪k,n−k are the inverse closed subsets of ℤn−0 for any k∈ℕ, 1≤k≤n/2−1. If n is an even integer and k=n/2−1, then we can show that Cayℤn,Sk is obtained from the complete graph K2k+1 by deleting a perfect matching, and hence Cayℤn,Sk is isomorphic to the cocktail party graph CPk+1. Moreover, we can show that CayD2n,Ω, where(5)D2n=a,ban=b2=1,ba=an−1b,is the dihedral group of order 2n and Ω=a,a2,…,an−1,ab,a2b,…,an−1b is the inverse closed subset of D2n−1, is isomorphic to the cocktail party graph CPn. In this section, we consider the problem of determining the cardinality ψΓ of minimal doubly resolving sets of Γ. First, we show that if n is an even integer and k=n/2−1, then the metric dimension of Γ is k+1. Also, we prove that if n is an even integer and k=n/2−1, then every minimal resolving set of Γ is also a doubly resolving set, and, consequently, ψΓ is equal to the metric dimension of βΓ, which is known from the literature. Moreover, we find an explicit expression for the strong metric dimension of Γ.Theorem 5.
LetΓ=Cayℤn,Sk be the Cayley graph on the cyclic group ℤnn≥8, where S1=1,n−1,…,Sk=Sk−1∪k,n−k are the inverse closed subsets of ℤn−0 for any k∈ℕ, 1≤k≤n/2−1. If n is an even integer and k=n/2−1, then the metric dimension of Γ is k+1.Proof.
LetVΓ=1,…,n be the vertex set of Γ. By proof of Proposition 3.4 in [27], we know that the diameter of Γ is 2. Hence, for all the vertices x,y∈VΓ, the length of a shortest path from x to y is dx,y=1 or 2. Also, we know that the size of the largest clique in the graph Γ is k+1. Now, let W be an ordered subset of vertices in the graph Γ such that W is a clique in Γ. Indeed, for every x,y∈W, we have dΓx,y=1. In the following cases, we show that the metric dimension of Γ is k+1.Case 1. It is easy to see that if W≤k, then W is not a resolving set of Γ. In particular, if W=k, then we show that W is not a resolving set of Γ. We may assume without loss of generality that an ordered subset of vertices in the graph Γ is W=1,2,3,…,k. Hence, VΓ−W=k+1,k+2,…,n. On the contrary, by proof of Proposition 3.2 in [27], we know that for every vertex x in Γ, there is exactly one y in Γ such that x−1y=k+1, that is, dx,y=2. Hence, there are vertices k+2,k+3,…,n−1 in VΓ−W such that d1,k+2=2,d2,k+3=2,…,dk,n−1=2. Therefore, the metric representations of the vertices k+2,k+3,…,n−1∈VΓ−W with respect to W are the k-vectors rk+2W=2,1,1,…,1,rk+3W=1,2,1,…,1,…,rnW=1,1,1,…,2. Moreover, the metric representation of the vertices k+1,n∈VΓ−W with respect to W is the k-vector rk+1W=rnW=1,1,1,…,1. Thus, W is not a resolving set of Γ because the metric representation of the vertices k+1,n is the same as the k-vector.Case 2. Let W be a clique in the graph Γ such that x∈W and W=k. We know that there is exactly one y in VΓ−W such that x−1y=k+1, that is, dx,y=2. In the following, we show that an ordered subset W∪y of vertices in the graph Γ is not a resolving set of Γ. In this case, we may assume without loss of generality that an ordered subset of vertices in the graph Γ is W=1,2,…,k, and let x=1 and y=k+2. Therefore, the metric representation of the vertices k+1,n∈VΓ−W∪y with respect to W∪y is the k+1-vector rk+1W=rnW=1,1,1,…,1. Thus, W∪y is not a resolving set of Γ.Case 3. Now, let W be a clique in the graph Γ such that W=k+1. We show that W is a resolving set of Γ. We may assume without loss of generality that an ordered subset of vertices in the graph Γ is W=1,2,3,…,k,k+1. Hence, VΓ−W=k+2,k+3,…,n. Therefore, the metric representations of the vertices k+2,k+3,…,n∈VΓ−W with respect to W are the k+1-vectors rk+2W=2,1,1,…,1,rk+3W=1,2,1,…,1,…,rnW=1,1,1,…,2. Thus, all the vertices of VΓ−W have different representations with respect to W. This implies that W is a resolving set of Γ. Moreover, the metric dimension of βΓ≤k+1 because Γ is a vertex transitive graph.Case 4. In particular, let W be a clique in the graph Γ such that W=k+1. We show that for each x∈VΓ−W, an ordered subset W∪x of vertices in the graph Γ is also a resolving set of Γ. We may assume without loss of generality that an ordered subset of vertices in the graph Γ is W=1,2,3,…,k,k+1, and let x=k+2. So, W∪x=1,2,3,…,k+1,k+2. Hence, VΓ−W∪x=k+3,k+4,…,n. Therefore, the metric representations of the vertices k+3,k+4,…,n∈VΓ−W∪x, with respect to W∪x, are the k+2-vectors rk+3W=1,2,1,…,1,1,rk+4W=1,2,1,…,1,1,…,rnW=1,2,1,…,1,1. This implies that W∪x is also a resolving set of Γ.
From the above cases, we conclude that the minimum cardinality of a resolving set ofΓ is k+1. Moreover, it is well known that every Cayley graph is a vertex transitive. Hence, the cardinality of every minimal resolving set in Γ is k+1.Theorem 6.
LetΓ=Cayℤn,Sk be the Cayley graph on the cyclic group ℤnn≥8, where S1=1,n−1,…,Sk=Sk−1∪k,n−k are the inverse closed subsets of ℤn−0 for any k∈ℕ, 1≤k≤n/2−1. If n is an even integer and k=n/2−1, then the cardinality of the minimum doubly resolving set of Γ is k+1.Proof.
In this theorem, letVΓ=v1,v2,…,vn, where vi=i for 1≤i≤n. We know that the ordered subset Z=1,2,3,…,k,k+1 of vertices in the graph Γ is a resolving set for Γ of size k+1. Also, by Theorem 5, the metric dimension of Γ is βΓ=k+1. Moreover, BΓ≤ψΓ. We show that the subset Z=1,2,3,…,k,k+1 of vertices in the graph Γ is a doubly resolving set of Γ. It is sufficient to show that for two vertices vi and vj of Γ, there are vertices x,y∈Z such that dvi,x−dvi,y≠dvj,x−dvj,y. Consider two vertices vi and vj of Γ. We may assume that i<j. In the following cases, we show that the cardinality of the minimum doubly resolving set of Γ is k+1.Case 1. If 1≤i<j≤k+1, then vi,vj∈Z. So, dvi,vj=1. We can assume that x=vi∈Z and y=vj∈Z. Hence, we have dvi,x−dvi,y≠dvj,x−dvj,y because dvi,x−dvj,y<0 and dvj,x−dvj,y>0.Case 2. Let 1≤i≤k+1<j≤n. Hence, vi∈Z and vj∉Z. Moreover, we know that dvi,vj=1 or 2. In the following, let dvi,vj=1. We may assume that vi=1 and vj=n. Hence, by taking x=vi∈Z and y=k+1∈Z, we have 0=0−0=dvi,x−dvi,y≠dvj,x−dvj,y=1−2=−1. Thus, the vertices x and y of Z doubly resolve vi,vj. Now, let dvi,vj=2. We may assume that vi=1 and vj=k+2. Hence, by taking x=1∈Z and y=2∈Z, we have −1=0−1=dvi,x−dvi,y≠dvj,x−dvj,y=2−1=1. Thus, the vertices x and y of Z doubly resolve vi,vj.Case 3. Finally, let 1<k+1<i<j≤n. Hence, vi∉Z and vj∉Z. Also, we know that dvi,vj=1. On the conrary, by proof of Proposition 3.2 in [27], we know that for every vertex vi∈VΓ−Z, there is exactly one x∈Z such that dvi,x=2. Also, for every vertex vj∈VΓ−Z, there is exactly one y∈Z such that dvj,y=2. Hence, 1=2−1=dvi,x−dvi,y≠dvj,x−dvj,y=1−2=−1. Thus, the vertices x and y of Z doubly resolve vi,vj.
From the above cases, we conclude that the minimum cardinality of a doubly resolving set ofΓ is k+1.Theorem 7.
LetΓ=Cayℤn,Sk be the Cayley graph on the cyclic group ℤnn≥8, where S1=1,n−1,…,Sk=Sk−1∪k,n−k are the inverse closed subsets of ℤn−0 for any k∈ℕ, 1≤k≤n/2−1. If n is an even integer and k=n/2−1, then the strong metric dimension of Γ is k+1.Proof.
In this theorem, letVΓ=v1,v2,…,vn, where vi=i for 1≤i≤n. We know that the ordered subset N=1,2,3,…,k,k+1 of vertices in the graph Γ is a resolving set for Γ of size k+1. Also, by Theorem 5, the metric dimension of Γ is βΓ=k+1. Moreover, BΓ≤sdimΓ. We show that the subset N=1,2,3,…,k,k+1 of vertices in the graph Γ is a strong resolving set of Γ. Consider two vertices vi and vj of Γ. Assume that i<j. It is sufficient to prove that there exists a vertex w∈N such that vi belongs to a shortest vj−w path or vj belongs to a shortest vi−w path. Let 1<k+1<i<j≤n. Hence, vi∉N and vj∉N. Moreover, we have dvi,vj=1. On the contrary, by proof of Proposition 3.2 in [27], we know that for every vertex vi∈VΓ−N, there is exactly one w∈N such that vi−1w=k+1, indeed dvi,w=2. Hence, dvj,w=1. So, dvi,w=dvi,vj+dvj,w, that is, vertex vj belongs to a shortest vi−w path, and hence w strongly resolves vertices vi and vj. Also, for vi∈N or vj∈N, vertex vi or vertex vj obviously strongly resolves pair vi,vj. Therefore, N is a strong resolving set. Thus, the minimum cardinality of a strong resolving set of Γ is k+1.Conclusion 1.
LetCPn≅CayD2n,Ω be the Cayley graph on the dihedral group D2n, where Ω is the inverse closed subset of D2n−1 which is defined already. Then, the minimum cardinality of resolving set, doubly resolving set, and strong resolving set of CPn is n.


## 3.1. Metric Dimension, Minimal Doubly Resolving Sets, and the Strong Metric Dimension of the Jellyfish GraphJFGn,m

For an integern≥3, the n-cycle is the graph Cn with vertex set VCn=v1,v2,…,vn or simply 1,2,…,n and edge set ECn=vivi+1:1≤i≤n, where vn+1=v1. An interesting family of graphs of order nm+n is defined as follows. Let Γ be a graph with a vertex set V1∪V2, where V1=VCn and V2=A1j,A2j,…,Anj, and let Aij=∪j=1mvij, 1≤i≤n. Suppose that every vertex i∈V1 is adjacent to vertices vi1,vi2,…,vim∈Aij and degvij=1 for every vertex vij∈Aij, then the resulting graph is called the jellyfish graph JFGn,m with parameters m and n. In particular, if n is an even integer, then the jellyfish graph JFGn,m is a bipartite graph. In this paper, we consider the problem of determining the cardinality ψJFGn,m of minimal doubly resolving sets of the jellyfish graph JFGn,m. First, we find the metric dimension of the jellyfish graph JFGn,m, in fact we prove that if n≥3 and m≥2, then the metric dimension of the jellyfish graph JFGn,m is nm−n. Also, we consider the problem of determining the cardinality ψJFGn,m of minimal doubly resolving sets of JFGn,m and the strong metric dimension of the jellyfish graph JFGn,m. Moreover, we find an adjacency dimension of the jellyfish graph JFGn,m.Theorem 1.
Letn,m be integers such that n≥3 and m≥2. Then, the metric dimension of the jellyfish graph JFGn,m is nm−n.Proof.
LetVJFGn,m=V1∪V2, where V1=VCn=1,2,…,n and V2=A1j,A2j,…,Anj, and let Aij=∪j=1mvij, 1≤i≤n. Suppose that every vertex i∈V1 is adjacent to vertices vi1,vi2,…,vim∈Aij. We can show that the diameter of the jellyfish graph JFGn,m is n/2+2. In the following cases, we show that the metric dimension of the jellyfish graph JFGn,m is nm−n.Case 1. Let W be an ordered subset of V1 in the jellyfish graph JFGn,m such that W≤n. It is easy to prove that if W≤n, then W is not a resolving set of the jellyfish graph JFGn,m. In particular, if W=n, then we show that W is not a resolving set of the jellyfish graph JFGn,m. We may assume without loss of generality that an ordered subset is W=1,2,…,n. Hence, VJFGn,m−W=A1j,A2j,…,Anj. Therefore, the metric representation of the vertices v11,v12,…,v1m∈A1j with respect to W is the same as the n-vector. Thus, W is not a resolving set of the jellyfish graph JFGn,m.Case 2. Let W be an ordered subset of V2 in the jellyfish graph JFGn,m such that W=A2j,A3j,…,Anj. Hence, VJFGn,m−W=1,2,…,n,A1j. We know that W=nm−m. Therefore, the metric representation of the vertices v11,v12,…,v1m∈A1j with respect to W is the same as the nm−m-vector. Thus, W is not a resolving set of jellyfish graph JFGn,m.Case 3. Let W be an ordered subset of V2 in the jellyfish graph JFGn,m such that W=A1j,A2j,A3j,…,Anj−vn1,vn2. Hence, VJFGn,m−W=1,2,…,n,vn1,vn2. We know that W=nm−2. Therefore, the metric representation of the vertices vn1,vn2∈Anj with respect to W is the same as the nm−2-vector. Thus, W is not a resolving set of the jellyfish graph JFGn,m.Case 4. Let W be an ordered subset of V2 in the jellyfish graph JFGn,m such that W=nm−1. We show that W is a resolving set of the jellyfish graph JFGn,m. We may assume without loss of generality that an ordered subset is W=A1j,A2j,…,Anj−vnm. Hence, VJFGn,m−W=1,2,…,n,vnm. We can show that all the vertices 1,2,…,n,vnm∈VJFGn,m−W have different representations with respect to W. For every k∈VJFGn,m−W, 1≤k≤n and vij∈Aij, 1≤i≤n, and 1≤j≤m, if k=i, then we have dk,vij=1, otherwise dk,vij>1. Also, for the vertex vnm∈VJFGn,m−W with vnm≠vij∈Aij, 1≤i≤n, and 1≤j≤m, if i=n, then we have dvnm,vij=2, otherwise dvnm,vij>2. Therefore, all the vertices 1,2,…,n,vnm∈VJFGn,m−W have different representations with respect to W. This implies that W is a resolving set of the jellyfish graph JFGn,m.Case 5. Let W be an ordered subset of V2 in the jellyfish graph JFGn,m such that W=A1j−v1m,A2j−v2m,…,Anj−vnm. Hence, VJFGn,m−W=1,2,…,n,v1m,v2m,…,vnm. We know that W=nm−n. In a similar fashion which is done in Case 4, we can show that all the vertices 1,2,…,n,v1m,v2m,…,vnm∈VJFGn,m−W have different representations with respect to W. This implies that W is a resolving set of the jellyfish graph JFGn,m.Case 6. In particular, let W be an ordered subset of V2 in the jellyfish graph JFGn,m such that W=nm. We show that W is a resolving set of the jellyfish graph JFGn,m. We may assume without loss of generality that an ordered subset is W=A1j,A2j,…,Anj. Hence, VJFGn,m−W=1,2,…,n. We can show that all the vertices 1,2,…,n∈VJFGn,m−W have different representations with respect to W. This implies that W is a resolving set of the jellyfish graph JFGn,m.
From the above cases, we conclude that the minimum cardinality of a resolving set of the jellyfish graphJFGn,m is nm−n.Lemma 2.
Letnandm be integers such that n≥3 and m≥2. Then, the subset Z=A1j−v1m,A2j−v2m,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is not a doubly resolving set of the jellyfish graph JFGn,m.Proof.
We know that the ordered subsetZ=A1j−v1m,A2j−v2m,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is a resolving set of the jellyfish graph JFGn,m of size nm−n. Also by Theorem 1, the metric dimension of the jellyfish graph JFGn,m is βJFGn,m=nm−n. Moreover, BJFGn,m≤ψJFGn,m. We show that the subset Z=A1j−v1m,A2j−v2m,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is not a doubly resolving set of the jellyfish graph JFGn,m. If u=vim and v=i and 1≤i≤n, then for every x,y∈Z, we have du,x−du,y=dv,x−dv,y.Lemma 3.
Letnandm be integers such that n≥3 and m≥2. Then, the subset Z=A1j,A2j,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is not a doubly resolving set of the jellyfish graph JFGn,m.Proof.
We show that the subsetZ=A1j,A2j,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is not a doubly resolving set of the jellyfish graph JFGn,m. If u=vnm and v=n, then for every x,y∈Z, we have du,x−du,y=dv,x−dv,y.Theorem 2.
Letnandm be integers such that n≥3 and m≥2. Then, the cardinality of the minimum doubly resolving set of the jellyfish graph JFGn,m is nm.Proof.
LetVJFGn,m=V1∪V2, where V1=VCn=1,2,…,n and V2=A1j,A2j,…,Anj, and let Aij=∪j=1mvij, 1≤i≤n. Suppose that every vertex i∈V1 is adjacent to vertices vi1,vi2,…,vim∈Aij. We know that the ordered subset vi1,vi2,…,vim∈Aij of vertices in the jellyfish graph JFGn,m is a resolving set of the jellyfish graph JFGn,m of size nm. Also by Theorem 1, the metric dimension of the jellyfish graph JFGn,m is JFGn,m. Moreover, BJFGn,m≤ψJFGn,m. We show that the subset Z=A1j,A2j,…,Anj of vertices in the jellyfish graph JFGn,m is a doubly resolving set of the jellyfish graph JFGn,m. It is sufficient to show that for two vertices u and v of the jellyfish graph JFGn,m there are vertices x,y∈Z such that du,x−du,y≠dv,x−dv,y. Consider two vertices u and v of the jellyfish graph JFGn,m. Then, we have the following:Case 1. Let u∉Z and v∉Z. Hence, u,v∈V1=VCn=1,2,…,n. We can assume without loss of generality that u=i and v=j, 1≤i,j≤n, and i≠j. Therefore, if x=vi1 and y=vj1, and then we have du,x−du,y≠dv,x−dv,y because du,x−du,y<0 and dv,x−dv,y>0.Case 2. Let u∈Z and v∈Z. Hence, u,v∈V2=A1j,A2j,…,Anj. Therefore, if x=u and y=v, then we have du,x−du,y≠dv,x−dv,y because du,x−du,y<0 and dv,x−dv,y>0.Case 3. Finally, let u∉Z and v∈Z. Hence, u∈V1=VCn=1,2,…,n and v∈V2=A1j,A2j,…,Anj. We can assume without loss of generality that u=k, 1≤k≤n, and v=v11∈A11. Therefore, if x=vk2 and y=v11, then we have du,x−du,y≠dv,x−dv,y because du,x−du,y≤0 and dv,x−dv,y>0.
Thus, by Lemmas2 and 3 and the above cases, we conclude that the cardinality of the minimum doubly resolving set of the jellyfish graph JFGn,m is nm.Lemma 4.
Letnandm be integers such that n≥3 and m≥2. Then, the subset N=A1j−v1m,A2j−v2m,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is not a strong resolving set of the jellyfish graph JFGn,m.Proof.
LetM=V2−N=v1m,v2m,…,vnm, where V2 is the set which is defined already. It is not hard to see that for every two distinct vertices u,v∈M, there is not a vertex w∈N such that u belongs to a shortest v−w path or v belongs to a shortest u−w path. So, the subset N=A1j−v1m,A2j−v2m,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is not a strong resolving set of the jellyfish graph JFGn,m. We conclude that if N is a strong resolving set of the jellyfish graph JFGn,m, then N≥nm−1 because M must be less than 2.Theorem 3.
Letnandm be integers such that n≥3 and m≥2. Then, the strong metric dimension of the jellyfish graph JFGn,m is nm−1.Proof.
By Lemma4, we know that if N is a strong resolving set of the jellyfish graph JFGn,m, then N≥nm−1. We show that the subset N=A1j,A2j,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is a strong resolving set of the jellyfish graph JFGn,m. It is sufficient to prove that every two distinct vertices u,v∈VJFGn,m−N=1,2,…,n,vnm are strongly resolved by a vertex w∈N. In the following cases, we show that the strong metric dimension of the jellyfish graph JFGn,m is nm−1.Case 1. Let u and v be two distinct vertices in VJFGn,m−N such that u,v∈V1=VCn=1,2,…,n. So, there is i,j∈V1 such that u=i and v=j. Therefore, i and j will be strongly resolved by some vij∈Aij because i and vij are adjacent, and hence i belongs to a shortest vij−j path.Case 2. Now, let u and v be two distinct vertices in VJFGn,m−N such that u∈V1=1,2,…,n and v=vnm. Without loss of generality we may assume u=i, where i∈V1. Therefore, i and vnm will be strongly resolved by some vij∈Aij because i and vij are adjacent, and hence i belongs to a shortest vij−vnm path.
From the above cases, we conclude that the minimum cardinality of a strong metric dimension of the jellyfish graphJFGn,m is nm−1.Lemma 5.
Letnandm be integers such that n≥3 and m≥2. Then, an ordered subset W=A1j−v1m,A2j−v2m,…,Anj−vnm of vertices in the jellyfish graph JFGn,m is not the adjacency resolving set of the jellyfish graph JFGn,m.Proof.
LetΓ=JFGn,m and M=V2−W=v1m,v2m,…,vnm, where V2 is the set which is defined already. Thus, the adjacency representation of the vertices v1m,v2m,…,vnm∈VJFGn,m−W with respect to W is the nm−n-vector r^v1mW=r^v2mW=…=r^vnmW=2,2,…,2. For every vertex w∈W, we have aΓw,v1m=aΓw,v1m=…=aΓw,vnm=2. We conclude that if W is an adjacency resolving set of the jellyfish graph JFGn,m, then W≥nm−1 because M must be less than 2.Theorem 4.
Letnandm be integers such that n≥3 and m≥2. Then, the adjacency dimension of the jellyfish graph JFGn,m is nm−1.Proof.
By Lemma5, we know that if W is an adjacency resolving set of the jellyfish graph JFGn,m, then W≥nm−1. Now, let Γ=JFGn,m and W be an ordered subset of V2 in the jellyfish graph JFGn,m such that W=nm−1. We show that W is an adjacency resolving set of the jellyfish graph JFGn,m. We may assume without loss of generality that an ordered subset is W=A1j,A2j,…,Anj−vnm. Hence, VJFGn,m−W=1,2,…,n,vnm. We can show that all the vertices 1,2,…,n,vnm∈VJFGn,m−W have different adjacency representations with respect to W. For every k∈VJFGn,m−W, 1≤k≤n and vij∈Aij, 1≤i≤n, and 1≤j≤m, if k=i, then we have aΓk,vij=1, otherwise aΓk,vij=2. Also, for the vertex vnm∈VJFGn,m−W with vnm≠vij∈Aij, 1≤i≤n, and 1≤j≤m, we have aΓvnm,vij=2. Therefore, all the vertices 1,2,…,n,vnm∈VJFGn,m−W have different adjacency representations with respect to W. This implies that W is an adjacency resolving set of the jellyfish graph JFGn,m. We now conclude that the minimum cardinality of the adjacency resolving set of the jellyfish graph JFGn,m is nm−1.


## 3.2. Metric Dimension, Minimal Doubly Resolving Sets, and the Strong Metric Dimension of the Cocktail Party GraphCPk+1

LetΓ=Cayℤn,Sk be the Cayley graph on the cyclic additive group ℤn, where S1=1,n−1,…,Sk=Sk−1∪k,n−k are the inverse closed subsets of ℤn−0 for any k∈ℕ, 1≤k≤n/2−1. If n is an even integer and k=n/2−1, then we can show that Cayℤn,Sk is obtained from the complete graph K2k+1 by deleting a perfect matching, and hence Cayℤn,Sk is isomorphic to the cocktail party graph CPk+1. Moreover, we can show that CayD2n,Ω, where(5)D2n=a,ban=b2=1,ba=an−1b,is the dihedral group of order 2n and Ω=a,a2,…,an−1,ab,a2b,…,an−1b is the inverse closed subset of D2n−1, is isomorphic to the cocktail party graph CPn. In this section, we consider the problem of determining the cardinality ψΓ of minimal doubly resolving sets of Γ. First, we show that if n is an even integer and k=n/2−1, then the metric dimension of Γ is k+1. Also, we prove that if n is an even integer and k=n/2−1, then every minimal resolving set of Γ is also a doubly resolving set, and, consequently, ψΓ is equal to the metric dimension of βΓ, which is known from the literature. Moreover, we find an explicit expression for the strong metric dimension of Γ.Theorem 5.
LetΓ=Cayℤn,Sk be the Cayley graph on the cyclic group ℤnn≥8, where S1=1,n−1,…,Sk=Sk−1∪k,n−k are the inverse closed subsets of ℤn−0 for any k∈ℕ, 1≤k≤n/2−1. If n is an even integer and k=n/2−1, then the metric dimension of Γ is k+1.Proof.
LetVΓ=1,…,n be the vertex set of Γ. By proof of Proposition 3.4 in [27], we know that the diameter of Γ is 2. Hence, for all the vertices x,y∈VΓ, the length of a shortest path from x to y is dx,y=1 or 2. Also, we know that the size of the largest clique in the graph Γ is k+1. Now, let W be an ordered subset of vertices in the graph Γ such that W is a clique in Γ. Indeed, for every x,y∈W, we have dΓx,y=1. In the following cases, we show that the metric dimension of Γ is k+1.Case 1. It is easy to see that if W≤k, then W is not a resolving set of Γ. In particular, if W=k, then we show that W is not a resolving set of Γ. We may assume without loss of generality that an ordered subset of vertices in the graph Γ is W=1,2,3,…,k. Hence, VΓ−W=k+1,k+2,…,n. On the contrary, by proof of Proposition 3.2 in [27], we know that for every vertex x in Γ, there is exactly one y in Γ such that x−1y=k+1, that is, dx,y=2. Hence, there are vertices k+2,k+3,…,n−1 in VΓ−W such that d1,k+2=2,d2,k+3=2,…,dk,n−1=2. Therefore, the metric representations of the vertices k+2,k+3,…,n−1∈VΓ−W with respect to W are the k-vectors rk+2W=2,1,1,…,1,rk+3W=1,2,1,…,1,…,rnW=1,1,1,…,2. Moreover, the metric representation of the vertices k+1,n∈VΓ−W with respect to W is the k-vector rk+1W=rnW=1,1,1,…,1. Thus, W is not a resolving set of Γ because the metric representation of the vertices k+1,n is the same as the k-vector.Case 2. Let W be a clique in the graph Γ such that x∈W and W=k. We know that there is exactly one y in VΓ−W such that x−1y=k+1, that is, dx,y=2. In the following, we show that an ordered subset W∪y of vertices in the graph Γ is not a resolving set of Γ. In this case, we may assume without loss of generality that an ordered subset of vertices in the graph Γ is W=1,2,…,k, and let x=1 and y=k+2. Therefore, the metric representation of the vertices k+1,n∈VΓ−W∪y with respect to W∪y is the k+1-vector rk+1W=rnW=1,1,1,…,1. Thus, W∪y is not a resolving set of Γ.Case 3. Now, let W be a clique in the graph Γ such that W=k+1. We show that W is a resolving set of Γ. We may assume without loss of generality that an ordered subset of vertices in the graph Γ is W=1,2,3,…,k,k+1. Hence, VΓ−W=k+2,k+3,…,n. Therefore, the metric representations of the vertices k+2,k+3,…,n∈VΓ−W with respect to W are the k+1-vectors rk+2W=2,1,1,…,1,rk+3W=1,2,1,…,1,…,rnW=1,1,1,…,2. Thus, all the vertices of VΓ−W have different representations with respect to W. This implies that W is a resolving set of Γ. Moreover, the metric dimension of βΓ≤k+1 because Γ is a vertex transitive graph.Case 4. In particular, let W be a clique in the graph Γ such that W=k+1. We show that for each x∈VΓ−W, an ordered subset W∪x of vertices in the graph Γ is also a resolving set of Γ. We may assume without loss of generality that an ordered subset of vertices in the graph Γ is W=1,2,3,…,k,k+1, and let x=k+2. So, W∪x=1,2,3,…,k+1,k+2. Hence, VΓ−W∪x=k+3,k+4,…,n. Therefore, the metric representations of the vertices k+3,k+4,…,n∈VΓ−W∪x, with respect to W∪x, are the k+2-vectors rk+3W=1,2,1,…,1,1,rk+4W=1,2,1,…,1,1,…,rnW=1,2,1,…,1,1. This implies that W∪x is also a resolving set of Γ.
From the above cases, we conclude that the minimum cardinality of a resolving set ofΓ is k+1. Moreover, it is well known that every Cayley graph is a vertex transitive. Hence, the cardinality of every minimal resolving set in Γ is k+1.Theorem 6.
LetΓ=Cayℤn,Sk be the Cayley graph on the cyclic group ℤnn≥8, where S1=1,n−1,…,Sk=Sk−1∪k,n−k are the inverse closed subsets of ℤn−0 for any k∈ℕ, 1≤k≤n/2−1. If n is an even integer and k=n/2−1, then the cardinality of the minimum doubly resolving set of Γ is k+1.Proof.
In this theorem, letVΓ=v1,v2,…,vn, where vi=i for 1≤i≤n. We know that the ordered subset Z=1,2,3,…,k,k+1 of vertices in the graph Γ is a resolving set for Γ of size k+1. Also, by Theorem 5, the metric dimension of Γ is βΓ=k+1. Moreover, BΓ≤ψΓ. We show that the subset Z=1,2,3,…,k,k+1 of vertices in the graph Γ is a doubly resolving set of Γ. It is sufficient to show that for two vertices vi and vj of Γ, there are vertices x,y∈Z such that dvi,x−dvi,y≠dvj,x−dvj,y. Consider two vertices vi and vj of Γ. We may assume that i<j. In the following cases, we show that the cardinality of the minimum doubly resolving set of Γ is k+1.Case 1. If 1≤i<j≤k+1, then vi,vj∈Z. So, dvi,vj=1. We can assume that x=vi∈Z and y=vj∈Z. Hence, we have dvi,x−dvi,y≠dvj,x−dvj,y because dvi,x−dvj,y<0 and dvj,x−dvj,y>0.Case 2. Let 1≤i≤k+1<j≤n. Hence, vi∈Z and vj∉Z. Moreover, we know that dvi,vj=1 or 2. In the following, let dvi,vj=1. We may assume that vi=1 and vj=n. Hence, by taking x=vi∈Z and y=k+1∈Z, we have 0=0−0=dvi,x−dvi,y≠dvj,x−dvj,y=1−2=−1. Thus, the vertices x and y of Z doubly resolve vi,vj. Now, let dvi,vj=2. We may assume that vi=1 and vj=k+2. Hence, by taking x=1∈Z and y=2∈Z, we have −1=0−1=dvi,x−dvi,y≠dvj,x−dvj,y=2−1=1. Thus, the vertices x and y of Z doubly resolve vi,vj.Case 3. Finally, let 1<k+1<i<j≤n. Hence, vi∉Z and vj∉Z. Also, we know that dvi,vj=1. On the conrary, by proof of Proposition 3.2 in [27], we know that for every vertex vi∈VΓ−Z, there is exactly one x∈Z such that dvi,x=2. Also, for every vertex vj∈VΓ−Z, there is exactly one y∈Z such that dvj,y=2. Hence, 1=2−1=dvi,x−dvi,y≠dvj,x−dvj,y=1−2=−1. Thus, the vertices x and y of Z doubly resolve vi,vj.
From the above cases, we conclude that the minimum cardinality of a doubly resolving set ofΓ is k+1.Theorem 7.
LetΓ=Cayℤn,Sk be the Cayley graph on the cyclic group ℤnn≥8, where S1=1,n−1,…,Sk=Sk−1∪k,n−k are the inverse closed subsets of ℤn−0 for any k∈ℕ, 1≤k≤n/2−1. If n is an even integer and k=n/2−1, then the strong metric dimension of Γ is k+1.Proof.
In this theorem, letVΓ=v1,v2,…,vn, where vi=i for 1≤i≤n. We know that the ordered subset N=1,2,3,…,k,k+1 of vertices in the graph Γ is a resolving set for Γ of size k+1. Also, by Theorem 5, the metric dimension of Γ is βΓ=k+1. Moreover, BΓ≤sdimΓ. We show that the subset N=1,2,3,…,k,k+1 of vertices in the graph Γ is a strong resolving set of Γ. Consider two vertices vi and vj of Γ. Assume that i<j. It is sufficient to prove that there exists a vertex w∈N such that vi belongs to a shortest vj−w path or vj belongs to a shortest vi−w path. Let 1<k+1<i<j≤n. Hence, vi∉N and vj∉N. Moreover, we have dvi,vj=1. On the contrary, by proof of Proposition 3.2 in [27], we know that for every vertex vi∈VΓ−N, there is exactly one w∈N such that vi−1w=k+1, indeed dvi,w=2. Hence, dvj,w=1. So, dvi,w=dvi,vj+dvj,w, that is, vertex vj belongs to a shortest vi−w path, and hence w strongly resolves vertices vi and vj. Also, for vi∈N or vj∈N, vertex vi or vertex vj obviously strongly resolves pair vi,vj. Therefore, N is a strong resolving set. Thus, the minimum cardinality of a strong resolving set of Γ is k+1.Conclusion 1.
LetCPn≅CayD2n,Ω be the Cayley graph on the dihedral group D2n, where Ω is the inverse closed subset of D2n−1 which is defined already. Then, the minimum cardinality of resolving set, doubly resolving set, and strong resolving set of CPn is n.


## 4. Conclusion

In this paper, we determined the minimum cardinality of the resolving set, doubly resolving set, and strong resolving set of the jellyfish graphJFGn,m. In particular, it has been shown that the minimum cardinality of the resolving set, doubly resolving set, and strong resolving set of the cocktail party graph CPk+1 is k+1.



---

*Source: 9407456-2020-05-29.xml*