# The Metric Dimension of Some Generalized Petersen Graphs

Authors: Zehui Shao; S. M. Sheikholeslami; Pu Wu; Jia-Biao Liu
Journal: Discrete Dynamics in Nature and Society
 (2018)

---

## Abstract

The distanced(u,v) between two distinct vertices u and v in a graph G is the length of a shortest (u,v)-path in G. For an ordered subset W={w1,w2,…,wk} of vertices and a vertex v in G, the code of v with respect to W is the ordered k-tuple cW(v)=(d(v,w1),d(v,w2),…,d(v,wk)). The set W is a resolving set for G if every two vertices of G have distinct codes. Themetric dimension of G is the minimum cardinality of a resolving set of G. In this paper, we first extend the results of the metric dimension of P(n,3) and P(n,4) and study bounds on the metric dimension of the families of the generalized Petersen graphs P(2k,k) and P(3k,k). The obtained results mean that these families of graphs have constant metric dimension.


---

## Body

## 1. Introduction

LetG be a connected graph with vertex set V=V(G) and edge set E=E(G). The distance between two distinct vertices u and v in G, denoted by d(u,v), is the length of a shortest (u,v)-path. For positive integer k and a vertex v∈V(G), the k-neighborhood of v is the set Nk(v)={u∣d(u,v)=k}. For an ordered subset W={w1,w2,…,wk} of vertices and a vertex v in G, the code of v with respect to W is the ordered k-tuple cW(v)=(d(v,w1),d(v,w2),…,d(v,wk)). The set W is a resolving set [1] (or locating set [2]) for G if every two vertices of G have distinct codes. Themetric dimension of G, denoted by dim⁡(G), is the minimum cardinality of a resolving set of G. A resolving set containing a minimum number of vertices is called a basis for G [3].Graph theory is a powerful tool to model the real world applications such as physical-chemical property testing [4, 5]. Motivated by the problem of uniquely determining the location of an intruder in a network, the concept of metric dimension of a graph was introduced by Slater in [6], where the metric generators were called locating sets. The concept of metric dimension of a graph was also introduced by Harary and Melter in [1], where metric generators were called resolving sets. Applications of this invariant to the navigation of robots in networks are discussed in [7] and applications to chemistry in [8, 9]. This graph parameter was studied further in a number of other papers including, for instance, [10–19]. Several variations of metric generators including resolving dominating sets [20], independent resolving sets [21], local metric sets [22], strong resolving sets [23], mixed metric dimension [24], and k-metric dimension [25] have since been introduced and studied.We observe from definition that the property of a given setW of vertices of a graph G to be a resolving set of G can be tested by investigating the vertices of V(G)∖W because every vertex w∈W is the unique vertex of G whose distance from w is 0. If d(x,t)≠d(y,t), we say that vertex t distinguishes vertices x and y.For natural numbersn and k, where n>2k, a generalized Petersen graph P(n,k) is a graph with vertex set U∪V, where U={u1,u2,…,un} and V={v1,v2,…,vn}, and edge set E1∪E2∪E3, where E1={uiui+1∣1≤i≤n, E2={uivi∣1≤i≤n}, and E3={vivi+k∣1≤i≤n}, where subscripts are taken modulo n (see [2, 26]). We observe that, for each 1≤i≤n,(1)N2ui=ui-2,ui+2,vi-1,vi+1,vi-k,vi+k,(2)N2vi=ui-1,ui+1,vi-2k,vi+2k,ui-k,ui+k,(3)N3ui=ui-3,ui+3,vi-2,vi+2,vi+1-k,vi+k+1,vi-1-k,vi+k-1,vi-2k,vi+2k,ui-k,ui+k,(4)N3vi=ui-2,ui+2,vi+1,vi-1,ui+1+k,ui+k-1,ui-1-k,ui-k+1,ui-2k,ui+2k,vi-3k,vi+3k.If k=3 and n≥16, then clearly |N2(x)|≥6 and |N3(x)|≥8 for each x∈V(P(n,k)).Javaid et al. [27] proved that dim(P(n,2))=3 for n≥5 and posed the following problem.Problem 1.
Is the generalized Petersen graphsP(n,k), for n≥7 and 3≤k≤⌊(n-1)/2⌋, a family of graphs with constant metric dimension?Some partial answers are given to aforementioned problem as follows.Theorem 2 (see [28]).
Forn≥3, dim⁡(P(n,1))=2 when n≡1(mod2) and dim⁡(P(n,1))=3 if n≡0(mod2).Theorem 3 (see [29]).
(5)dim⁡Pn,3=4,ifn≡0mod6andn≥24;=3,ifn≡1mod6andn≥25;≤5,ifn≡2mod6andn≥8;≤4,ifn≡3,4,5mod6andn≥17;In [30, 31], it was showed thatTheorem 4.
(i)dim⁡(P(2k+1,k))=3 if k≥2.
(ii)(6)dimP2k,k-1=3,ifk=2ork≥3isodd;4,ifk≥4isodd.In [32], it was proved thatTheorem 5.
Forn≥4, dim⁡(P(n,4))=3 if n≡0(mod4), dim⁡(P(n,4))=4 when n=4k+3 for even k, and dim⁡(P(n,4))≤4 otherwise.In this paper, we first extend the results of Theorems3 and 5.We make use of the following result in this paper.Theorem 6 (see [7]).
IfG is a graph of order n, diameter d and metric dimension k, then n<dk+k.


## 2. Main Results

Next result extends Theorem3.Lemma 7.
LetG be a connected graph and let N2v≥6 or N3v≥8 for each v∈V(G). Then dim⁡(G)≥3.Proof.
Clearly, for anyw,v∈V(G) and for any z∈Nk(w) we have(7)dv,w-k≤dv,z≤dv,w+k.Suppose, to the contrary, that S={w1,w2} is a resolving set of G. Since N2w1≥6 or N3w1≥8, we deduce from (7) and the Pigeonhole principle that there exist two vertices x1,x2∈N2(w1) such that d(x1,w2)=d(x2,w2), a contradiction.Theorem 8.
Forn≥7,
(i) Ifn∈{9,10,11,15} or n≡1(mod6), then dim⁡(P(n,3))=3.
(ii) Ifn=20, then dim⁡(P(n,3))=5.Proof.
Ifn=9, then let W={u1,u7,v5}. The code of v with respect to W in P(9,3) is presented in Table 1 yielding dim⁡(P(9,3))≤3.
Now, we show thatdim(P(9,3))≥3. Suppose, to the contrary, there exists a resolving set W={x,y} of P(9,3). First let W∩U≠∅. We may assume w.l.o.g. that x∈W∩U. By (1), we have N2x=6. For each u∈N2(x), we have d(y,x)-2≤d(y,u)≤d(y,x)+2. By the Pigeonhole principle, we have d(y,u)=d(y,v) for some u,v∈N2(x) and this leads to a contradiction. Now let W∩U=∅. Assume without loss of generality that x=v1 and y=vi for some i∈{2,3,4,5}. If i∈{2,3}, then (d(x,u4),d(y,u4))=(d(x,u9),d(y,u9)), and if i∈{4,5}, then (d(x,u7-i),d(y,u7-i))=(d(x,u9-i),(y,u9-i)), a contradiction. Thus, dim(P(9,3))≥3 and so dim⁡(P(9,3))=3.
Ifn=10, then let W={u1,v9,v10}. The code of v with respect to W in P(10,3) is presented in Table 2 showing that dim⁡(P(10,3))≤3.
Next, we show thatdim⁡(P(10,3))≥3. Suppose, to the contrary, there exists a resolving set W={x,y} of P(10,3). As above, we may assume that W∩U=∅. We may assume w.l.o.g. that x=v1 and y=vi for some i∈{2,3,…,6}. If i∈{2,4,6}, then (d(x,u3),d(y,u3))=(d(x,u5), d(y,u5)), and if i∈{3,5}, then we have (d(x,u2),d(y,u2))=(d(x,u4), d(y,u4)), a contradiction.
Ifn=11, then let W={u1,u5,v2}. The code of v with respect to W in P(11,3) is presented in Table 3 yielding dim⁡(P(11,3))≤3.
Sincediam(P(11,3))=4, we deduce from Theorem 6 that dim(P(11,3))≥3. Thus, dim(P(11,3))=3.
Ifn=15, then let W={u1,u3,v11}. The code of v with respect to W in P(15,3) is presented in Table 4 implying that dim⁡(P(15,3))≤3.
Sincediam(P(15,3))=5, it follows from Theorem 6 that dim⁡(P(15,3))≥3. Hence, dim⁡(P(15,3))=3.
Ifn=20, then let W={u1,u3,u11,v8,v10}. The code of v with respect to W in P(20,3) is presented in Table 5. This implies that dim⁡(P(20,3))≤5.
Analogous to the proof of the casen=9, we can obtain the desired lower bound with a more complicated analysis. Also it can be verified by computer search.
Ifn≤15, we can verify the results by computer. If n≥16 and n≡1(mod6), we have N2v=6 and |N3(v)|≥8 for any v∈P(n,3). Now by Lemma 7, we have dim⁡(P(n,3))≥3. Now, the proof is complete.Table 1
The codecW(v) of v with respect to W={u1,u7,v5} in P(9,3).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u 1 ( 0,3 , 3 ) u2 ( 1,4 , 2 ) u3 ( 2,4 , 3 ) u4 ( 3,3 , 2 ) u5 ( 4,2 , 1 ) u 6 (4,1,2) u7 ( 3,0 , 3 ) u8 ( 2,1 , 2 ) u9 ( 1,2 , 3 ) v1 ( 1,2 , 4 ) v 2 ( 2,3 , 1 ) v3 ( 3,3 , 4 ) v4 ( 2,2 , 3 ) v5 ( 3,3 , 0 ) v6 ( 3,2 , 3 ) v 7 ( 2,1 , 4 ) v8 ( 3,2 , 1 ) v9 ( 2,3 , 4 )Table 2
The codecW(v) of v with respect to W={u1,v9,v10} in P(10,3).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u1 (0,3,2) u 2 (1,2,3) u 3 (2,3,2) u 4 (3,4,3) u 5 (4,3,4) u6 (5,2,3) u 7 (4,3,2) u 8 (3,2,3) u 9 (2,1,2) u 10 (1,2,1) v1 (1,4,3) v 2 (2,1,4) v 3 (3,2,1) v 4 (2,5,2) v 5 (3,2,5) v6 (4,1,2) v 7 (3,4,1) v 8 (2,3,4) v 9 (3,0,3) v 10 (2,3,0)Table 3
The codecW(v) of v with respect to W={u1,u5,v2} in P(11,3).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u1 (0,4,2) u 2 (1,3,1) u 3 (2,2,2) u 4 (3,1,3) u 5 (4,0,2) u6 (4,1,3) u 7 (4,2,3) u 8 (4,3,3) u 9 (3,4,3) u 10 (2,4,2) u11 (1,4,3) v 1 (1,3,3) v 2 (2,2,0) v 3 (3,3,3) v 4 (2,2,3) v5 (3,1,1) v 6 (3,2,4) v 7 (3,3,2) v 8 (3,2,2) v 9 (2,3,4) v10 (3,3,1) v 11 (2,3,3)Table 4
The codecW(v) of v with respect to W={u1,u3,v11} in P(15,3).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u1 (0,2,4) u 2 (1,1,3) u 3 (2,0,4) u 4 (3,1,4) u 5 (4,2,3) u6 (5,3,4) u 7 (4,4,3) u 8 (5,5,2) u 9 (5,4,3) u 10 (4,5,2) u11 (5,5,1) u 12 (4,4,2) u 13 (3,5,3) u 14 (2,4,2) u 15 (1,3,3) v1 (1,3,5) v 2 (2,2,2) v 3 (3,1,5) v 4 (2,2,5) v 5 (3,3,2) v6 (4,2,5) v 7 (3,3,4) v 8 (4,4,1) v 9 (4,3,4) v 10 (3,4,3) v11 (4,4,0) v 12 (3,3,3) v 13 (2,4,4) v 14 (3,3,1) v 15 (2,2,4)Table 5
The codecW(v) of v with respect to W={u1,u3,u11,v8,v10} in P(20,3).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u1 (0,2,6,4,4) u 2 (1,1,5,3,5) u 3 (2,0,6,4,4) u 4 (3,1,5,3,3) u5 (4,2,4,2,4) u 6 (5,3,5,3,3) u 7 (4,4,4,2,2) u 8 (5,5,3,1,3) u9 (6,4,2,2,2) u 10 (5,5,1,3,1) u 11 (6,6,0,2,2) u 12 (5,5,1,3,3) u13 (6,6,2,4,2) u 14 (5,5,3,3,3) u 15 (4,6,4,4,4) u 16 (5,5,5,5,3) u17 (4,4,4,4,4) u 18 (3,5,5,5,5) u 19 (2,4,6,4,4) u 20 (1,3,5,5,5) v1 (1,3,5,5,3) v 2 (2,2,4,2,4) v 3 (3,1,5,5,5) v 4 (2,2,4,4,2) v5 (3,3,3,1,5) v 6 (4,2,4,4,4) v 7 (3,3,3,3,1) v 8 (4,4,2,0,4) v9 (5,3,3,3,3) v 10 (4,4,2,4,0) v 11 (5,5,1,1,3) v 12 (4,4,2,4,4) v13 (5,5,3,5,1) v 14 (4,4,2,2,4) v 15 (3,5,3,5,5) v 16 (4,4,4,4,2) v17 (3,3,3,3,5) v 18 (2,4,4,6,4) v 19 (3,3,5,3,3) v 20 (2,2,4,4,6)The following theorem extends the result of Theorem5.Theorem 9.
LetG be the graph G=P(n,4) with n≥9; then if n∈{9,10,11,13,17,21}orn≡0(mod4), then dim⁡(G)=3.Proof.
Ifn=9, let W={u1,v8,v9}. The code of v with respect to W in P(9,4) is presented in Table 6 showing that dim⁡(P(9,4))≤3.
Ifn=10, let W={u1,u5,v3}. The code of v with respect to W in P(10,4) is presented in Table 7 showing that dim⁡(P(10,4))≤3.
Note that the diameter ofP(10,4) is 4; by Theorem 6, we have dim⁡(P(10,4))≥3.
Ifn=11, let W={u1,v8,v11}. The code of v with respect to W in P(11,4) is presented in Table 8 showing that dim⁡(P(11,4))≤3.
Note that the diameter ofP(11,4) is 4; by Theorem 6, we have dim⁡(P(11,4))≥3.
Ifn=17, let W={u1,v14,v17}. The code of v with respect to W in P(17,4) is presented in Table 9 showing that dim⁡(P(17,4))≤3.
Note that the diameter ofP(17,4) is 5; by Theorem 6, we have dim⁡(P(17,4))≥3.
Ifn=21, let W={u1,u16,v14}. The code of v with respect to W in P(21,4) is presented in Table 10 showing that dim⁡(P(21,4))≤3.
Note that the diameter ofP(21,4) is 6; by Theorem 6, we have dim⁡(P(21,4))≥3.Table 6
The codecW(v) of v with respect to W={u1,v8,v9} in P(9,4).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u1 (0,3,2) u 2 (1,3,3) u 3 (2,2,3) u 4 (3,2,2) u 5 (3,3,2) u6 (3,3,3) u 7 (3,2,3) u 8 (2,1,2) u 9 (1,2,1) v 1 (1,4,2) v2 (2,3,4) v 3 (3,1,3) v 4 (3,1,1) v 5 (2,3,1) v 6 (2,4,3) v7 (3,2,4) v 8 (3,0,2) v 9 (2,2,0)Table 7
The codecW(v) of v with respect to W={u1,u5,v3} in P(10,4).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u1 (0,3,3) u 2 (1,3,2) u 3 (2,2,1) u 4 (3,1,2) u 5 (3,0,3) u6 (4,1,3) u 7 (3,2,2) u 8 (3,3,3) u 9 (2,3,2) u 10 (1,4,3) v1 (1,2,2) v 2 (2,3,3) v 3 (3,3,0) v 4 (3,2,3) v 5 (2,1,2) v6 (3,2,4) v 7 (2,3,1) v 8 (3,3,4) v 9 (3,2,1) v 10 (2,3,4)Table 8
The codecW(v) of v with respect to W={u1,v8,v11} in P(11,4).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u1 (0,2,2) u 2 (1,3,3) u 3 (2,3,3) u 4 (3,2,2) u 5 (3,3,3) u6 (4,3,3) u 7 (4,2,2) u 8 (3,1,3) u 9 (3,2,3) u 10 (2,3,2) u11 (1,3,1) v 1 (1,1,3) v 2 (2,4,4) v 3 (3,4,2) v 4 (3,1,1) v5 (2,2,4) v 6 (3,4,4) v 7 (3,3,1) v 8 (2,0,2) v 9 (3,3,4) v10 (3,4,3) v 11 (2,2,0)Table 9
The codecW(v) of v with respect to W={u1,v14,v17} in P(17,4).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u1 (0,2,2) u 2 (1,3,3) u 3 (2,4,3) u 4 (3,4,2) u 5 (3,3,3) u6 (4,3,4) u 7 (5,4,4) u 8 (5,4,3) u 9 (4,3,3) u 10 (4,2,4) u11 (5,3,4) u 12 (5,3,3) u 13 (4,2,2) u 14 (3,1,3) u 15 (3,2,3) u16 (2,3,2) u 17 (1,3,1) v 1 (1,1,3) v 2 (2,3,4) v 3 (3,5,4) v4 (3,5,1) v 5 (2,2,3) v 6 (3,2,5) v 7 (4,5,5) v 8 (4,5,2) v9 (3,3,2) v 10 (3,1,5) v 11 (4,4,5) v 12 (4,4,3) v 13 (3,3,1) v14 (2,0,4) v 15 (3,3,4) v 16 (3,4,3) v 17 (2,4,0)Table 10
The codecW(v) of v with respect to W={u1,u16,v14} in P(21,4).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u1 (0,5,3) u 2 (1,5,4) u 3 (2,4,5) u 4 (3,5,5) u 5 (3,6,4) u6 (4,6,3) u 7 (5,5,4) u 8 (5,4,4) u 9 (4,5,3) u 10 (5,5,2) u11 (6,4,3) u 12 (6,3,3) u 13 (5,3,2) u 14 (4,2,1) u 15 (5,1,2) u16 (5,0,3) u 17 (4,1,3) u 18 (3,2,2) u 19 (3,3,3) u 20 (2,3,4) u21 (1,4,4) v 1 (1,4,2) v 2 (2,4,3) v 3 (3,3,6) v 4 (3,4,6) v5 (2,5,3) v 6 (3,5,2) v 7 (4,4,5) v 8 (4,3,5) v 9 (3,4,4) v10 (4,4,1) v 11 (5,3,4) v 12 (5,2,4) v 13 (4,3,3) v 14 (3,3,0) v15 (4,2,3) v 16 (4,1,4) v 17 (3,2,4) v 18 (2,3,1) v 19 (3,3,4) v20 (3,2,5) v 21 (2,3,5)Theorem 10.
LetG be the graph G=P(2k,k) with k≥3; then (8)dim⁡G=3,ifk=3ork≡0mod2;≤4,otherwise.Proof.
Case 1 (k=3 or k≡0 (mod 2)). If k=3, let W={u3,v1,v2}. The code of v with respect to W in P(6,3) is presented in Table 11 showing that dim⁡(P(6,3))≤3.
Ifk=4, let W={v4,v7,v8}. The code of v with respect to W in P(8,4) is presented in Table 12 showing that dim⁡(P(8,4))≤3.
Ifk≥6, let W={u1,u2,uk+1}. Then the codes of the outer vertices are cW(ui)=(h1(i),h2(i),h3(i)) and the codes of the inner vertices are cW(vi)=(g1(i),g2(i),g3(i)), where (9)h1i=i-1,3≤i≤k2+2;k+4-i,k2+3≤i≤k;i+2-k,k+1≤i≤3k2-1;2k+1-i,3k2≤i≤2k.h2i=i-2,3≤i≤k2+3;k+5-i,k2+4≤i≤k+2;i+1-k,k+3≤i≤3k2;2k+2-i,3k2+1≤i≤2k.h3i=i+2,3≤i≤k2-1;k+1-i,k2≤i≤k;i-1-k,k+1≤i≤3k2+2;2k+4-i,3k2+3≤i≤2k.g1i=i,1≤i≤k2+1;k+3-i,k2+2≤i≤k+1;i+1-k,k+2≤i≤3k2;2k+2-i,3k2≤i≤2k.g2i=i+1i=1;i-1,2≤i≤k2+2;k+4-i,k2+3≤i≤k+1;i-k,k+2≤i≤3k2+1;2k+3-i,3k2+2≤i≤2k.g3i=i+1,1≤i≤k2;k+2-i,k2+1≤i≤k+1;i+2-k,k+2≤i≤3k2+1;2k+3-i,3k2+2≤i≤2k.It can be verified that there are no two vertices on the outer cycle with the same codes, and there are no two vertices in the inner cycle and outer cycle with the same codes. Moreover, no two vertices in the inner cycle have same codes. Hence, W={u1,u2,uk+1} is a resolving set of P(2k,k) for even k≥6. This means that dim⁡(P(2k,k))≤3 for even k≥6.
Case 2 (k≡1 (mod 2) and k≥5). Let W={u1,u2,uk+1,uk+2}. Then the codes of the outer vertices are cW(ui)=(h1(i),h2(i),h3(i),h4(i)), where(10)h1i=i-1,1≤i≤k+12+2;k+4-i,k+12+3≤i≤k+1;i+2-k,k+2≤i≤3k-12;2k+1-i,3k+12≤i≤2k.h2i=ii=1;i-2,1≤i≤k+12+3;k+5-i,k+12+4≤i≤k+2;i+1-k,k+3≤i≤3k-12;2k+2-i,3k+12+1≤i≤2k.h3i=i+2,1≤i≤k-12;k+1-i,k+12≤i≤k;i-1-k,k+1≤i≤3k+12+2;2k+4-i,3k+12+3≤i≤2k.h4i=i+3i=1;i+1,2≤i≤k+12;k+2-i,k+32≤i≤k+1;i-2-k,k+2≤i≤3k+12+3;2k+5-i,3k+12+4≤i≤2k.Then the codes of the inner vertices are cW(vi)=(g1(i),g2(i),g3(i),g4(i)), where(11)g1i=i,1≤i≤k+12+1;k+3-i,k+32≤i≤k;i+1-k,k+1≤i≤3k+12;2k+2-i,3k+32≤i≤2k.g2i=i+1i=1;i-1,2≤i≤k+32;k+4-i,k+52≤i≤k+1;i-k,k+2≤i≤3k+12;2k+3-i,3k+32≤i≤2k.g3i=i+1,1≤i≤k+12;k+2-i,k+32≤i≤k;i-k,k+1≤i≤3k+12;2k+3-i,3k+32≤i≤2k.g4i=i+2i=1;i,2≤i≤k+12;k+3-i,k+32≤i≤k+1;i-1-k,k+2≤i≤3k+32;2k+4-i,3k+52≤i≤2k.It can be verified that there are no two vertices on the outer cycle with the same codes, and there are no two vertices in the inner cycle and outer cycle with the same codes. Moreover, no two vertices in the inner cycle have same codes. Hence, W={u1,u2,uk+1,uk+2} is a resolving set of P(2k,k) for odd k≥5. This means that dim⁡(P(2k,k))≤4 for odd k≥5.Table 11
The codecW(v) of v with respect to W={u3,v1,v2} in P(6,3).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u1 (2,1,2) u 2 (1,2,1) u 3 (0,3,2) u 4 (1,2,3) u 5 (2,3,2) u6 (3,2,3) v 1 (3,0,3) v 2 (2,3,0) v 3 (1,4,3) v 4 (2,1,4) v5 (3,4,1) v 6 (2,3,4)Table 12
The codecW(v) of v with respect to W={v4,v7,v8} in P(8,4).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u1 (3,3,2) u 2 (3,3,3) u 3 (2,2,3) u 4 (1,3,2) u 5 (2,3,3) u6 (3,2,3) u 7 (3,1,2) u 8 (2,2,1) v 1 (4,4,3) v 2 (4,4,4) v3 (3,1,4) v 4 (0,4,1) v 5 (3,4,4) v 6 (4,3,4) v 7 (4,0,3) v8 (1,3,0)Theorem 11.
LetG be the graph G=P(3k,k) with k≥3; then (12)dim⁡G=4,ifk=7;3,otherwise.Proof.
Case 1 (k≡0 (mod 2)). If k=4, let W={u1,v10,v11}. The code of v with respect to W in P(12,4) is presented in Table 13 showing that dim⁡(P(12,4))≤3.
Ifk≥6, let W={u1,vk/2+2,vk+1}. Then the codes of the outer vertices are cW(ui)=(h1(i),h2(i),h3(i)) and the codes of the inner vertices are cW(vi)=(g1(i),g2(i),g3(i)), where (13)h1i=i-1,1≤i≤k2+2;k+4-i,k2+3≤i≤k+1;i+2-k,k+2≤i≤3k2+1;2k+4-i,3k2+2≤i≤2k+1;i-2k+2,2k+2≤i≤5k2-1;3k-i+1,5k2≤i≤3k.g1i=i,1≤i≤k2+1;k+3-i,k2+2≤i≤k+1;i+1-k,k+2≤i≤3k2+1;2k+3-i,3k2+2≤i≤2k+1;i-2k+1,2k+2≤i≤5k2;3k-i+2,5k2+1≤i≤3k.h2i=k2+1,i=1;k-i-2,2≤i≤k2+2;i-k+4,k2+3≤i≤k+2;2k-i-1,k+3≤i≤3k2+2;i-2k+5,3k2+3≤i≤2k+2;3k-i-1,2k+3≤i≤5k2+2;i-3k+5,5k2+3≤i≤3k.g2i=k2+2,i=1;0,i=k2+2;1,i∈3k2+2,5k2+2;k-i-1,2≤i≤k2+1;i-k+5,k2+3≤i≤k+2;2k-i,k+3≤i≤3k2+1;i-2k+6,3k2+3≤i≤2k+2;3k-i,2k+3≤i≤5k2+1;i-3k+6,5k2+3≤i≤3k.h3i=i+1,1≤i≤k2;k+2-i,k2+1≤i≤k+1;i-k,k+2≤i≤3k2+1;2k+3-i,3k2+2≤i≤2k+1;i-2k+1,2k+2≤i≤5k2+1;3k-i+3,5k2+2≤i≤3k.g3i=0,i=k+1;1,i∈1,2k+1;i+2,2≤i≤k2;k-i+3,k2+1≤i≤k;i-k+1,k+2≤i≤3k2+1;2k-i+4,3k2+2≤i≤2k;i-2k+2,2k+2≤i≤5k2+1;3k-i+4,5k2+2≤i≤3k.It can be verified that there are no two vertices on the outer cycle with the same codes, and there are no two vertices in the inner cycle and outer cycle with the same codes. Moreover, no two vertices in the inner cycle have same codes. Hence, W={u1,vk/2+2,vk+1} is a resolving set of P(3k,k) for even k≥6. This means that dim⁡(P(3k,k))≤3 for even k≥6.
Case 2 (k≡1 (mod 2) and k≥5). If k=5, let W={v4,v10,v13}. The code of v with respect to W in P(15,5) is presented in Table 14 showing that dim⁡(P(15,5))≤3.
Note that the diameter ofP(15,5) is 5; by Theorem 6, we have dim⁡(P(15,5))≥3.
Ifk=7, we can confirm that dim⁡(P(21,7))≥4 by an exhaustive search. Let W={v14,v17,v20,v21}. The code of v with respect to W in P(21,7) is presented in Table 15 showing that dim⁡(P(21,7))≤4.
Ifk≥9, let W={u1,vk,v(3k-3)/2}. Then the codes of the outer vertices are cW(ui)=(h1(i),h2(i),h3(i)) and the codes of the inner vertices are cW(vi)=(g1(i),g2(i),g3(i)), where (14)h1i=i-1,1≤i≤k+52;k+4-i,k+72≤i≤k+1;i+2-k,k+2≤i≤3k+12;2k+2-i,3k+32≤i≤2k+1;i-2k+2,2k+2≤i≤5k-12;3k-i+1,5k+12≤i≤3k.g1i=i,1≤i≤k+32;k+3-i,k+52≤i≤k+1;i+1-k,k+2≤i≤3k+12;2k+3-i,3k+32≤i≤2k+1;i-2k+1,2k+2≤i≤5k+12;3k-i+2,5k+32≤i≤3k.h2i=i+2,1≤i≤k-12;k+1-i,k+12≤i≤k;i+1-k,k+1≤i≤3k+12;2k+2-i,3k+32≤i≤2k;i-2k+2,2k+1≤i≤5k-12;3k-i+2,5k+12≤i≤3k.g2i=0,i=k;1,i∈2k,3k;i+3,1≤i≤k-12;k+2-i,k+12≤i≤k-1;i+2-k,k+1≤i≤3k+12;2k+3-i,3k+32≤i≤2k-1;i-2k+3,2k+1≤i≤5k-12;3k-i+3,5k+12≤i≤3k-1.h3i=k+12-i,1≤i≤k-32;i-1,k-12≤i≤k-2;k-i+4,k-1≤i≤3k-32;i-k-2,3k-12≤i≤2k-1;2k-i+5,2k≤i≤5k-32;i-2k-1,5k-12≤i≤3k-2;3k-i+5,3k-1≤i≤3k.g3i=0,i=3k-32;1,i∈k-32,5k-32;k+32-i,1≤i≤k-52;i,k-12≤i≤k-2;k-i+5,k-1≤i≤3k-52;i-k-1,3k-12≤i≤2k-1;2k-i+6,2k≤i≤5k-52;i-2k,5k-12≤i≤3k-2;3k-i+6,3k-1≤i≤3k.It can be verified that there are no two vertices on the outer cycle with the same codes, and there are no two vertices in the inner cycle and outer cycle with the same codes. Moreover, no two vertices in the inner cycle have same codes. Hence, W={u1,vk,v(3k-3)/2} is a resolving set of P(3k,k) for odd k≥9. This means that dim⁡(P(3k,k))≤3 for odd k≥9.
Now, we will show thatdim⁡(P(3k,k))≥3. Note that for any w∈U, say w=ui, we have |N2(w)|=6 (see Figure 1) and for any w∈V, say w=vi, we have N3w=8 (see Figure 2). By Lemma 7, we have dim⁡(P(3k,k))≥3.Table 13
The codecW(v) of v with respect to W={u1,v10,v11} in P(21,7).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u1 (0,3,3) u 2 (1,2,3) u 3 (2,3,2) u 4 (3,4,3) u 5 (3,3,4) u6 (4,2,3) u 7 (5,3,2) u 8 (4,3,3) u 9 (3,2,3) u 10 (3,1,2) u11 (2,2,1) u 12 (1,3,2) v 1 (1,4,4) v 2 (2,1,4) v 3 (3,4,1) v4 (3,5,4) v 5 (2,4,5) v 6 (3,1,4) v 7 (4,4,1) v 8 (3,4,4) v9 (2,3,4) v 10 (3,0,3) v 11 (3,3,0) v 12 (2,4,3)Table 14
The codecW(v) of v with respect to W={v4,v10,v13} in P(15,5).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u1 (4,3,4) u 2 (3,4,3) u 3 (2,4,2) u 4 (1,3,3) u 5 (2,2,4) u6 (3,3,4) u 7 (4,4,3) u 8 (3,3,2) u 9 (2,2,3) u 10 (3,1,4) u11 (4,2,3) u 12 (4,3,2) u 13 (3,4,1) u 14 (2,3,2) u 15 (3,2,3) v1 (5,4,5) v 2 (4,5,4) v 3 (3,5,1) v 4 (0,4,4) v 5 (3,1,5) v6 (4,4,5) v 7 (5,5,4) v 8 (4,4,1) v 9 (1,3,4) v 10 (4,0,5) v11 (5,3,4) v 12 (5,4,3) v 13 (4,5,0) v 14 (1,4,3) v 15 (4,1,4)Table 15
The codecW(v) of v with respect to W={v14,v17,v20,v21} in P(21,7).
v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) v c W ( v ) u1 (3,4,3,2) u 2 (4,3,4,3) u 3 (5,2,5,4) u 4 (5,3,4,5) u 5 (4,4,3,4) u6 (3,5,2,3) u 7 (2,5,3,2) u 8 (3,4,4,3) u 9 (4,3,5,4) u 10 (5,2,5,5) u11 (4,3,4,5) u 12 (3,4,3,4) u 13 (2,5,2,3) u 14 (1,4,3,2) u 15 (2,3,4,3) u16 (3,2,5,4) u 17 (4,1,4,5) u 18 (5,2,3,4) u 19 (4,3,2,3) u 20 (3,4,1,2) u21 (2,5,2,1) v 1 (4,5,4,3) v 2 (5,4,5,4) v 3 (6,1,6,5) v 4 (6,4,5,6) v5 (5,5,4,5) v 6 (4,6,1,4) v 7 (1,6,4,1) v 8 (4,5,5,4) v 9 (5,4,6,5) v10 (6,1,6,6) v 11 (5,4,5,6) v 12 (4,5,4,5) v 13 (3,6,1,4) v 14 (0,5,4,1) v15 (3,4,5,4) v 16 (4,3,6,5) v 17 (5,0,5,6) v 18 (6,3,4,5) v 19 (5,4,3,4) v20 (4,5,0,3) v 21 (1,6,3,0)Figure 1
The set of black vertices isN2(w) for w=ui.Figure 2
The set of black vertices isN3(w) for w=vi.



---

*Source: 4531958-2018-08-01.xml*