Self-centeredness of Generalized Petersen Graphs

Abstract

A connected graph is said to be self-centered if all its vertices have the same eccentricity. The family of generalized Petersen graphs P(n, k), introduced by Coxeter [6] and named by Watkins [18], is a family of cubic graphs of order 2n defined by positive integral parameters n and k, $n\ge 2k$. Not all generalized Petersen graphs are self-centered. In this paper, we prove self-centeredness of P(n, k) whenever k divides n and $k< \frac{n}{2}$, except the case when n is odd and k is even. We also prove non-self-centeredness of generalized Petersen graphs P(n, k) when n even with $k=\frac{n}{2}$; $n=4m+2$ with $k=\frac{n}{2}-1$ for some positive integer $m\ge 3$; $n\ge 9$ is odd and $k=2$ or $k=\frac{n-1}{2}$; and $n = m(4m+1 )\pm (m+1)$ with $k = 4m + 1$ for any positive integer $m \ge 2$. Finally, we make an exhaustive computer search and get all possible values of n and k for which P(n, k) is non-self-centered.

1 Introduction

Graph centrality plays a significant importance in facility location problem, and has a great role in designing a communication network. In a locality, for the efficient use of resources, we place them at central nodes. Because of this, self-centered graphs are ideal as the facility can be placed (located) at any node or vertex of the locality. In the paper, by a graph $G=(V(G),E(G))$ (or simply G) we mean a simple finite graph with the vertex set V(G) and the edge set E(G). The length of a shortest u–v path in a graph G gives the distance between vertices u and v, which is denoted by $d_G(u,v)$ (or d(u, v)). The maximum of distances from a vertex v to all other vertices in a graph G is known as the eccentricity (denoted by e(v)) of the vertex v. The radius of G, denoted by rad(G), is the minimum eccentricity of vertices in G. Similarly, the diameter of G, denoted by diam(G), is the maximum eccentricity of vertices. Vertices with minimum eccentricity are called central vertices and the subgraph induced on these vertices is called the center C(G) of the graph G. A graph G is known as a self-centered graph if $C(G) = G$. In other words, for a self-centered graph G, rad(G) is equal to diam(G). Further, if eccentricity of every vertex in a self-centered graph is d then the graph is known as d-self-centered graph.

As a generalization of the well-known Petersen graph, the generalized Petersen graph has attracted the attention of several researchers. For each positive integers n and k with $n\ge 2k$, the generalized Petersen graph P(n, k) is a graph with vertex set $V(P(n,k))=\{u_{0},u_{1},u_{2},...,u_{n-1},v_{0},v_{1},v_{2},$ $\ldots ,v_{n-1}\}$ and the edge set E(P(n, k)) $=\{u_{i}u_{i+1},u_{i}v_{i},v_{i}v_{i+k} : 0\le i\le n-1$}, where subscripts are addition modulo n. Throughout the paper, we refer this notation for vertex set and edge set of P(n, k). For $n=5$ and $k=2$, P(5, 2) is the well known Petersen graph.

The generalized Petersen graphs, named by Watkins [18] were defined by Coxeter [6] but not with this name. The essence of the Petersen graph is a remarkable configuration that serves as a counterexample to many optimistic predictions and conjectures about what might be true for graphs in general. The generalized Petersen graphs have been studied by several authors; for instance, Tait coloring of generalized Petersen graphs have been studied and analysed in [4], generalization of generalized Petersen graphs on the basis of symmetry properties have been discussed in [13]. A result on maximum number of vertices in a generalized Petersen graph was given by authors in [1], where number of vertices is treated as a function of diameter. A formula for number of isomorphism classes of generalized Petersen graphs was presented by Steimle and Staton [17]. For works related to domination number in generalized Petersen graphs, one can refer to [5, 7], and [9]. However, there were no significant work done related to self-centeredness of generalized Petersen graphs because of the complex structure of these graphs. This motivated us to work on the self-centeredness property of generalized Petersen graphs.

The theorem below gives a criteria for generalized Petersen graphs to be isomorphic.

Theorem 1

[17] Let $n>3$ and k, l relatively prime to n with $kl\equiv 1 \pmod n$. Then $P(n,k)\cong P(n,l)$.

The theorem stated below is useful in proving the self-centeredness of generalized Petersen graph P(n, 1).

Theorem 2

[16] Let $G = G_1\Box G_2$ be the Cartesian product of graphs $G_1$ and $G_2$. If $G_1$ and $G_2$ are l- and m-self centered graphs, respectively, then G is $(l+m)$-self centered graph.

We note that P(n, 1) is the Cartesian product of the cycle $C_n$ and the complete graph $K_2$. Since $C_n$ is $\lfloor \frac{n}{2} \rfloor$-self-centered graph and $K_2$ is 1-self-centered graph, by Theorem 2 we get the result below.

Theorem 3

For $n\ge 3$, the generalized Petersen graph P(n, 1) is a d-self-centered graph, where $d = \lfloor \frac{n}{2} \rfloor + 1$.

Vertex transitive graphs are self-centered. In [8], the authors have proved that P(n, k) is vertex transitive if and only if $k^2 \equiv \pm 1 (\bmod \ n)$, or $n=10$ and $k=2$. So, one get the following result.

Theorem 4

For $n\ge 3$, generalized Petersen graph P(n, k) is self-centered for $k^2 \equiv \pm 1 (\bmod \ n)$, or $n=10$ and $k=2$. Moreover, P(10, 2) is 5-self-centered and the other P(n, k) are d-self-centered, where

$$\begin{aligned} d = {\left\{ \begin{array}{ll} k+1, &{} \mathrm { if }\,\, n = k^2-1,\\ k+1, &{} \mathrm { if }\,\, n = k^2+1 \,\,\mathrm { and }\,\, k \,\,\mathrm {is} \,\,\mathrm {even, }\,\, k\ne 2,\\ k+2, &{} \mathrm { if }\,\, n = k^2+1 \,\,\mathrm { and }\,\, k \,\,\mathrm {is} \,\,\mathrm {odd.}\\ \end{array}\right. } \end{aligned}$$

Self-centered graphs were studied and surveyed by many authors in the last few decades. For the same, we refer the articles [2, 3], and [10,11,12]. Self-centeredness of different types of graph products are studied by the authors in [14, 15].

In the remaining of the paper, we assume $k\ge 2$. The main technique followed in this paper for verification of self-centeredness of P(n, k) is the determination of eccentricities of $u_0$ and $v_0$, because P(n, k) is symmetric on outer vertices $u_0,u_1,u_2,\ldots ,u_{n-1}$ and also symmetric on inner vertices $v_0,v_1,v_2,\ldots ,$ $v_{n-1}$. If $e(u_0) = e(v_0)$ then the generalized Petersen graph is self-centered, otherwise not.

The rest of the paper is organized as follows. In Sect. 2, we prove the non-self-centeredness of generalized Petersen graphs P(n, k) when n even, $k = \frac{n}{2}$ or $n=4m+2$ with $k=\frac{n}{2}-1$ for some positive integer $m\ge 3$. Then we prove self-centeredness of P(n, k) whenever n is even, $k< \frac{n}{2}$ and k divides n. In Sect. 3, we study self-centeredness of generalized Petersen graphs P(n, k) for odd n. We prove that P(n, k) is not self-centered for odd $n\ge 9$ with $k=2$ or $k = \frac{n-1}{2}$. Then we prove the self-centeredness of P(n, k) for odd n and odd k, $k< \frac{n}{2}$, and k|n. Also, we prove non-self-centeredness of P(n, k) when $n = m(4m+1 )\pm (m+1)$ with $k = 4m + 1$ for any positive integer $m \ge 2$. Finally, we make an exhaustive computer search and get all possible values of n and k for which P(n, k) is non-self-centered.

2 Self-centeredness of P(n, k) for an Even n

In the following result, we investigate the self-centeredness of P(n, k) for an even n and $k=\frac{n}{2}$.

Theorem 5

Let P(n, k) be a generalized Petersen graph such that $n\ge 4$ is even and $k = \frac{n}{2}$. Then P(n, k) is not a self-centered graph.

Proof

To prove the result, it is sufficient to show that eccentricity of two vertices in P(n, k) are not equal. We note that $C:v_0,u_0,u_1,u_2,\ldots ,u_k,v_k,v_0$ induces a cycle of length $k+3$, see Fig. 1, where the cycle C is highlighted by thick lines. We observe that $d(u_0, u_i) = d(u_0, u_{n-i})$, for $i \in \{ 1, 2, 3, ..., \frac{n}{2}\}$. Depending on the parity of k, we distinguish following two cases.

Fig. 1.

Generalized Petersen graph P(n, k) with n even and $k = \frac{n}{2}$

• Case 1. The integer k is even.

  Since $k = \frac{n}{2}$, in this case n will be a multiple of four. Consider vertices $u_0$ and $v_0$. Since $u_0$ lies on C and C is of length $k+3$,

  $$\begin{aligned} \max \{d(u_0,u_i) : 1\le i\le \frac{n}{2}\} = \lfloor \frac{k+3}{2}\rfloor = \frac{k+2}{2} = \frac{n+4}{4}= \frac{n}{4}+1. \end{aligned}$$

  (1)

  Next, we find $d(u_0,v_i)$ for $1\le i\le \frac{n}{2}$. First, let $1\le i\le \frac{n}{4}$. For these values of i, we get that $d(u_0,v_i) = d(u_0,u_i) + 1$. Now, $\max \{d(u_0,u_i): 1\le i\le \frac{n}{4}\}= \frac{n}{4}$ and so

  $$\begin{aligned} \max \{d(u_0,v_i) : 1\le i\le \frac{n}{4}\} = \max \{d(u_0,u_i) + 1 : 1\le i\le \frac{n}{4}\} = \frac{n}{4}+1. \end{aligned}$$

  (2)

  For $\frac{n}{4} <i \le \frac{n}{2}$, a shortest $v_i$–$u_0$ path is given by $P_i: v_i,v_{i+k},u_{i+k},u_{i+(k+1)},$ $u_{i+(k+2)},\ldots ,u_0$, where $l(P_i) = n-i-k+2 = \frac{n}{2} +2 -i$ (since $k = \frac{n}{2}$). The maximum length of $P_i$ is for $i =\frac{n}{4}+1$, and hence

  $$\begin{aligned} \max \{l(P_i):\frac{n}{4} <i \le \frac{n}{2}\} = \frac{n}{4}+1. \end{aligned}$$

  (3)

  From Eqs. (1)−(3), we get that $e(u_0) = \frac{n}{4}+1$.

  Since $v_0$ lies on C and n is a multiple of four,

  $$\begin{aligned} \max \{d(v_0,u_i) : 1\le i\le \frac{n}{2}\} = \lfloor \frac{k+3}{2}\rfloor =\frac{n}{4}+1. \end{aligned}$$

  (4)

  Next for $\frac{n}{4} \le i \le \frac{n}{2}$, we obtain $d(v_0,v_i) = d(u_0,v_i) +1$, and this gives

  $$\begin{aligned} \max \{d(v_0,v_i) : \frac{n}{4} \le i \le \frac{n}{2}\} =\frac{n}{4}+1. \end{aligned}$$

  (5)

  Finally, for $1\le i\le \frac{n}{4}$, a shortest $v_i$–$v_0$ path is given by $P'_i: v_i,v_{i+k},u_{i+k},u_{i+(k+1)},$ $\ldots ,u_0$, where $l(P'_i) = n-i-k+3 = \frac{n}{2}+3-i$, and the maximum length of $P'_i$ is for $i = \frac{n}{4}+1$, i.e.,

  $$\begin{aligned} \max \{l(P'_i):1\le i\le \frac{n}{4}\} = \frac{n}{2}+3-\frac{n}{4}-1 = \frac{n}{4}+2. \end{aligned}$$

  (6)

  Hence $e(v_0) = \frac{n}{4}+2$. Thus, we get that $e(u_0)\ne e(v_0)$ and P(n, k) is not a self-centered graph in this case.

• Case 2. The integer k is odd.

  In this case n is not a multiple of four but cycle C is of an even length. Since $u_0$ and $v_0$ lie on C, for $1\le i\le \frac{n}{2}$, we have

  $$\begin{aligned} \max \{d(u_0,u_i): 1\le i\le \frac{n}{2}\} = \frac{k+3}{2} ~~\text {and,} \end{aligned}$$

  (7)
  $$\begin{aligned} \max \{d(v_0,u_i) : 1\le i\le \frac{n}{2}\} = \frac{k+3}{2}. \end{aligned}$$

  (8)

  For $1\le i\le \lfloor \frac{n}{4}\rfloor +1$, a shortest $u_0$–$v_i$ path is given by $Q_i:u_0,u_1,u_2,\ldots ,u_i,v_i$, where $l(Q_i) = i+1$ and maximum length of $Q_i$ is for $i=\lfloor \frac{n}{4}\rfloor +1$, i.e.,

  $$\begin{aligned} \max \{l(Q_i) : 1\le i\le \lfloor \frac{n}{4}\rfloor +1\} = \lfloor \frac{n}{4}\rfloor +1+1= \lfloor \frac{k+3}{2}\rfloor . \end{aligned}$$

  (9)

  Again, for $\lfloor \frac{n}{4}\rfloor +2\le i\le \frac{n}{2}$, a shortest $u_0$–$v_i$ path is given by $Q_i':v_i,v_{i+k},u_{i+k},$ $u_{i+(k+1)},$ $\ldots ,u_0$ and the length of $Q_i'$ is $\frac{n}{2} + 2 - i$. The path $Q_i'$ has a maximum length for $i = \lfloor \frac{n}{4}\rfloor +2$, i.e.,

  $$\begin{aligned} \max \{l(Q_i') : \lfloor \frac{n}{4}\rfloor +2\le i\le \frac{n}{2}\} = \frac{n}{2} - \lfloor \frac{n}{4}\rfloor = \frac{k+1}{2}. \end{aligned}$$

  (10)

  From Eqs. (7), (9), and (10), we have $e(u_0) = \frac{k+3}{2}$.

  Next, we consider the vertex $v_0$. For $1\le i\le \lfloor \frac{n}{4}\rfloor +1$, a shortest $v_0$–$v_i$ path is given by $T_i:v_0,u_0,u_1,u_2,\ldots ,u_i,v_i$. The length of the path $T_i$ is $i+2$. The maximum length of $T_i$ is for $i=\lfloor \frac{n}{4}\rfloor +1$, i.e.,

  $$\begin{aligned} \max \{l(T_i) : 1\le i\le \lfloor \frac{n}{4}\rfloor +1\} = \lfloor \frac{n}{4}\rfloor +1+2= \frac{k+5}{2}. \end{aligned}$$

  (11)

  Finally, for $\lfloor \frac{n}{4}\rfloor +2\le i\le \frac{n}{2}$, a shortest $v_0$–$v_i$ path is given by $T_i':v_i,v_{i+k},u_{i+k},u_{i+(k+1)},$ $\ldots ,u_n=u_0,v_0$, where $l(T_i') = \frac{n}{2}+3-i$. We get the maximum length of $T_i'$ for $\lfloor \frac{n}{4}\rfloor +2$, i.e.,

  $$\begin{aligned} \max \{l(T_i') : \lfloor \frac{n}{4}\rfloor +2\le i\le \lfloor \frac{n}{2}\rfloor \} = \frac{k}{2}+1. \end{aligned}$$

  (12)

  From Eqs. (8), (11), and (12), we have $e(v_0) = \frac{k+5}{2}$. This proves that $e(u_0) \ne e(v_0)$. Hence, P(n, k) is not a self-centered graph in this case also.

   $\square$

In the following theorem we get some non-self-centered generalized Petersen graphs P(n, k), where n is even but not divisible by k.

Theorem 6

Let P(n, k) be a generalized Petersen graph such that $n = 4m+2$ for some positive integer $m\ge 3$ and $k = \frac{n}{2}-1$. Then P(n, k) is not a self-centered graph.

Proof

Here we obtain a cycle $C: u_0,u_1,u_2,\ldots ,u_{\frac{n}{2}-1},v_{\frac{n}{2}-1},v_0,u_0$ of length $\frac{n+4}{2}$ i.e. of length $2m+3$, see Fig. 2, where the cycle C is highlighted by thick lines.

Fig. 2.

Generalized Petersen graph P(n, k) with $n=4m+2$ and $k = \frac{n}{2}-1$

Since $u_0$ and $v_0$ lie on C, we have

$$\begin{aligned} \begin{aligned} \max \{d(u_0,u_i) : 1\le i\le \frac{n}{2}-1\} = \max \{d(v_0,u_i):1\le i\le \frac{n}{2}-1\} = \lfloor \frac{2m+3}{2}\rfloor =m+1. \end{aligned} \end{aligned}$$

(13)

We have $d(u_0,u_{m+1}) = d(u_0,u_{m+2}) = m+1$ and $d(v_0,u_m) = d(v_0,u_{m+1}) = m+1$. Next, for every $j \in \{1,2,\ldots ,m\}\cup \{m+3,m+4,\ldots ,2m+1\}$, we get $d(u_0,v_j) \le m+1$. Similarly, for every $l \in \{1,2,\ldots ,m-1\}\cup \{m+2,m+4,\ldots ,2m+1\}$, $d(v_0,v_l) \le m+1$. Now for $l = m+1$ and $m+2$, a shortest $u_0$–$v_i$ paths $P_1$ and $P_2$ are given below.

$$\begin{aligned} \begin{array}{c} P_1 : u_n=u_0,u_{n-1},u_{n-2},\ldots ,u_{n-(m-1)},v_{n-(m-1)}, v_{m+1} = v_l, \quad \text {and} \\ P_2 : u_n=u_0,u_{n-1},u_{n-2},\ldots ,u_{n-(m-2)},v_{n-(m-2)}, v_{m+2} = v_l. \end{array} \end{aligned}$$

Also,

$$\begin{aligned} l(P_1) = m+1 \text { and } l(P_2) =m. \end{aligned}$$

(14)

Further for $l=m$ and $m+1$, smallest $v_0$–$v_i$ paths are as given below.

$P_3 : v_0,u_0,u_1,u_2,\ldots ,u_m, v_l = v_m$, and

$P_4 : v_0,u_0,u_{n-1},u_{n-2},\ldots ,u_{n-(m-1)},v_{n-(m-1)},v_l = v_{m+1}$. We notice that

$$\begin{aligned} l(P_3) = m+2 \text { and } l(P_4) =m+2. \end{aligned}$$

(15)

From the above three equations, we conclude that $e(u_0) = m+1$ and $e(v_0) = m+2$. Thus, $e(u_0) \ne e(v_0)$, and hence P(n, k) is not a self-centered graph.    $\square$

Theorem 7

Let P(n, k) be a generalized Petersen graph with n even, $k < \frac{n}{2}$ and n be divisible by k. If $n = kq$ then P(n, k) is a d-self-centered graph, where

$$\begin{aligned} d = {\left\{ \begin{array}{ll} \frac{q}{2} + \lfloor \frac{k+3}{2}\rfloor , &{} \mathrm { if }\,\, k \,\,\mathrm { divides }\,\, \frac{n}{2},\\ \lfloor \frac{q+1}{2}\rfloor + \lfloor \frac{k}{2}\rfloor +1, &{} \mathrm { otherwise.} \end{array}\right. } \end{aligned}$$

Proof

To prove the result, we consider the following sets of vertices in P(n, k).

$\bullet$ $R_1:$ :

$\{u_0,v_0,v_k,u_k,u_{k-1},u_{k-2},\ldots ,u_3,u_2,u_1\}$ and $R_1' :\{v_1,v_2,\ldots ,v_{k-1}\}$

$\bullet$ $R_2:$ :

$\{u_k,v_k,v_{2k},u_{2k},u_{2k-1},u_{2k-2},\ldots ,u_{k+1}\}$ and $R_2' :\{ v_{k+1},v_{k+2},\ldots ,v_{2k-1}\}$

$\vdots$

$\bullet$ $R_q:$ :

$\{u_{(q-1)k},v_{(q-1)k},v_{qk},u_{qk},u_{qk-1},u_{qk-2},\ldots ,u_{qk-k+1}\}$ and

$~~R_q' :\{ v_{k(\frac{q}{2}-1)},v_{k(\frac{q}{2}-1) + 1},\ldots ,v_{\frac{kq}{2}-1}\}$

We see that vertices of each $R_i$, $i \in \{1,2,\ldots ,q\}$, induces a cycle of length $k+3$, vertices of each $R'_i$ induces independent set and $\bigcup _{i=1}^{q} (R_i\cup R_i') = V(P(n,k))$. Next, we find distances from $u_0$ and $v_0$ to other vertices of P(n, k). It is sufficient to find the distances from $u_0$ and $v_0$ to vertices $u_1,u_2,\ldots ,u_{\frac{n}{2}}$, $v_0,u_0,v_1,v_2,\ldots ,v_{\frac{n}{2}}$. Here, we have following two cases.

• Case 1. When k divides $\frac{n}{2}$.

  Since vertices of $R_1$ induces a cycle $u_0,v_0,v_k,u_k,\ldots ,u_2,u_1,u_0$ of length $k+3$, we have

  $$\begin{aligned} \max \{d(u_0,x) : x\in R_1\} = \max \{d(v_0,x) : x\in R_1\} = \lfloor \frac{k+3}{2}\rfloor . \end{aligned}$$

  (16)
  $$\begin{aligned} \max \{d(u_0,x) : x\in R_1'\} = \max \{d(v_0,x) : x\in R_1'\} = \lfloor \frac{k+3}{2}\rfloor + 1. \end{aligned}$$

  (17)

  We see that for any vertex $x\in R_2$, $d(u_0,x) = d(u_0,v_0) + d(v_0,v_k) + d(v_k,x)$ and thus, we have

  $$\begin{aligned} \max \{d(u_0,x) : x\in R_2\} = \lfloor \frac{k+3}{2}\rfloor + 2, \quad \text {and} \end{aligned}$$

  (18)
  $$\begin{aligned} \max \{d(u_0,x) : x\in R_2'\} = \lfloor \frac{k+3}{2}\rfloor + 3, \quad \,\, \end{aligned}$$

  (19)

  and,

  $$\begin{aligned} \max \{d(v_0,x) : x\in R_2\} = \lfloor \frac{k+3}{2}\rfloor + 1, \quad \text {and} \end{aligned}$$

  (20)
  $$\begin{aligned} \max \{d(v_0,x) : x\in R_2'\} = \lfloor \frac{k+3}{2}\rfloor + 2. \quad \,\, \end{aligned}$$

  (21)

  Similarly, we get

  $$\begin{aligned} \max \{d(u_0,x) : x\in R_q\} = \lfloor \frac{k+3}{2}\rfloor + \frac{q}{2}, \quad \text {and} \end{aligned}$$

  (22)

  for the vertices $v_j\in R_q'$ for $j\ne \frac{k(q-1)}{2}$ and $\frac{k(q-1)}{2}+1$ when k is even, then

  $$\begin{aligned} \max \{d(u_0,x) : x\in R_q', x\ne v_{\frac{k(q-1)}{2}},v_{\frac{k(q-1)}{2}+1}\} = \lfloor \frac{k+3}{2}\rfloor + \frac{q}{2}. \end{aligned}$$

  (23)

  For $j= \frac{k(q-1)}{2}$, a shortest $u_0$–$v_j$ path is given by

  $P:u_0,u_1,\ldots ,u_{\frac{k}{2}},v_{\frac{k}{2}},v_{\frac{k}{2}+k},v_{\frac{k}{2}+2k},\ldots , v_{\frac{k}{2}+\frac{k(q-1)}{2}}$ and thus $d(u_0,u_j) =\frac{k+q}{2}$. Due to symmetric structure of the graph, the same can be obtained for $j = \frac{k(q-1)}{2}+1$.

  Finally, consider vertices $v_j\in R_q'$ for $j\ne \frac{q(k-1)}{2}$ when k is odd. Then

  $$\begin{aligned} \max \{d(u_0,x) : x\in R_q', x\ne v_{\frac{q(k-1)}{2}}\} = \lfloor \frac{k+3}{2}\rfloor + \frac{q}{2}, \end{aligned}$$

  (24)

  and for $j= \frac{q(k-1)}{2}$ a shortest $u_0$–$v_j$ path is given by

  $P':u_0,u_1,\ldots ,u_{\frac{k+1}{2}},v_{\frac{k+1}{2}},v_{\frac{k+1}{2}+k},v_{\frac{k+1}{2}+2k},\ldots , v_{\frac{k+1}{2}+k(\frac{q}{2}-1)}$ of length $\frac{k+q+1}{2}$ and thus $d(u_0,u_j) =\frac{k+q+1}{2}$.

  Now, for the vertex $v_0$, we obtain

  $$\begin{aligned} \max \{d(v_0,x) : x\in R_q\} = \lfloor \frac{k+3}{2}\rfloor + \frac{q}{2}-1. \end{aligned}$$

  (25)
  $$\begin{aligned} \max \{d(v_0,x) : x\in R_q'\} = \lfloor \frac{k+3}{2}\rfloor + \frac{q}{2}. \end{aligned}$$

  (26)

  From Eqs. (16)–(26), we conclude that $e(u_0) = e(v_0) = \frac{q}{2} + \lfloor \frac{k+3}{2}\rfloor$.

• Case 2. When k does not divide $\frac{n}{2}$.

  Given that $n=kq$ and k does not divide $\frac{n}{2}$, so q is an odd integer. This means k must be even. In this case, the distance between the vertex $u_0$ and a vertex in $R_1\cup \ldots \cup R_{\frac{q-1}{2}}$ is the same as obtained in the Case 1. That is, the maximum distance between $u_0$ and any vertex from $R_{\frac{q-1}{2}}$ is $\lfloor \frac{q-1}{2}\rfloor + \lfloor \frac{k+3}{2}\rfloor$. Next consider the vertices from the region $R_{\frac{q+1}{2}}$. Now, because of the symmetry of P(n, k) for an even n, the vertex farthest from $u_0$ ($v_0)$ lie in the region $R_{\frac{q+1}{2}}$. The vertex farthest from $u_0$ and $v_0$ are the vertices $u_{\frac{n}{2}}$ and $v_{\frac{n}{2}}$, respectively, at a distance $\lfloor \frac{q+1}{2}\rfloor + \lfloor \frac{k}{2}\rfloor +1$, and hence the result.

   $\square$

Theorem 8

The generalized Petersen graph P(n, k) is not self-centered for $n = 4m( 4m+1)$ and $k = 2m (4m-1)$ for some positive integer $m \ge 1$.

Proof

In this case, we find that $v_{\frac{n}{2}}$ is the farthest vertex from both $u_0$ and $v_0$ and have obtained that $d(u_0,v_{\frac{n}{2}}) = 4m+2$ and $d(v_0,v_{\frac{n}{2}}) = 4m+1$. So, $e(u_0)= 4m+2$ and $e(v_0)=4m+1$ and hence the given generalized Petersen graphs are not self-centered in this case.    $\square$

3 Self-centeredness of P(n, k) for Odd n

In this section, we first investigate self-centeredness of P(n, k) for $k = 2$. First of all, we prove that P(5, 2) and P(7, 2) are self-centered graphs.

Theorem 9

The generalized Petersen graph P(n, 2) is 2- or 3-self-centered graphs for $n = 5$ or 7, respectively.

Proof

For $n = 5$, the graph P(n, 2) is the well known Petersen graph and we know that radius and diameter of P(5, 2) is two. Thus, P(5, 2) is 2-self-centered graph.

Let us consider the vertices $u_0$ and $v_0$ in P(7, 2). The shortest path from $u_0$ to $u_1,u_2,$ or $u_3$ is through the edges in cycle $C:u_0,u_1,u_2,u_3,u_4,u_5,u_6,u_0$. So we get that $d(u_0,u_1), d(u_0,u_2)$, and $d(u_0,u_3)$ are equal to 1, 2, and 3, respectively. A shortest $u_0$–$v_i$ path for $i = 0,1,2$, and 3 is $(u_0,v_0)$, $(u_0,u_1,v_1)$, $(u_0,v_0,v_2)$, and $(u_0,u_1,v_1,v_3)$ with lengths 1, 2, 2, and 3, respectively. Similarly, a shortest $v_0-u_i$ path for $i = 0,1,2$, and 3 is $(v_0,u_0)$, $(v_0,u_0,u_1)$, $(v_0,v_2,u_2)$, $(v_0,v_2,u_2,u_3)$ with lengths 1, 2, 2, and 3, respectively. Further, a shortest $v_0$–$v_i$ path for $i = 1,2$, and 3 is $(v_0,u_0,u_1,v_1)$, $(v_0,v_2)$, and $(v_0,v_5,v_3)$ with lengths 3, 1, and 2 respectively. From this we can say that $e(u_0) = e(v_0) = 3$. Hence P(7, 2) is a 3-self-centered graph.    $\square$

Theorem 10

The generalized Petersen graph P(n, 2) is not self-centered for odd integers $n \ge 9$.

Proof

We take $n=4m+1$ or $4m+3$ for some positive integer $m\ge 2$. We shall find $d(u_0,u_i)$, $d(u_0,v_i)$, $d(v_0,u_i)$, and $d(v_0,v_i)$ for $i \in \{1,2,\ldots ,\lfloor \frac{n}{2} \rfloor \}$. First, we consider the vertex $u_0$. We note that $d(u_0,u_i) = i$ for $i = 1,2,3,$ and 4.

For an even index i, $6\le i\le 2m$, a shortest $u_0$–$u_i$ and $u_0$–$v_i$ path is given by $P_i: u_0,v_0,v_2,v_4,\ldots ,v_i,u_i$ and $P'_i : u_0,v_0,v_2,\ldots ,v_i$, where $l(P_i) = \frac{i+4}{2}$ and $l(P'_i) = \frac{i+2}{2}$. Now,

$$\begin{aligned} \max \{l(P_i) : 6\le i\le 2m, i \text { even}\} = m+2. \end{aligned}$$

(27)

$$\begin{aligned} \max \{l(P'_i): 6\le i\le 2m, i \text { even}\} = m+1. \end{aligned}$$

(28)

For an odd index i, a shortest $u_0$–$u_i$ and $u_0$–$v_i$ path is given by $Q_i : u_0,v_0,v_2,v_4, \ldots ,v_{i-1},u_{i-1},u_i$ and $Q'_i : u_0,u_1,v_1,v_3,\ldots ,v_i$, where $l(Q_i) = \frac{i+5}{2}$ and $l(Q'_i) = \frac{i+3}{2}$. If $n = 4m+1$ then

$$\begin{aligned} \max \{l(Q_i) : 5\le i\le 2m-1, i \text { odd}\} = m+2 \end{aligned}$$

(29)

$$\begin{aligned} \max \{l(Q'_i): 5\le i\le 2m-1, i \text { odd}\} = m+1, \end{aligned}$$

(30)

and for $n=4m+3$, we get

$$\begin{aligned} \max \{l(Q_i) : 5\le i\le 2m+1, i \text { odd}\} = m+3 \end{aligned}$$

(31)

$$\begin{aligned} \max \{l(Q'_i): 5\le i\le 2m+1, i \text { odd}\} = m+2. \end{aligned}$$

(32)

Next, we consider the vertex $v_0$. For an even index i, $6\le i\le 2m$, a shortest $v_0$–$u_i$ and $v_0$–$v_i$ path is given by $L_i :v_0,v_2,v_4,\ldots ,v_i,u_i$ and $L'_i :v_0,v_2,v_4,\ldots ,v_i$, where $l(L_i) = \frac{i+2}{2}$ and $l(L'_i) = \frac{i}{2}$.

$$\begin{aligned} \max \{l(L_i) : 6\le i\le 2m, i \text { even}\} = m+1. \end{aligned}$$

(33)

$$\begin{aligned} \max \{l(L'_i): 6\le i\le 2m, i \text { even}\} = m. \,\,\,\,\, \end{aligned}$$

(34)

Next let i be an odd index. When $n =4m+1$, for $5\le i<2m-1$, a shortest $v_0$–$v_i$ path is given by $M_i :v_0,v_2,v_4,\ldots ,v_{i-1},u_{i-1},u_i,v_i$ and the length of the path $M_i$ is $\frac{i+5}{2}$, and for $i = 2m-1$, a shortest $v_0$–$v_i$ path is $M'_i : v_0,v_{4m-1},v_{4m-3},\ldots ,v_{4m-(2m+1)}$ with length $m+1$. When $n=4m+3$, for $5\le i<2m+1$, a shortest $v_0$–$v_i$ path is given by $N_i : v_0,v_2,v_4,\ldots ,v_{i-1},u_{i-1},u_i,v_i$ and the length of the path $N_i$ is $\frac{i+5}{2}$, and for $i = 2m+1$, a shortest $v_0$–$v_i$ path is $N'_i : v_0,v_{4m+1},v_{4m-1},v_{4m-3},\ldots ,v_{4m-(2m-1)}$ with length $m+1$. Now, we get the following.

$$\begin{aligned} \max \{l(M_i) : 5\le i\le 2m-3, i \text { odd}\} = m+1. \end{aligned}$$

(35)

$$\begin{aligned} \max \{l(N_i): 5\le i\le 2m-1, i \text { odd}\} = m+2. \end{aligned}$$

(36)

From the Eqs. (27)–(36), we have

$$\begin{aligned} e(u_0) = {\left\{ \begin{array}{ll}\nonumber m+2, &{} \text {for n = 4m+1} \\ m+3, &{} \text {for n = 4m+3}, \end{array}\right. } \end{aligned}$$

and

$$\begin{aligned} e(v_0) = {\left\{ \begin{array}{ll} m+1, &{} \text {for n = 4m+1} \\ m+2, &{} \text {for n = 4m+3} \end{array}\right. } \end{aligned}$$

Thus, $e(u_0)\ne e(v_0)$ and hence P(n, 2) is not self-centered graph.    $\square$

Corollary 1

The generalized Petersen graph P(n, k) is not self-centered for odd integers $n\ge 9$ and $k = \frac{n-1}{2}$.

Proof

By the structure of generalized Petersen graph, for an odd integer n we get that $P(n,\frac{n+1}{2})$ and $P(n,\frac{n-1}{2})$ are isomorphic. Since $\frac{n+1}{2}$ is relatively prime with n, and n is odd, by Theorem 1 we get P(n, 2) and $P(n, \frac{n+1}{2})$ are isomorphic and thus P(n, 2) and $P(n, \frac{n-1}{2})$ are isomorphic. Since, P(n, 2) is not a self-centered graph for $n\ge 9$ with odd n, $P(n, \frac{n-1}{2})$ is also not a self-centered graph and hence the result.    $\square$

In the next theorem we prove that the generalized Petersen graph is a self-centered graph when both n and k are odd, and n is divisible by k.

Fig. 3.

Generalized Petersen graph P(n, k) with both n and k odd, k divides n

Theorem 11

Let P(n, k) be a generalized Petersen graph, where n and k are both odd and k divides n. Then P(n, k) is a d-self-centered graph, where $d = \frac{q+k}{2}+1$ and $n=kq$.

Proof

Due to symmetric structure of P(n, k) we have $d(u_0,u_i) = d(u_0,u_{n-i})$ for $i \in \{ 1,2,\ldots ,\lfloor \frac{n}{2} \rfloor \}$. We consider the cycle $C: u_0,u_1,u_2,\ldots ,u_k,v_k,v_0,u_0$ of length $k+3$, see Fig. 3, where C is highlighted by thick lines. Since $u_0,v_0\in C$, we have

$$\begin{aligned} \max \{d(u_0,u_i) :u_i\in C\} = \max \{d(v_0,u_i):u_i\in C\} = \frac{k+3}{2}. \end{aligned}$$

(37)

Next, we determine $d(u_0,u_i)$, $d(u_0,v_i)$, $d(v_0,u_i)$, and $d(v_0,v_i)$, where $u_i$, $v_i\notin C$. Let $m = 1,2,\ldots ,\frac{q-1}{2} -1,\frac{q-1}{2}$. We have following cases depending on the values of i. In the first three cases, we consider $m = 1,2,\ldots ,\frac{q-1}{2} -1$, and in the fourth case we take $m = \frac{q-1}{2}$.

Case 1. $mk \le i < mk + \frac{k+1}{2}$, $m = 1,2,\ldots ,\frac{q-1}{2} -1$.

Since $mk\le i$, we can write $i = mk+j$ for $j = 0,1,2,\ldots ,\frac{k-1}{2}$. Now, a shortest $u_0$–$u_i$ and $v_0$–$u_i$ paths are given by the paths $P_1$ and $P_2$ respectively, where

$$\begin{aligned} \begin{array}{c} P_1 : u_0,v_0,v_k,v_{2k},\ldots ,v_{mk},u_{mk},u_{mk+1},\ldots ,u_{mk+j} \\ P_2 : v_0,v_k,v_{2k},\ldots ,v_{mk},u_{mk},u_{mk+1},\ldots ,u_{mk+j}. \end{array} \end{aligned}$$

Moreover, $l(P_1) = m+j+2$ and $l(P_2) = m+j+1$. Both $P_1$ and $P_2$ obtain their maximum length for $m = \frac{q-1}{2}-1$ and $j = \frac{k-1}{2}$, i.e.

$$\begin{aligned} \max \{l(P_1) : i < mk + \frac{k+1}{2}\} = \frac{q+k}{2}. \,\,\,\,\,\, \end{aligned}$$

(38)

$$\begin{aligned} \max \{l(P_2): i < mk + \frac{k+1}{2}\} = \frac{q+k}{2} -1. \end{aligned}$$

(39)

Similarly, a shortest $u_0$–$v_i$ and $v_0$–$v_i$ paths are given by $P_3$ and $P_4$, respectively, where

$$\begin{aligned} \begin{array}{c} P_3 : v_i,v_{i-k},v_{i-2k},v_{i-3k},\ldots ,v_{i-mk},u_{i-mk},u_{i-mk-1},\ldots ,u_0 \\ P_4 : v_0,v_k,v_{2k},\ldots ,v_{mk},u_{mk},u_{mk+1},\ldots ,u_{mk+j},v_{mk+j} \end{array} \end{aligned}$$

Now, $l(P_3) = 1+i-(k-1)m$ and $l(P_4) = m+j+2$. Length of path $P_3$ is maximum for $m = \frac{q-1}{2}-1$ and corresponding value of i i.e. $i = mk +\frac{k+1}{2}-1$. This gives

$$\begin{aligned} \max \{l(P_3)\} = \frac{q+k}{2} - 1. \end{aligned}$$

(40)

Also, the path $P_4$ obtains its optimum length for $m = \frac{q-1}{2}-1$ and $j = \frac{k-1}{2}$, i.e.

$$\begin{aligned} \max \{l(P_4)\} = \frac{q+k}{2}. \end{aligned}$$

(41)

Case 2. $mk + \frac{k+1}{2}<i < mk+k$, $m = 1,2,\ldots ,\frac{q-1}{2} -1$.

Since $mk + \frac{k+1}{2}< i <mk+k$, we write $i = mk + (k-x)$ for $x = 1,2,\ldots ,\frac{k-3}{2}$. A shortest $u_0$–$u_i$ and $v_0$–$u_i$ paths are given below.

$$\begin{aligned} \begin{array}{c} P_5 : u_0,v_0,v_k,v_{2k},\ldots ,v_{mk},v_{mk+k},u_{mk+k},u_{mk+(k-1)},u_{mk+(k-2)},\ldots ,u_{mk+(k-x)} \\ P_6 : v_0,v_k,v_{2k},\ldots ,v_{mk},v_{mk+k},u_{mk+k},u_{mk+(k-1)},u_{mk+(k-2)},\ldots ,u_{mk+(k-x)} \end{array} \end{aligned}$$

We see that $l(P_5) =3+m+x$ and $l(P_6) = 2+m+x$. Now, maximum length of the paths $P_5$ and $P_6$ are obtained when $m = \frac{q-1}{2}-1$ and $x = \frac{k-3}{2}$, respectively. Hence,

$$\begin{aligned} \max \{l(P_5)\} = \frac{q+k}{2} + 1, \text {and } \max \{l(P_6)\} = \frac{q+k}{2} - 1. \end{aligned}$$

(42)

Further, shortest $u_0$–$v_i$ and $v_0$–$v_i$ paths are given by $P_7$ and $P_8$, respectively, where

$$\begin{aligned}&P_7 : v_i,v_{i-k},v_{i-2k},\ldots ,v_{i-mk},v_{n+i-mk-k},u_{n+i-mk-k},u_{n+i-mk-k-1},u_{n+i-mk-k-2},\ldots ,u_0 \\&P_8 : v_0,v_k,v_{2k},v_{3k},\ldots ,v_{mk},v_{mk+k},u_{mk+k},u_{mk+(k-1)},u_{mk+(k-2)},\ldots ,u_{mk+(k-x)},v_{mk+(k-x)} \end{aligned}$$

Moreover, $l(P_7) = 2 + m + (m+1)k - i$ and $l(P_8) = 3 + m +x$, and so

$$\begin{aligned} \max \{l(P_7)\} = \frac{q+k}{2} - 1, \text {and } \max \{l(P_8)\} = \frac{q+k}{2}. \end{aligned}$$

(43)

Case 3. $i = mk + \frac{k+1}{2}$, $m = 1,2,\ldots ,\frac{q-1}{2} -1$.

In this case, a shortest $u_0$–$u_i$, $v_0$–$u_i$, $u_0$–$v_i$, and $v_0$–$v_i$ paths are given by the following paths $P_9$, $P_{10}$, $P_{11}$, and $P_{12}$, respectively, where

$$\begin{aligned}&P_9 : u_0,v_0,v_k,v_{2k},\ldots ,v_{mk},u_{mk},u_{mk+1},u_{mk+2},\ldots ,u_{mk+\frac{k+1}{2}}\\&P_{10} : v_0,v_k,v_{2k},\ldots ,v_{mk},u_{mk},u_{mk+1},u_{mk+2},\ldots ,u_{mk+\frac{k+1}{2}}\\&P_{11} : v_i,v_{i-k},v_{i-2k},\ldots ,v_{i-mk},u_{i-mk},u_{i-mk-1},u_{i-mk-2},\ldots ,u_0 \\&P_{12} : v_0,v_k,v_{2k},\ldots ,v_{mk},u_{mk},u_{mk+1},u_{mk+2},\ldots ,u_{mk+\frac{k+1}{2}},v_{mk+\frac{k+1}{2}}. \end{aligned}$$

Moreover, $l(P_9) = 2 + m +\frac{k+1}{2}$, $l(P_{10}) = 1 + m +\frac{k+1}{2}$, $l(P_{11}) = 1 + i - (k-1)m$, and $l(P_{12}) = 2 + m +\frac{k+1}{2}$. These paths attain their maximum length for $m = \frac{q-1}{2} - 1$, and hence we get

$$\begin{aligned}&\max \{l(P_9)\} = \frac{q+k}{2} + 1, \max \{l(P_{10})\} = \frac{q+k}{2}, \max \{l(P_{11})\} = \frac{q+k}{2},\nonumber \\&\text { and }\max \{l(P_{12})\} = \frac{q+k}{2} + 1 \end{aligned}$$

(44)

Case 4. $i = mk+l$ and $m = \frac{q-1}{2}$, where $l = 0,1,2,\ldots ,\lfloor \frac{k}{2}\rfloor$

Shortest $u_0$–$u_i$, $v_0$–$u_i$, and $v_0$–$v_i$ paths are given by:

$$\begin{aligned}&P_{13} : u_0,v_0,v_k,v_{2k},\ldots ,v_{(m+1)k},u_{(m+1)k},u_{(m+1)k+1},\ldots ,u_{(m+1)k+l}\\&P_{14} : v_0,v_k,v_{2k},\ldots ,v_{(m+1)k},u_{(m+1)k},u_{(m+1)k+1},\ldots ,u_{(m+1)k+l},\\&P_{15} : v_0,v_k,v_{2k},\ldots ,v_{(m+1)k},u_{(m+1)k},u_{(m+1)k+1},\ldots ,u_{(m+1)k+l},v_{(m+1)k+l}. \end{aligned}$$

We have $l(P_{13}) = 3 + m + l$, $l(P_{14}) = 2 + m + l$, and $l(P_{15}) = 3 + m + l$, respectively. Finally, the path $P_{16} : v_i,v_{i-k},v_{i-2k},\ldots ,v_{i-mk},u_{i-mk},u_{i-mk-1},$$u_{i-mk-2},\ldots ,u_0$ gives a shortest $u_0$–$v_i$ path and the length of the path $P_{16}$ is $1 + m + i - mk$. The path $P_{16}$ attains its maximum length for $m = \frac{q-1}{2}$ and $i = mk + \lfloor \frac{k}{2}\rfloor$, i.e.

$$\begin{aligned} \max \{l(P_{16})\} = \frac{q+k}{2}. \end{aligned}$$

(45)

From the Eqs. (38)–(45), we conclude that $e(u_0) = e(v_0) = \frac{q+k}{2}+1$. Thus, generalized petersen graph is a d-self-centered graph, where $d = \frac{q+k}{2}+1$.    $\square$

In the theorem given below, we investigate self-centeredness of P(n, k) for $n = m(4m+1 ) \pm ( m+1 )$ and $k = 4m + 1$.

Theorem 12

For $n = m(4m+1 )\pm (m+1)$, $k = 4m + 1$, and any positive integer $m \ge 2$, the generalized Petersen graph is not a self-centered graph.

Proof

We have following two cases here.

Case 1. $k = 4m + 1$ and $n = m(4m+1 ) + ( m+1 ) = 4m^2 + 2m + 1$ for any $m \ge 2$.

In this case, $v_{\frac{k-1}{2}}$ and $v_{n - (\frac{k-1}{2})}$ are equivalently most distant vertices from $u_0$ as well as $v_0$ and their path lengths are $\frac{k-1}{2}$ and $\frac{k-1}{2} + 1$, respectively. This implies that, $e(u_0) = \frac{k-1}{2}$ and $e(v_0) = \frac{k-1}{2}+1$ and they differ by one.

Case 2. $k = 4m + 1$ and $n = m(4m+1 ) - ( m+1 ) = 4m^2 - 1$ for any $m\ge 2$.

In this case, $v_{\frac{k+1}{2}}$ and $v_{n - (\frac{k+1}{2})}$ are equivalently most distant vertices from $u_0$ as well as $v_0$ and their path lengths are $\frac{k+1}{2}$ and $\frac{k+1}{2} + 1$, respectively. This implies that, $e(u_0) = \frac{k+1}{2}$ and $e(v_0) = \frac{k+1}{2}+1$ and the eccentricities differ by one.

In both the above cases we get that $e(u_0) \ne e(v_0)$. Hence, the generalized Petersen graph is not a self-centered.    $\square$

4 Computer Search and Concluding Remarks

We made an exhaustive computer search and found all possible values of n and k for which P(n, k) are non self-centered. In this search, we have discarded isomorphs of these generalized Petersen graphs using Theorem 1. We list all non-isomorphic generalized Petersen graphs in Tables 1 and 2 and address their theoretical proofs obtained in this paper.

Table 1. Non-self-centeredness of P(n, k), n odd

Table 2. Non-self-centeredness of P(n, k), n even

For complete characterization, one has to prove theoretically that all generalized Petersen graphs P(n, k) other than those in Tables 1 and 2, and their isomorphs are self-centered. Hence, we make the following conjecture.

Conjecture: The generalized Petersen graphs P(n, k) other than those in Tables 1 and 2 and their isomorphs are self-centered.