On the neighbor-distinguishing in generalized Petersen graphs

1.   Preliminaries

Let $G$ be a simple, non-trivial connected graph with vertex set $V(G)$. For any two distinct vertices $u$ and $v$ in $G$, $u$-$v$ geodesic is a shortest walk between $u$ and $v$ without repetition of vertices. Two vertices are said to be adjacent if there is an edge between them, and they are also called neighbors of each other. The collection of all the neighbors of a vertex $v$ in $G$ is called the (open) neighborhood of $v$, denoted by $N(v)$.

A vertex $v$ of $G$ distinguishes a pair $(x, y)$ of distinct vertices of $G$, if the number of edges in $v$-$x$ geodesic is different from the number of edge in $v$-$y$ geodesic. If $(x, y)$ is a pair of neighbors in $G$, then $v$ is said to be adjacently distinguish the pair $(x, y)$. Equivalently, a vertex $v$ adjacently distinguishes a pair $(x, y)$ of two neighbors if the difference between the number of edges in $v$-$x$ geodesic and the number of edges in $v$-$y$ geodesic is one.

A set $D \subseteq V(G)$ is a distinguishing set (metric generator) for $G$ if the members of $D$ distinguish every pair of distinct vertices in $G$. The cardinality of a smallest distinguishing set for $G$ is called the metric dimension of $G$, denoted by $dim(G)$ ^[7,23]. The concept of distinguishing set was introduced, very firstly, by Blumenthal ^[5] in the general context of metric spaces. It was later rediscovered and studied, in the context of graphs, by Slater with the name locating set/reference set ^[23]. Independently, Harary and Melter studied distinguishing set as resolving set (metric generator) ^[7,20]. Applications of this notion to the navigation of robots in networks are discussed in ^[13,21], and applications to pharmaceutical chemistry in ^[10,11]. For more details about the theory and applications of this notion, we refer the readers to the papers cited in ^{[3,5,8,9,12,13,14,15,19,22]} and the references therein.

A set $A \subseteq V(G)$ is a neighbor-distinguishing set (local metric generator) for $G$ if the members of $A$ adjacently distinguish every pair of neighboring (adjacent) vertices in $G$. The cardinality of a smallest neighbor-distinguishing set for $G$ is called the adjacency (local) metric dimension of $G$, and we denote it by $dim_a(G)$.

The problem of distinguishing every two neighbors with the aid of distance (the number of edges in a geodesic) in a connected graph was introduced and studied by Okamoto et al. in 2010 ^[16]. Then, up till now, this notion endlessly received remarkable interest of many researchers working with distance in graphs. In 2015 and 2018, every two neighbors in the corona product of graphs are distinguished ^[6,18], while this problem for strong product and lexicographic product of graphs was solved in 2016 ^[4] and in 2018 ^[2,6], respectively. Using the neighbor-distinguishing problem of primary subgraphs, this problem was solved for the super graphs of these subgraphs in 2015 ^[17]. In 2018, Salman et al. proposed linear programming formulation for this problem and distinguished neighbors in two families of convex polytopes ^[19]. Recently, in 2019, split graphs of complete and complete bipartite graphs have been considered in the context of this problem ^[1]. Due to this noteworthy attention of researchers to this problem, we extend this study towards a very renowned family of generalized Petersen graphs in this article. Next, we state two results, proved by Okamoto et al. ^[16], and Salman et al. ^[19], respectively, which will be used in the sequel.

Theorem 1. ^[16] Let $G$ be a non-trivial connected graph of order $n$. Then $dim_a(G)$ $= n-1$ if and only if $G$ is a complete graph, and $dim_a(G) = 1$ if and only if $G$ is a bipartite graph.

Proposition 2. ^[19] A subset $A$ of vertices in a connected graph $G$ is a neighbor-distinguishing set for $G$ if and only if for every $u\in V(G)$ and for each $v\in N(u)$, the pair $(u, v)$ adjacently distinguished by some element of $A$.

Watkins, in $1969$ ^[24], generalized the eminent Petersen graph, and proposed the notation $P(n, m)$ to this generalized family, where $n \geq 3$ and $1 \leq m \leq \lfloor \frac{n-1}{2} \rfloor$. $P(n, m)$ is a cubic graph having the set

as the vertex set, and the set

as the edge set, where $N(u_i) = \{u_{i+1}, u_{i-1}, v_i \}$ and $N(v_i) = \{u_i, v_{i+m}, v_{i-m} \}$ for each $1 \leq i \leq n$, and the indices greater than $n$ or less than $1$ will be taken modulo $n$. Vertices $u_i$ and $v_i$ $(1 \leq i \leq n)$ are called the outer vertices and inner vertices, respectively, in $P(n, m)$. Figure 1 depicts graphs to two different families of generalized Petersen graphs.

The rest of the paper is divided into two sections: one is on the family of generalized Petersen graphs $P(n, 4)$; and the second is on the family of generalized Petersen graphs $P(2n, n-1)$. These families have been considered in the context of metric dimension problem by Naz et al. ^[15] and Ahmad et al. ^[3], respectively. Here, we solve the neighbor-distinguishing problem for these families.

2.   Family of generalized Petersen graphs $P(n, 4)$

In the next result, we show that only two vertices of $P(n, 4)$ perform the neighbor-distinguishing.

Theorem 3. For $n\geq 9$, let $G$ be a generalized Petersen graph $P(n, 4)$, then a neighbor-distinguishing set for $G$ is a $2$-element subset of $V(G)$.

Proof. For $n = 9$, it is an easy exercise to see that the set $A = \{v_1, v_2 \}$ is a neighbor-distinguishing set for $G$. For $n\geq 10$, let $A$ be a $2$-element subset of $V(G)$. Then, according to Proposition 2, we would perform neighbor-distinguishing for each pair $(x, y)$, where $x \in V(G)$ and $y \in N(x)$. Note that, if $x \in A$, then $(x, y)$ is adjacently distinguished, because the number of edges in $y-x$ geodesic is $1$, while the number of edges in $x-x$ geodesic is $0$. Now, we discuss the following eight cases:

Case 1: ($n = 8k$ with $k\geq 2$)

Let $A = \{v_1 = a_1, v_3 = a_2\}$, then

● the number of edges in $u_1-a_2$ geodesic is 3,

● the number of edges in $u_2-a_2$ geodesic is 2,

● the number of edges in $v_1-a_2$ geodesic is 4,

● the number of edges in $v_2-a_2$ geodesic is 3.

Further, Tables 1 and 2 provide the lists of number of edges in $x-a_1$ and $x-a_2$ geodesics for all $x \in V(G)-A$.

Case 2: ($n = 8k+1$ with $k\geq 2$)

Let $A = \{v_1 = a_1, v_4 = a_2\}$, then

● the number of edges in $u_1-a_2$ geodesic is 3,

● the number of edges in $u_2-a_2$ geodesic is 3,

● the number of edges in $u_3-a_2$ geodesic is 2.

Further, Tables 1–3 provide the lists of number of edges in $x-a_1$ and $x-a_2$ geodesics for all $x \in V(G)-A$.

Case 3: ($n = 8k+2$ with $k\geq 1$)

Let $A = \{v_1 = a_1, v_2 = a_2\}$, then

● the number of edges in $u_2-a_2$ geodesic is 2.

Further, Tables 1, 2 and 4 provide the lists of number of edges in $x-a_1$ and $x-a_2$ geodesics for all $x \in V(G)-A$.

Case 4: ($n = 8k+3$ with $k\geq 1$)

Let $A = \{v_1 = a_1, v_3 = a_2\}$, then

● the number of edges in $u_1-a_2$ geodesic is 3,

● the number of edges in $u_2-a_2$ geodesic is 2.

Further, Tables 1, 2 and 5 provide the lists of number of edges in $x-a_1$ and $x-a_2$ geodesics for all $x \in V(G)-A$.

Case 5: ($n = 8k+4$ with $k\geq 1$)

Let $A = \{v_1 = a_1, v_4 = a_2\}$, then

● the number of edges in $v_1-a_2$ geodesic is 4,

● the number of edges in $v_2-a_2$ geodesic is 4,

● the number of edges in $u_1-a_2$ geodesic is 3,

● the number of edges in $u_2-a_2$ geodesic is 3.

Moreover, Tables 1 and 2 provide the lists of number of edges in $x-a_1$ and $x-a_2$ geodesics for all $x \in V(G)-A$.

Case 6: ($n = 8k+5$ with $k\geq 1$)

Let $A = \{v_1 = a_1, v_2 = a_2\}$, then

● the number of edges in $u_1-a_2$ geodesic is 2,

● the number of edges in $v_1-a_2$ geodesic is 3.

Further, Tables 1, 2 and 6 provide the lists of number of edges in $x-a_1$ and $x-a_2$ geodesics for all $x \in V(G)-A$.

Case 7: ($n = 8k+6$ with $k\geq 1$)

Let $A = \{v_1 = a_1, v_2 = a_2\}$, then

● the number of edges in $v_{3k+3}-a_1$ geodesic is $\frac{5k+4}{4} \equiv 3 (mod \ 4)$,

● the number of edges in $v_{3k+4}-a_2$ geodesic is $\frac{5k+4}{4} \equiv 0 (mod \ 4)$,

● the number of edges in $u_{4k+3}-a_1$ geodesic is $k+2$,

● the number of edges in $u_{4k+4}-a_1$ geodesic is $k+3$,

● the number of edges in $u_{4k+5}-a_1$ geodesic is $k+2$,

● the number of edges in $u_{4k+4}-a_2$ geodesic is $k+2$,

● the number of edges in $u_{4k+5}-a_2$ geodesic is $k+3$,

● the number of edges in $u_{4k+6}-a_2$ geodesic is $k+2$.

Further, Tables 1, 2 and 7 provide the lists of number of edges in $x-a_1$ and $x-a_2$ geodesics for all $x \in V(G)-A$.

Case 8: ($n = 8k+7$ with $k\geq 1$)

Let $A = \{v_1 = a_1, v_3 = a_2\}$, then

● the number of edges in $v_{1}-a_2$ geodesic is $4$,

● the number of edges in $u_{4k+4}-a_1$ geodesic is $k+2$,

● the number of edges in $u_{4k+5}-a_1$ geodesic is $k+2$,

● the number of edges in $u_{1}-a_2$ geodesic is $3$,

● the number of edges in $u_{5k+2}-a_2$ geodesic is $\frac{3k+12}{4} \equiv 2 (mod \ 4)$,

● the number of edges in $u_{5k+3}-a_2$ geodesic is $\frac{5k+4}{4} \equiv 3 (mod \ 4)$.

Moreover, Tables 1, 2 and 8 provide the lists of number of edges in $x-a_1$ and $x-a_2$ geodesics for all $x \in V(G)-A$.

In all of these eight cases, for $y \in N(x)$, if we denote

● the number of edges in $x-a_1$ geodesic by $\alpha_1$,

● the number of edges in $y-a_1$ geodesic by $\beta_1$,

● the number of edges in $x-a_2$ geodesic by $\alpha_2$,

● the number of edges in $y-a_2$ geodesic by $\beta_2$,

then it can be seen that

which implies that either $a_1 \in A$ or $a_2 \in A$ adjacently distinguishes the pair $(x, y)$. Hence, $A$ is a neighbor-distinguishing set for $G$.

Theorem 4. For $n\geq 9$, if $G$ is a generalized Petersen graph $P(n, 4)$, then $dim_a(G) = 2$.

Proof. Since $dim_a(G) = 1$ if and only if $G$ is a bipartite graph, by Theorem 1. So $dim_a(G)\geq 2$, because $G$ is not a bipartite graph. Hence, we get the required result, by Theorem 3.

3.   Family of generalized Petersen graphs $P(2n, n-1)$

The results of this section provide the solution of the problem of neighbor-distinguishing in the generalized Petersen graphs $P(2n, n-1)$.

Theorem 5. For all $n\geq 3$, if $G$ is a generalized Petersen graph $P(2n, n-1)$, then the set $A = \{u_1, v_{n-1} \}$ is a neighbor-distinguishing set for $G$.

Proof. According to Proposition 2, we have to perform neighbor-distinguishing for each pair $(x, y)$, where $x \in V(G)$ and $y \in N(x)$. When $x \in A$, then the pair $(x, y)$ adjacently distinguished by $x$, because the number of edges in $y-x$ geodesic is $1$ while the number of edges in $x-x$ geodesic is $0$. Further, Table 9 provides the list of number of edges in $x-u_1$ and $x-v_{n-1}$ geodesics for all $x \in V(G)-A$.

Now, for any $y\in N(x)$, if we denote

● the number of edges in $x-u_1$ geodesic by $\alpha_1$,

● the number of edges in $y-u_1$ geodesic by $\beta_1$,

● the number of edges in $x-v_{n-1}$ geodesic by $\alpha_2$,

● the number of edges in $y-v_{n-1}$ geodesic by $\beta_2$,

then it can be seen that

which implies that either $u_1 \in A$ or $v_{n-1} \in A$ adjacently distinguishes the pair $(x, y)$. Hence, $A$ is a neighbor-distinguishing set for $G$.

Theorem 6. For $n\geq 3$, if $G$ is a generalized Petersen graph $P(2n, n-1)$, then $dim_a(G) = 2$.

Proof. Since $dim_a(G) = 1$ if and only if $G$ is a bipartite graph, by Theorem 1. So $dim_a(G)\geq 2$, because $G$ is not a bipartite graph. Hence, we get the required result, by Theorem 5.

4.   Conclusions

Distinguishing every two vertices in a graph is an eminent problem in graph theory. Many graph theorists have been shown remarkable interest to solve this problem with the aid of distance (the number of edges in a geodesic) from last four decades. Using the technique of finding geodesics between vertices, we solved the problem of distinguishing every two neighbors in generalized Petersen graphs $P(n, 4)$ and $P(2n, n-1)$. We investigated that, in both the families of generalized Petersen graphs, only two vertices are adequate to distinguish every two neighbors.

Acknowledgments

The authors are grateful to the editor and anonymous referees for their comments and suggestions to improve the quality of this article. This research is supported by Balochistan University of Engineering and Technology Khuzdar, Khuzdar 89100, Pakistan.

Conflict of interest

The authors declare that they have no conflict of interest.