# Some Resolving Parameters in a Class of Cayley Graphs

Authors: Jia-Bao Liu; Ali Zafari
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Resolving parameters are a fundamental area of combinatorics with applications not only to many branches of combinatorics but also to other sciences. In this study, we construct a class of Toeplitz graphs and will be denoted byT2nW so that they are Cayley graphs. First, we review some of the features of this class of graphs. In fact, this class of graphs is vertex transitive, and by calculating the spectrum of the adjacency matrix related with them, we show that this class of graphs cannot be edge transitive. Moreover, we show that this class of graphs cannot be distance regular, and because of the difficulty of the computing resolving parameters of a class of graphs which are not distance regular, we regard this as justification for our focus on some resolving parameters. In particular, we determine the minimal resolving set, doubly resolving set, and strong metric dimension for this class of graphs.


---

## Body

## 1. Introduction

The graphs in this paper are simple, undirected, and connected. An automorphism of a graphΓ is a permutation φ of the vertex set of Γ with the property that, for any vertices x and y, we have x is adjacent to y in Γ if and only if φx is adjacent to φy in Γ. The set of all automorphisms of a graph Γ, with the operation of composition of permutations, is a permutation group on VΓ and a subgroup of the symmetric group on VΓ. This is the automorphism group of Γ, denoted by AutΓ. Suppose Γ1 and Γ2 are two graphs. If there is a bijection, say φ, from VΓ1 to VΓ2 so that x is adjacent to y in Γ1 if and only if φx is adjacent to φy in Γ2, then we say that Γ1 is isomorphic to Γ2. If we consider a graph Γ as a network, then the network stability is very important to us, and especially, if graph Γ is vertex transitive, that is, AutΓ acts transitively on VΓ, then the cost of studying the network will be very low, and hence, the network will be more stable. Consider a finite group G, and suppose Q is a subset of G so that it is closed under taking inverses and does not contain the identity; then, the Cayley graph Γ=CayG,Q has vertex set G and edge set EΓ=x,yx−1y∈Q. Thus, the studying of Cayley graphs is very useful because every Cayley graph is vertex transitive [1]. The distance between any pair u,v∈VΓ of vertices of Γ is the length of geodesic between u and v, denoted by dΓu,v or simply du,v. A vertex x∈VΓ is said to resolve a pair u,v∈VΓ if du,x≠dv,x. Resolving parameters are a fundamental area of combinatorics with applications not only to many branches of combinatorics but also to other sciences. For an arranged subset R=r1,r2,...,rm of vertices in a connected graph Γ, the metric representation of a vertex v in Γ is the m-vector rv|R=dv,r1,dv,r2,...,dv,rm relative to R. Also, the subset R is considered as the resolving set for Γ if any pair of vertices of Γ is distinguished by some vertices of R. A resolving set with least number of vertices is referred as metric basis for Γ and the cardinality of such resolving set is known as metric dimension denoted by βΓ. 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. The concept of the metric dimension in algebraic graph theory dates back to the 1970s. It was defined independently by Harary and Melter [2] and by Slater [3]. In recent years, a considerable literature has developed [4]. This concept has different applications in the areas of network discovery and verification [5]. For more details, see [6–9]. An (n x n) matrix T=tij is called a Toeplitz matrix if tij=ti+1,j+1 for each i,j=1,...,n−1, see [10]. In fact, a Toeplitz matrix is a square matrix so that entries in every diagonal parallel to the main diagonal are equal, and hence, a Toeplitz matrix is determined by its first row and column. A simple undirected graph Γ with vertex set 1,...,n and its adjacency matrix T=tij is called a Toeplitz graph if T is the Toeplitz matrix. In this paper, we consider a class of Toeplitz graphs will be denoted by T2nW so that they are Cayley graphs as follows.Letn be a fixed even integer is greater than or equal 4; also, let 2n=1,2,...,2n and x2n=x1,x2,...,x2n be corresponding sets so that xi=i. Hence, we say that xi<xj if i<j. Now, let W1=x1,x3,...,x2n−1 and W2=xn be subsets of the set x2n, and let W=W1∪W2=x1,x3,...,xn,...,x2n−1 be a refinement of union of the two sets W1 and W2 so that 1=x1<x3<...<xn<...<x2n−1. We can see that a graph with 2n vertices so that the vertices are labelled by the set 1,2,...,2n and the edge set:(1)iji,j∈2n,j−i=xtforsomext∈W,which is Toeplitz graph T2nW. For more result of the Toeplitz graphs, see [11, 12]. Figure 1 shows the Toeplitz graph T81,3,4,5,7.In particular, we can verify that the Toeplitz graphT2nW which is defined already is isomorphic to the Cayley graph Λ=CayD2n,Ψ, where(2)D2n=<a,b|an=b2=1,ba=an−1b>is the dihedral group of order 2n, and Ψ=ab,a2b,...,an−1b,b∪an/2 is an inverse closed subset of D2n−1. Thus, the Toeplitz graph T2nW is a vertex transitive. Also, for convenience, we can use the symbols in the Cayley graph Λ=CayD2n,Ψ, instead of the symbols in the Toeplitz graph T2nW. Some metrics for a class of distance regular graphs is computed in [13, 14]. On the contrary, because of the difficulty of the computing resolving parameters of a class of graphs which are not distance regular, we regard this as justification for our focus on some resolving parameters in the Cayley graph Λ=CayD2n,Ψ. The important results of this study are presented in Sections 3.1 and 3.2. In Section 3.1, first, we will be determining the automorphism group of the Cayley graph Λ=CayD2n,Ψ; also, we will show that the Cayley graph Λ=CayD2n,Ψ cannot be distance regular. In particular, we will prove that the Cayley graph Λ=CayD2n,Ψ cannot be edge transitive. Moreover, in Section 3.2, we will be computing some resolving parameters for this class of Cayley graphs.Figure 1
The Toeplitz graphT8(1, 3, 4, 5, 7).


## 2. Definitions and Preliminaries

Definition 1 (see [15]).
A graphΓ is edge transitive if its automorphism group acts transitively on EΓ.Definition 2 (see [15]).
A graphΓis 1-transitive or symmetric if its automorphism group acts transitively on the set of paths of length 1 or 1-arcs.Proposition 1 (see [15]).
LetΓbe a symmetric graph of valencyk, and letλbe a simple eigenvalue ofΓ; then,λ=±k.Definition 3 (see [16]).
Suppose thatΓis a regular graph of valencykand for any two verticesuandvinΓ; ifdu,v=r, then we haveΓr+1v∩Γ1u=br, andΓr−1v∩Γ1u=cr0≤r≤d. Then, we say thatΓis a distance regular graph.Proposition 2 (see [16]).
IfΓis a distance regular graph with diameterd, thenΓhas exactlyd+1distinct eigenvalues.Definition 4 (see [17]).
SupposeΓis a graph of order at least 2; verticesx,y∈VΓare said to doubly resolve verticesu,v∈VΓifdu,x−du,y≠dv,x−dv,y. A setS=s1,s2,...,slof vertices ofΓis a doubly resolving set ofΓif every two distinct vertices ofΓare doubly resolved by some two vertices ofS. A doubly resolving set with minimum cardinality is called the minimal doubly resolving set. This minimum cardinality is denoted byψΓ.Definition 5 (see [18]).
LetΓbe a graph. A vertexwofΓstrongly resolves two verticesuandvofΓifubelongs to a shortestv−wpath orvbelongs to a shortestu−wpath. A setS=s1,s2,...,smof vertices ofΓis a strong resolving set ofΓif every two distinct vertices ofΓare strongly resolved by some vertex ofS. The strong metric dimension of a graphΓis the cardinality of smallest strong resolving set ofΓand denoted bysdimΓ.


## 3. Main Results

### 3.1. Some of the Features of the Cayley GraphCayD2n,Ψ

In this section, we review some of the features of the Cayley graphCayD2n,Ψ. It is well known that the spectrum of a graph is the spectrum of the adjacency matrix related with it, that is, its set of eigenvalues together with their multiplicities. If all the eigenvalues of the adjacency matrix of a graph are integers, in this case, the graph related with it is called an integral graph, see [19]. As we shall see, the theory of integral graphs has connections to some parts of graph theory, edge transitivity, and symmetric graph. In the next theorem, we obtain the automorphism group of the Cayley graph CayD2n,Ψ by applications of wreath product in graph theory; for more details of the wreath product, see [20].Proposition 3.
Letnbe an even integer greater than or equal4, andΛ=CayD2n,Ψbe a Cayley graph on the dihedral groupD2n, whereΨis defined already. Ifk=n/2−1, thenAutΛ≅Z2wrISymk+1wrJSym2, whereI=1,...,k+1andJ=1,2.Proof.
We can see that the complement ofΛ, denoted by Λ¯, is isomorphic to the disjoint union of 2 copies of cocktail party graph CPn/2, and we can show that CPn/2 is isomorphic to the CayZn,Sk, where Zn is the cyclic group of order n and Sk=1,n−1,2,n−2,...,k,n−k, see Proposition 3.2 of [21]. Hence, given by the above discussion and the theorem in [22], we have AutΛ¯≅AutCPn/2wrISym2=Z2wrISymk+1wrJSym2. In particular, we have AutΛ¯=AutΛ because a simple undirected graph and its complement have the same automorphism group.Proposition 4.
Letnbe an even integer greater than or equal4, andΛ=CayD2n,Ψbe a Cayley graph on the dihedral groupD2n, whereΨis defined already; then,Λcannot be a distance regular graph.Proof.
It is not hard to see that the diameter ofΛ is 2 and Λ is not a bipartite graph, because an/2∈Ψ. Now, by a similar way, which is done in proof of Proposition 11 in [23], we can show that the adjacency matrix spectrum of Λ is n+1,1−n,1n−2,−1n, where the superscripts give the multiplicities of eigenvalues with multiplicity greater than one. Hence, Λ has exactly four distinct eigenvalues. Moreover, based on Proposition 2, we know that if Λ is a distance regular graph with diameter d, then Λ has exactly d+1 distinct eigenvalues. Thus, Λ cannot be a distance regular graph.Proposition 5.
Letnbe an even integer greater than or equal4andΛ=CayD2n,Ψbe a Cayley graph on the dihedral groupD2n, whereΨis defined already; then,Λcannot be an edge transitive graph.Proof.
By contradiction, supposeΛ is an edge transitive graph. It is well known that a connected graph that is edge transitive and vertex transitive need not be 1-transitive. In particular, in p.59, 7.53 of [24], Tutte proved that if a connected graph, regular of odd valency, is both vertex and edge transitive, then it is 1-transitive. Thus, if Λ is a edge transitive graph, then it must be Λ is a 1-transitive graph because it is vertex transitive of odd valency n+1. On the contrary, based on Proposition 1, if λ is a simple eigenvalue of a 1-transitive graph Λ, then λ=±n+1, which is not the case, see Proposition 4. This contradiction shows that Λ cannot be an edge transitive graph.


### 3.2. Metric Dimension, Minimal Doubly Resolving set, and Strong Resolving Set of the Cayley GraphCayD2n,Ψ

Theorem 1.
Ifnis an even integer greater than or equal4andΛ=CayD2n,Ψis a Cayley graph on the dihedral groupD2n, whereΨis defined already, then the metric dimension ofΛisn.Proof.
LetVΛ=V1∪V2, where V1=a,a2,...,an and V2=ab,a2b,...,anb. For every pair of distinct vertices x,y∈VΛ, the length of a shortest path from x to y is dx,y=1 or 2 because the diameter of Λ is 2. In particular, if R is an arranged subset of V1 or V2 in graph Λ such that R≤n, then we can show that R is not a resolving set of Λ. Let R=R1∪R2 be an arranged subset of vertices in graph Λ such that R1 is a subset of V1, R2 is a subset of V2, and R1∪R2=n. In the following cases, we can be concluded that the metric dimension of Λ is n.Case 1: ifR1≠R2, then we can assume that R1<R2. Hence, there is a pair of distinct vertices u1,u2∈VΛ−R, such that u1,u2∈V1−R1, and a shortest path from u1 to u2 is du1,u2=1. Therefore, the metric representation of the vertices u1,u2∈VΛ−R is the same as n-vector, relative to R. Thus, R is not a resolving set of Λ.Case 2: ifR1=R2 and there are vertices x,y∈R1, such that x is adjacent to y in Λ, then there are vertices u,v∈V1−R1 such that u is adjacent to v in Λ. Therefore, the metric representation of the vertices u,v∈VΛ−R is the same as n-vector, relative to R. Thus, R is not a resolving set of Λ.Case 3: now, letR1=R2, and suppose that, for all the vertices x,y in R1, we have x is not adjacent to y in Λ, that is, dx,y=2. Also, for all the vertices u,v in R2, we have u is not adjacent to v in Λ, that is, du,v=2. We may assume that R1=a,a2,...,an/2 and R2=ab,a2b,...,an/2b. So, we can assume that an arranged subset R of vertices in graph Λ is R=a,a2,...,an/2;ab,a2b,...,an/2b. Hence, VΛ−R=an+2i/2,...,an;an+2i/2b,...,anb, for 1≤i≤n/2.
Therefore, the metric representations of the verticesan+2/2,an+4/2,...,an;an+2/2b,an+4/2b,...,anb∈VΛ−R relative to R are the n-vectors:(3)ran+2/2|R=1,2,2,...,2;1,...,1,ran+4/2|R=2,1,2,...,2;1,...,1,…,ran|R=2,2,...,1;1,1,...1and ran+2/2b|R=1,...,1;1,2,2,...,2, ran+4/2b|R=1,...,1;2,1,2,...,2,...,ranb|R=1,1,...1;2,2,...,1. Thus, all the vertices in VΛ−R have different representations relative to R. This implies that R is a resolving set of Λ.Theorem 2.
Ifnis an even integer greater than or equal4andΛ=CayD2n,Ψis a Cayley graph on the dihedral groupD2n, whereΨis defined already, then the cardinality of minimum doubly resolving set ofΛisn.Proof.
By the previous theorem, we know that the arranged subsetR=a,a2,...,;ab,a2b,...,an/2b of vertices in the graph Λ is a resolving set for Λ. We show that the subset R is a doubly resolving set of Λ. It is sufficient to show that, for two vertices u and v in graph Λ, there are vertices x,y∈R such that du,x−du,y≠dv,x−dv,y. Consider two vertices u and v of Λ. By the following cases, we can be concluded that the minimum cardinality of a doubly resolving set of Λ is n.Case 1: consider a pair of distinct verticesu,v∈Λ such that u,v∈R. Then, the length of a shortest path from u to v is du,v=1 or 2. Let uandv be two vertices in R such that a shortest path from u to v in graph Λ is du,v=1. We may assume that u=a and v=ab. Hence, by taking x=a∈R and y=an/2∈R, we have −2=0−2=du,x−du,y≠dv,x−dv,y=1−1=0. Therefore, the vertices x and y of R doubly resolve u,v. Now, let u,v be two vertices in R such that a shortest path from u to v in graph Λ is du,v=2. We may assume that u=a and v=an/2. Hence, by taking x=a∈R and y=ab∈R, we have −1=0−1=du,x−du,y≠dv,x−dv,y=2−1=1. Therefore, the vertices x and y of R doubly resolve u,v.Case 2: consider a pair of distinct verticesu,v∈Λ such that u∈R and v∉R. Then, the length of a shortest path from u to v is du,v=1 or 2. Suppose a pair of distinct vertices u∈R and v∉R are adjacent in graph Λ, that is, du,v=1. We may assume that u=a and v=an+2/2. Hence, by taking x=a∈R and y=ab∈R, we have −1=0−1=du,x−du,y≠dv,x−dv,y=1−1=0. Therefore, the vertices x and y of R doubly resolve u,v. Now, suppose a pair of distinct vertices u∈R and v∉R are not adjacent in graph Λ, that is, du,v=2. We may assume that u=a and v=an. Hence, by taking x=a∈R and y=ab∈R, we have −1=0−1=du,x−du,y≠dv,x−dv,y=2−1=1. Therefore, the vertices x and y of R doubly resolve u,v.Case 3: consider a pair of distinct verticesu,v∈Λ such that u∉R and v∉R. Then, the length of a shortest path from u to v is du,v=1 or 2. We can show that the subset R of vertices in graph Λ is a doubly resolving set of Λ. Because by Theorem 1, we can be concluded that VΛ−R is also a resolving set of Λ.Lemma 1.
Ifnis an even integer greater than or equal4andΛ=CayD2n,Ψis a Cayley graph on the dihedral groupD2n, whereΨis defined already, then the subsetR=a,a2,...,an/2;ab,a2b,...,an/2bof vertices in graphΛis not a strong resolving set ofΛ.Proof.
We know that the arranged subsetR=a,a2,...,an/2;ab,a2b,...,an/2b of vertices in graph Λ is a resolving set for Λ of size n. Now, let VΛ=V1∪V2, where V1=a,a2,...,an, V2=ab,a2b,...,anb, and R=R1∪R2, where R1=a,a2,...,an/2 is a subset of V1 and R2=ab,a2b,...,an/2b is a subset of V2. Consider two vertices u,v in Λ such that u,v∈V1−R1 and u is not adjacent to v in Λ, that is, du,v=2. In the following cases, we show that there is not w∈R such that w is strongly resolve vertices u and v. For every vertex w∈R, we have w∈R1 or w∈R2.Case 1: ifw∈R1, then the length of a shortest path from u to w is du,w=1 or 2 and length of a shortest path from v to w is dv,w=1 or 2. Note that, if du,w=1, then dv,w=2. Therefore, w is not strongly resolve vertices u and v. In particular, if du,w=2, then dv,w=1 or 2, and hence, w is not strongly resolve vertices u and v because du,v=2.Case 2: ifw∈R2, then the length of a shortest path from u to w is du,w=1 and length of a shortest path from v to w is dv,w=1. Therefore, w is not strongly resolve vertices u and v.Theorem 3.
Ifnis an even integer greater than or equal4andΛ=CayD2n,Ψis a Cayley graph on the dihedral groupD2n, whereΨis defined already, then the strong metric dimension ofΛis2n−2.Proof.
LetVΛ=V1∪V2, where V1=a,a2,...,an and V2=ab,a2b,...,anb. It is not hard to see that if n≥4, then the size of largest clique in the graph Λ is 4. Moreover, we know that the subset N=an,an/2;anb,an/2b of vertices in Λ is a clique in the graph Λ. Now, let the subset S of vertices in Λ be S=VΛ−N. In the following cases, we show that the subset S of vertices in Λ is not a strong resolving set of Λ.Case 1: letu=an and v=an/2. We know that du,v=1 and u,v∈V1, and hence, for every w∈S such that w∈V2, we have du,w=1 and dv,w=1. Thus, w is not strongly resolve vertices u and v.Case 2: now, letu=an and v=an/2. We know that du,v=1 and u,v∈V1, and hence, for every w∈S such that w∈V1, we have du,w=2 and dv,w=2. Thus, w is not strongly resolve vertices u and v.
Therefore, the subsetS of the vertices in graph Λ is not a strong resolving set of Λ. From the above cases, we can be concluded that the minimum cardinality of a strong resolving set for Λ must be 2n−2.


## 3.1. Some of the Features of the Cayley GraphCayD2n,Ψ

In this section, we review some of the features of the Cayley graphCayD2n,Ψ. It is well known that the spectrum of a graph is the spectrum of the adjacency matrix related with it, that is, its set of eigenvalues together with their multiplicities. If all the eigenvalues of the adjacency matrix of a graph are integers, in this case, the graph related with it is called an integral graph, see [19]. As we shall see, the theory of integral graphs has connections to some parts of graph theory, edge transitivity, and symmetric graph. In the next theorem, we obtain the automorphism group of the Cayley graph CayD2n,Ψ by applications of wreath product in graph theory; for more details of the wreath product, see [20].Proposition 3.
Letnbe an even integer greater than or equal4, andΛ=CayD2n,Ψbe a Cayley graph on the dihedral groupD2n, whereΨis defined already. Ifk=n/2−1, thenAutΛ≅Z2wrISymk+1wrJSym2, whereI=1,...,k+1andJ=1,2.Proof.
We can see that the complement ofΛ, denoted by Λ¯, is isomorphic to the disjoint union of 2 copies of cocktail party graph CPn/2, and we can show that CPn/2 is isomorphic to the CayZn,Sk, where Zn is the cyclic group of order n and Sk=1,n−1,2,n−2,...,k,n−k, see Proposition 3.2 of [21]. Hence, given by the above discussion and the theorem in [22], we have AutΛ¯≅AutCPn/2wrISym2=Z2wrISymk+1wrJSym2. In particular, we have AutΛ¯=AutΛ because a simple undirected graph and its complement have the same automorphism group.Proposition 4.
Letnbe an even integer greater than or equal4, andΛ=CayD2n,Ψbe a Cayley graph on the dihedral groupD2n, whereΨis defined already; then,Λcannot be a distance regular graph.Proof.
It is not hard to see that the diameter ofΛ is 2 and Λ is not a bipartite graph, because an/2∈Ψ. Now, by a similar way, which is done in proof of Proposition 11 in [23], we can show that the adjacency matrix spectrum of Λ is n+1,1−n,1n−2,−1n, where the superscripts give the multiplicities of eigenvalues with multiplicity greater than one. Hence, Λ has exactly four distinct eigenvalues. Moreover, based on Proposition 2, we know that if Λ is a distance regular graph with diameter d, then Λ has exactly d+1 distinct eigenvalues. Thus, Λ cannot be a distance regular graph.Proposition 5.
Letnbe an even integer greater than or equal4andΛ=CayD2n,Ψbe a Cayley graph on the dihedral groupD2n, whereΨis defined already; then,Λcannot be an edge transitive graph.Proof.
By contradiction, supposeΛ is an edge transitive graph. It is well known that a connected graph that is edge transitive and vertex transitive need not be 1-transitive. In particular, in p.59, 7.53 of [24], Tutte proved that if a connected graph, regular of odd valency, is both vertex and edge transitive, then it is 1-transitive. Thus, if Λ is a edge transitive graph, then it must be Λ is a 1-transitive graph because it is vertex transitive of odd valency n+1. On the contrary, based on Proposition 1, if λ is a simple eigenvalue of a 1-transitive graph Λ, then λ=±n+1, which is not the case, see Proposition 4. This contradiction shows that Λ cannot be an edge transitive graph.


## 3.2. Metric Dimension, Minimal Doubly Resolving set, and Strong Resolving Set of the Cayley GraphCayD2n,Ψ

Theorem 1.
Ifnis an even integer greater than or equal4andΛ=CayD2n,Ψis a Cayley graph on the dihedral groupD2n, whereΨis defined already, then the metric dimension ofΛisn.Proof.
LetVΛ=V1∪V2, where V1=a,a2,...,an and V2=ab,a2b,...,anb. For every pair of distinct vertices x,y∈VΛ, the length of a shortest path from x to y is dx,y=1 or 2 because the diameter of Λ is 2. In particular, if R is an arranged subset of V1 or V2 in graph Λ such that R≤n, then we can show that R is not a resolving set of Λ. Let R=R1∪R2 be an arranged subset of vertices in graph Λ such that R1 is a subset of V1, R2 is a subset of V2, and R1∪R2=n. In the following cases, we can be concluded that the metric dimension of Λ is n.Case 1: ifR1≠R2, then we can assume that R1<R2. Hence, there is a pair of distinct vertices u1,u2∈VΛ−R, such that u1,u2∈V1−R1, and a shortest path from u1 to u2 is du1,u2=1. Therefore, the metric representation of the vertices u1,u2∈VΛ−R is the same as n-vector, relative to R. Thus, R is not a resolving set of Λ.Case 2: ifR1=R2 and there are vertices x,y∈R1, such that x is adjacent to y in Λ, then there are vertices u,v∈V1−R1 such that u is adjacent to v in Λ. Therefore, the metric representation of the vertices u,v∈VΛ−R is the same as n-vector, relative to R. Thus, R is not a resolving set of Λ.Case 3: now, letR1=R2, and suppose that, for all the vertices x,y in R1, we have x is not adjacent to y in Λ, that is, dx,y=2. Also, for all the vertices u,v in R2, we have u is not adjacent to v in Λ, that is, du,v=2. We may assume that R1=a,a2,...,an/2 and R2=ab,a2b,...,an/2b. So, we can assume that an arranged subset R of vertices in graph Λ is R=a,a2,...,an/2;ab,a2b,...,an/2b. Hence, VΛ−R=an+2i/2,...,an;an+2i/2b,...,anb, for 1≤i≤n/2.
Therefore, the metric representations of the verticesan+2/2,an+4/2,...,an;an+2/2b,an+4/2b,...,anb∈VΛ−R relative to R are the n-vectors:(3)ran+2/2|R=1,2,2,...,2;1,...,1,ran+4/2|R=2,1,2,...,2;1,...,1,…,ran|R=2,2,...,1;1,1,...1and ran+2/2b|R=1,...,1;1,2,2,...,2, ran+4/2b|R=1,...,1;2,1,2,...,2,...,ranb|R=1,1,...1;2,2,...,1. Thus, all the vertices in VΛ−R have different representations relative to R. This implies that R is a resolving set of Λ.Theorem 2.
Ifnis an even integer greater than or equal4andΛ=CayD2n,Ψis a Cayley graph on the dihedral groupD2n, whereΨis defined already, then the cardinality of minimum doubly resolving set ofΛisn.Proof.
By the previous theorem, we know that the arranged subsetR=a,a2,...,;ab,a2b,...,an/2b of vertices in the graph Λ is a resolving set for Λ. We show that the subset R is a doubly resolving set of Λ. It is sufficient to show that, for two vertices u and v in graph Λ, there are vertices x,y∈R such that du,x−du,y≠dv,x−dv,y. Consider two vertices u and v of Λ. By the following cases, we can be concluded that the minimum cardinality of a doubly resolving set of Λ is n.Case 1: consider a pair of distinct verticesu,v∈Λ such that u,v∈R. Then, the length of a shortest path from u to v is du,v=1 or 2. Let uandv be two vertices in R such that a shortest path from u to v in graph Λ is du,v=1. We may assume that u=a and v=ab. Hence, by taking x=a∈R and y=an/2∈R, we have −2=0−2=du,x−du,y≠dv,x−dv,y=1−1=0. Therefore, the vertices x and y of R doubly resolve u,v. Now, let u,v be two vertices in R such that a shortest path from u to v in graph Λ is du,v=2. We may assume that u=a and v=an/2. Hence, by taking x=a∈R and y=ab∈R, we have −1=0−1=du,x−du,y≠dv,x−dv,y=2−1=1. Therefore, the vertices x and y of R doubly resolve u,v.Case 2: consider a pair of distinct verticesu,v∈Λ such that u∈R and v∉R. Then, the length of a shortest path from u to v is du,v=1 or 2. Suppose a pair of distinct vertices u∈R and v∉R are adjacent in graph Λ, that is, du,v=1. We may assume that u=a and v=an+2/2. Hence, by taking x=a∈R and y=ab∈R, we have −1=0−1=du,x−du,y≠dv,x−dv,y=1−1=0. Therefore, the vertices x and y of R doubly resolve u,v. Now, suppose a pair of distinct vertices u∈R and v∉R are not adjacent in graph Λ, that is, du,v=2. We may assume that u=a and v=an. Hence, by taking x=a∈R and y=ab∈R, we have −1=0−1=du,x−du,y≠dv,x−dv,y=2−1=1. Therefore, the vertices x and y of R doubly resolve u,v.Case 3: consider a pair of distinct verticesu,v∈Λ such that u∉R and v∉R. Then, the length of a shortest path from u to v is du,v=1 or 2. We can show that the subset R of vertices in graph Λ is a doubly resolving set of Λ. Because by Theorem 1, we can be concluded that VΛ−R is also a resolving set of Λ.Lemma 1.
Ifnis an even integer greater than or equal4andΛ=CayD2n,Ψis a Cayley graph on the dihedral groupD2n, whereΨis defined already, then the subsetR=a,a2,...,an/2;ab,a2b,...,an/2bof vertices in graphΛis not a strong resolving set ofΛ.Proof.
We know that the arranged subsetR=a,a2,...,an/2;ab,a2b,...,an/2b of vertices in graph Λ is a resolving set for Λ of size n. Now, let VΛ=V1∪V2, where V1=a,a2,...,an, V2=ab,a2b,...,anb, and R=R1∪R2, where R1=a,a2,...,an/2 is a subset of V1 and R2=ab,a2b,...,an/2b is a subset of V2. Consider two vertices u,v in Λ such that u,v∈V1−R1 and u is not adjacent to v in Λ, that is, du,v=2. In the following cases, we show that there is not w∈R such that w is strongly resolve vertices u and v. For every vertex w∈R, we have w∈R1 or w∈R2.Case 1: ifw∈R1, then the length of a shortest path from u to w is du,w=1 or 2 and length of a shortest path from v to w is dv,w=1 or 2. Note that, if du,w=1, then dv,w=2. Therefore, w is not strongly resolve vertices u and v. In particular, if du,w=2, then dv,w=1 or 2, and hence, w is not strongly resolve vertices u and v because du,v=2.Case 2: ifw∈R2, then the length of a shortest path from u to w is du,w=1 and length of a shortest path from v to w is dv,w=1. Therefore, w is not strongly resolve vertices u and v.Theorem 3.
Ifnis an even integer greater than or equal4andΛ=CayD2n,Ψis a Cayley graph on the dihedral groupD2n, whereΨis defined already, then the strong metric dimension ofΛis2n−2.Proof.
LetVΛ=V1∪V2, where V1=a,a2,...,an and V2=ab,a2b,...,anb. It is not hard to see that if n≥4, then the size of largest clique in the graph Λ is 4. Moreover, we know that the subset N=an,an/2;anb,an/2b of vertices in Λ is a clique in the graph Λ. Now, let the subset S of vertices in Λ be S=VΛ−N. In the following cases, we show that the subset S of vertices in Λ is not a strong resolving set of Λ.Case 1: letu=an and v=an/2. We know that du,v=1 and u,v∈V1, and hence, for every w∈S such that w∈V2, we have du,w=1 and dv,w=1. Thus, w is not strongly resolve vertices u and v.Case 2: now, letu=an and v=an/2. We know that du,v=1 and u,v∈V1, and hence, for every w∈S such that w∈V1, we have du,w=2 and dv,w=2. Thus, w is not strongly resolve vertices u and v.
Therefore, the subsetS of the vertices in graph Λ is not a strong resolving set of Λ. From the above cases, we can be concluded that the minimum cardinality of a strong resolving set for Λ must be 2n−2.


## 4. Conclusion

Computing resolving parameters of a graph is an NP-hard problem. In this study, we considered a class of Toeplitz graphs and we denoted byT2nW so that they are isomorphic to the Cayley graph Λ=CayD2n,Ψ, which is defined already. In fact, this class of graphs is vertex transitive, and by calculating the spectrum of the adjacency matrix related with them, we showed that this class of graphs cannot be edge transitive. Also, we proved that this class of graphs cannot be distance regular, and because of the difficulty of the computing resolving parameters of a class of graphs which are not distance regular, we regarded this as justification for our focus on some resolving parameters. In particular, we determined the minimal resolving set, doubly resolving set, and strong metric dimension for this class of graphs.



---

*Source: 9444579-2022-01-17.xml*