Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 2 (2009) 41–47
The strongly distance–balanced property of
the generalized Petersen graphs∗
Klavdija Kutnar
University of Primorska, FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia
Aleksander Malnič
University of Ljubljana, IMFM, Jadranska 19, 1111 Ljubljana, Slovenia
Dragan Marušič †
University of Primorska, FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia
and
University of Ljubljana, IMFM, Jadranska 19, 1111 Ljubljana, Slovenia
Štefko Miklavič
University of Primorska, FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia
Received 15 July 2008, accepted 1 January 2009, published online 13 March 2009
Abstract
A graph X is said to be strongly distance–balanced whenever for any edge uv of X
and any positive integer i, the number of vertices at distance i from u and at distance i + 1
from v is equal to the number of vertices at distance i + 1 from u and at distance i from
v. It is proven that for any integers k ≥ 2 and n ≥ k2 + 4k + 1, the generalized Petersen
graph GP(n, k) is not strongly distance–balanced.
Keywords: Graph, strongy distance–balanced, generalized Petersen graph.
Math. Subj. Class.: 05C07, 05C12
∗Supported in part by “Agencija za raziskovalno dejavnost Republike Slovenije”, research program P1-0285
†Corresponding author.
E-mail addresses: klavdija.kutnar@upr.si (Klavdija Kutnar), aleksander.malnic@guest.arnes.si (Aleksander
Malnič), dragan.marusic@upr.si (Dragan Marušič), stefko.miklavic@upr.si (Štefko Miklavič)
Copyright c© 2009 DMFA
42 Ars Math. Contemp. 2 (2009) 41–47
1 Introduction
Let X be a graph with diameter d, and let V (X) and E(X) denote the vertex set and the
edge set of X , respectively. For u, v ∈ V (X), we let d(u, v) denote the minimal path-
length distance between u and v. We say that X is distance–balanced whenever for an
arbitrary pair of adjacent vertices u and v of X
|{x ∈ V (X) | d(x, u) < d(x, v)}| = |{x ∈ V (X) | d(x, v) < d(x, u)}|
holds. These graphs were, at least implicitly, first studied by Handa [1] who considered
distance–balanced partial cubes. The term itself, however, is due to Jerebic, Klavžar and
Rall [3] who studied distance–balanced graphs in the framework of various kinds of graph
products.
Let uv be an arbitrary edge of X . For any two nonnegative integers i, j, we let
Dij(u, v) = {x ∈ V (X) | d(u, x) = i and d(v, x) = j}.
The triangle inequality implies that only the sets Di−1i (u, v), D
i
i(u, v) and D
i
i−1(u, v)
(1 ≤ i ≤ d) can be nonempty. One can easily see that X is distance–balanced if and only
if for every edge uv ∈ E(X)
d∑
i=1
|Dii−1(u, v)| =
d∑
i=1
|Di−1i (u, v)| (1.1)
holds.
Obviously, if |Dii−1(u, v)| = |D
i−1
i (u, v)| holds for 1 ≤ i ≤ d and for every edge
uv ∈ E(X), then X is distance–balanced. The converse, however, is not necessarily
true. For instance, in the generalized Petersen graphs GP(24, 4), GP(35, 8) and GP(35, 13)
(see Section 2 for the definition of generalized Petersen graphs), we can find two adjacent
vertices u, v and an integer i, such that |Dii−1(u, v)| 6= |D
i−1
i (u, v)|. But it is easy to see
that these graphs are distance–balanced.
We therefore say that X is strongly distance–balanced, if |Dii−1(u, v)| = |D
i−1
i (u, v)|
for every positive integer i and every edge uv ∈ E(X). Let us remark that graphs with
this property are also called distance–degree regular. Distance–degree regular graphs were
studied in [2].
For a graph X , a vertex u of X and an integer i, let Si(u) = {x ∈ V (X) | d(x, u) = i}
denote the set of vertices of X which are at distance i from u. The following result was
proven in [4].
Proposition 1.1. [4, Proposition 2.1] Let X be a graph with diameter d. Then X is strongly
distance–balanced if and only if |Si(u)| = |Si(v)| holds for every edge uv ∈ E(X) and
every i ∈ {0, . . . , d}.
In [3], the following conjecture was stated.
Conjecture 1.2. [3, Conjecture 2.5] For any integer k ≥ 2 there exists a positive integer
n0 such that the generalized Petersen graph GP(n, k) is not distance–balanced for every
integer n ≥ n0.
In this short note we prove the following slightly weaker result.
K. Kutnar et al.: The strongly distance–balanced property of the generalized Petersen graphs 43
Theorem 1.3. For any integers k ≥ 2 and n ≥ k2 + 4k + 1, the generalized Petersen
graph GP(n, k) is not strongly distance–balanced.
We will prove Theorem 1.3 in two steps. In the first step we prove that the graph
GP(k2 + 4k + 1, k) is not strongly distance–balanced. In the second step we use the
result from the first step to prove that GP(n, k) is not strongly distance-balanced if n ≥
k2 + 4k + 1.
2 Proof of Theorem 1.3
Let n ≥ 3 be a positive integer, and let k ∈ {1, . . . , n − 1} \ {n/2}. The generalized
Petersen graph GP(n, k) is defined to have the following vertex set and edge set:
V (GP(n, k)) = {ui | i ∈ Zn} ∪ {vi | i ∈ Zn},
E(GP(n, k)) = {uiui+1 | i ∈ Zn} ∪ {vivi+k | i ∈ Zn} ∪ {uivi | i ∈ Zn}. (2.1)
Note that GP(n, k) is cubic, and that it is bipartite precisely when n is even and k is odd.
It is easy to see that GP(n, k) ∼= GP(n, n − k). Furthermore, if the multiplicative inverse
k−1 of k exists in Zn, then the mapping f : V (GP(n, k)) → V (GP(n, k−1)) defined by
the rule
f(ui) = vk−1i, f(vi) = uk−1i (2.2)
gives rise to an isomorphism of graphs GP(n, k) and GP(n, k−1), where the use of the
same symbols for vertices in GP(n, k) and GP(n, k−1) should cause no confusion.
We first investigate the sets Si(u0) and Si(v0) of the graph GP(k2 + 4k + 1, k).
Lemma 2.1. Let k ≥ 9 be an integer, let n = k2 +4k+1 and let u0 ∈ V (GP(n, k)). Then
the following statements hold:
(i) S1(u0) = {u±1, v0}, S2(u0) = {u±2, v±1, v±k},
S3(u0) = {u±3, u±k, v±2, v±(k+1), v±(k−1), v±2k};
(ii) if i ∈ {4, . . . , bk/2c+ 1}, then
Si(u0) = {u±i, u±(i−2)k} ∪ {v±(i−1), v±(i−1)k} ∪
{u±(lk+i−l−2), u±(lk−i+l+2) | 1 ≤ l ≤ i− 3} ∪
{v±(lk+i−l−1), v±(lk−i+l+1) | 1 ≤ l ≤ i− 2};
(iii) if k is odd, then
S(k+3)/2(u0) = {u±(k+3)/2, u±(k−1)k/2, u±(3k−3)/2} ∪
{u±(lk+(k−1)/2−l), u±(lk−(k−1)/2+l) | 2 ≤ l ≤ (k − 3)/2} ∪
{v±(k+1)/2, v±(k+1)k/2, v±(3k−1)/2} ∪
{v±(lk+(k+1)/2−l), v±(lk−(k+1)/2+l) | 2 ≤ l ≤ (k − 1)/2};
(iv) if k is even, then
S(k+4)/2(u0) = {u±k2/2, u±(3k−2)/2} ∪
{u±(lk+k/2−l), u±(lk−k/2+l) | 2 ≤ l ≤ (k − 2)/2} ∪
{v±3k/2, v±(k+2)k/2} ∪
{v±(lk+3k/2−l), v±(lk+k/2+l) | 1 ≤ l ≤ (k − 2)/2}.
44 Ars Math. Contemp. 2 (2009) 41–47
Proof. Using the fact that by assumption k ≥ 9, a careful inspection of the neighbors’ sets
of vertices ui and vi, we see that (i) holds.
We now prove part (ii) by induction. Similarly as above we see that (ii) holds for
i ∈ {4, 5}.
Let us now assume that (ii) holds for i− 1 and i, where i ∈ {5, . . . , bk/2c}. Hence we
have
Si−1(u0) = {u±(i−1), u±(i−3)k} ∪ {u±(lk+i−l−3), u±(lk−i+l+3) | 1 ≤ l ≤ i− 4} ∪
{v±(i−2), v±(i−2)k} ∪ {v±(lk+i−l−2), v±(lk−i+l+2) | 1 ≤ l ≤ i− 3}
and
Si(u0) = {u±i, u±(i−2)k} ∪ {u±(lk+i−l−2), u±(lk−i+l+2) | 1 ≤ l ≤ i− 3} ∪
{v±(i−1), v±(i−1)k} ∪ {v±(lk+i−l−1), v±(lk−i+l+1) | 1 ≤ l ≤ i− 2}.
Now we compute the neighbors of the vertices belonging to the set Si(u0). Since
S1(u−r) = {u−q, v−q | uq, vq ∈ S1(ur)} and
S1(v−r) = {u−q, v−q | uq, vq ∈ S1(vr)},
we will only list the following sets:
- S1(ui) = {ui+1, ui−1, vi},
- S1(u(i−2)k) = {u(i−2)k+(i+1)−(i−2)−2, u(i−2)k−(i+1)+(i−2)+2, v(i−2)k},
- S1(ulk+i−l−2) = {ulk+(i+1)−l−2, ulk+(i−1)−l−2, vlk+(i−1)−l−1},
- S1(ulk−i+l+2) = {ulk−(i−1)+l+2, ulk−(i+1)+l+2, vlk−(i−1)+l+1},
- S1(vi−1) = {ui−1, vk+(i+1)−2, v−(k−(i+1)+2)},
- S1(v(i−1)k) = {u(i−1)k, vik, v(i−2)k},
- S1(vlk+i−l−1) = {ulk+(i+1)−l−2, v(l+1)k+(i+1)−(l+1)−1, v(l−1)k+(i−1)−(l−1)−1},
- S1(vlk−i+l+1) = {ulk−(i+1)+l+2, v(l+1)k−(i+1)+(l+1)+1, v(l−1)k−(i−1)+(l−1)+1}.
Obviously, Si+1(u0) consists of all the neighbors of vertices in Si(u0), which are not in
Si−1(u0) or Si(u0). Thus
Si+1(u0) = {u±(i+1), u±(i−1)k} ∪
{u±(lk+(i+1)−l−2), u±(lk−(i+1)+l+2) | 1 ≤ l ≤ i− 2} ∪
{v±i, v±ik} ∪ {v±(lk+(i+1)−l−1), v±(lk−(i+1)+l+1) | 1 ≤ l ≤ i− 1}
and the result follows.
Let us now prove (iii). Assume first k is odd, and abbreviate b = (k + 1)/2. By (ii),
Sb−1(u0) = {u±(b−1), u±(b−3)k} ∪ {u±(lk+b−l−3), u±(lk−b+l+3) | 1 ≤ l ≤ b− 4} ∪
{v±(b−2), v±(b−2)k} ∪ {v±(lk+b−l−2), v±(lk−b+l+2) | 1 ≤ l ≤ b− 3}
K. Kutnar et al.: The strongly distance–balanced property of the generalized Petersen graphs 45
and
Sb(u0) = {u±b, u±(b−2)k} ∪ {u±(lk+b−l−2), u±(lk−b+l+2) | 1 ≤ l ≤ b− 3} ∪
{v±(b−1), v±(b−1)k} ∪ {v±(lk+b−l−1), v±(lk−b+l+1) | 1 ≤ l ≤ b− 2}.
Let us now compute the neighbors of the vertices in Sb(u0). Since S1(u−r) = {u−q, v−q |
uq, vq ∈ S1(ur)} and S1(v−r) = {u−q, v−q | uq, vq ∈ S1(vr)}, we will only list the
following sets:
- S1(ub) = {ub+1, ub−1, vb},
- S1(u(b−2)k) = {u(b−2)k+(b+1)−(b−2)−2, u(b−2)k−(b+1)+(b−2)+2, v(b−2)k},
- S1(ulk+b−l−2) = {ulk+b−l−1, ulk+b−l−3, vlk+b−l−2},
- S1(ulk−b+l+2) = {ulk−b+l+3, ulk−b+l+1, vlk−b+l+2},
- S1(vb−1) = {ub−1, vk+b−1, v−(k−b+1)} = {ub−1, vk+b−1, v−b},
- S1(v(b−1)k) = {u(b−1)k, vbk, v(b−2)k},
- S1(vlk+b−l−1) = {ulk+b−l−1, v(l+1)k+b−l−1, v(l−1)k+b−l−1},
- S1(vlk−b+l+1) = {ulk−b+l+1, v(l+1)k−b+l+1, v(l−1)k−b+l+1}.
Observe that u±(k−b+2) = u±(b+1). Therefore, sorting out those neigbors of the vertices
in Sb(u0) which are either in Sb−1(u0) or Sb(u0), we obtain that
Sb+1(u0) = {u±(b+1), u±(b−1)k, u±(k+b−2)} ∪
{u±(lk+b−l−1), u±(lk−b+l+1) | 2 ≤ l ≤ b− 2} ∪
{v±b, v±bk, v±(k+b−1)} ∪ {v±(lk+b−l), v±(lk−b+l) | 2 ≤ l ≤ b− 1}
and hence the result follows.
The proof of (iv) is done in a similar way to that of (iii) above and is omitted.
We have the following immediate corollary of Lemma 2.1.
Corollary 2.2. Let k ≥ 9 be an integer, let n = k2 + 4k + 1 and let u0 ∈ V (GP(n, k)).
Then the following statements hold:
(i) |S1(u0)| = 3, |S2(u0)| = 6, |S3(u0)| = 12;
(ii) |Si(u0)| = 8i− 12 for i ∈ {4, . . . , bk/2c+ 1};
(iii) if k is odd, then |S(k+3)/2(u0)| = 4k − 4;
(iv) if k is even, then |S(k+4)/2(u0)| = 4k − 4.
The proofs of the next lemma and corollary are omitted as they can be carried out using
the same arguments as in the proof of Lemma 2.1. (Note that−(k +4) is the multiplicative
inverse of k in Zk2+4k+1.)
Lemma 2.3. Let k ≥ 9 be an integer, let n = k2 + 4k + 1, and let u0 ∈ V (GP(n, k + 4)).
Then the following statements hold:
(i) S1(u0) = {u±1, v0}, S2(u0) = {u±2, v±1, v±(k+4)},
S3(u0) = {u±3, u±(k+4), v±2, v±(k+5), v±(k+3), v±2(k+4)};
46 Ars Math. Contemp. 2 (2009) 41–47
(ii) if i ∈ {4, . . . , bk/2c+ 1}, then
Si(u0) = {u±i, u±(i−2)(k+4)} ∪ {v±(i−1), v±(i−1)(k+4)} ∪
{u±(lk+i+3l−2), u±(lk−i+5l+2) | 1 ≤ l ≤ i− 3} ∪
{v±(lk+i+3l−1), v±(lk−i+5l+1) | 1 ≤ l ≤ i− 2};
(iii) if k is odd, then
S(k+3)/2(u0) = {u±(k+3)/2, u±(k−1)(k+4)/2} ∪
{u±(lk+(k−1)/2+3l), u±(lk−(k−1)/2+5l) | 1 ≤ l ≤ (k − 3)/2} ∪
{v±(k+1)/2, v±(k+1)(k+4)/2, v±(k2+3k−6)/2} ∪
{v±(lk+(k+1)/2+3l), v±(lk−(k+1)/2+5l) | 1 ≤ l ≤ (k − 3)/2};
(iv) if k is even, then
S(k+4)/2(u0) = {u±(k+4)/2, u±k(k+4)/2} ∪
{u±(lk+k/2+3l), u±(lk−k/2+5l) | 1 ≤ l ≤ (k − 2)/2} ∪
{v±(k+2)/2, v±(k+2)2/2} ∪
{v±(lk+(k+2)/2+3l), v±(lk−(k+2)/2+5l) | 1 ≤ l ≤ (k − 2)/2}.
Corollary 2.4. Let k ≥ 9 be an integer, let n = k2 +4k+1 and let u0 ∈ V (GP(n, k+4)).
Then the following statements hold:
(i) |S1(u0)| = 3, |S2(u0)| = 6, |S3(u0)| = 12;
(ii) |Si(u0)| = 8i− 12 for i ∈ {4, . . . , bk/2c+ 1};
(iii) if k is odd, then |S(k+3)/2(u0)| = 4k − 2;
(iv) if k is even, then |S(k+4)/2(u0)| = 4k.
Corollary 2.5. Let k ≥ 2 be an integer, let n = k2 + 4k + 1, let b = bk/2c + 2 and let
u0, v0 ∈ V (GP(n, k)). Then |Sb(u0)| 6= |Sb(v0)|. In particular, GP(n, k) is not strongly
distance–balanced.
Proof. If k ≤ 8, then a direct check shows that |Sb(u0)| 6= |Sb(v0)|. Assume now k ≥ 9.
Note that−(k +4) = n− (k +4) ∈ Zn is the multiplicative inverse of k ∈ Zn. Therefore,
by (2.2), we have
GP(n, (k + 4)) ∼= GP(n,−(k + 4)) ∼= GP(n, k).
Under this isomorphism, the vertex u0 ∈ V (GP(n, (k + 4))) maps to the vertex v0 ∈
V (GP(n, k)). (Recall that the same symbols are used for vertices in GP(n, k) and in
GP(n, (k + 4)).) The result now follows from Corollaries 2.2 and 2.4.
We are now ready to prove our main result.
Proof of Theorem 1.3. Let k ≥ 2 be an integer, let n0 = k2 + 4k + 1, let n ≥ n0, and let
b = bk/2c + 2. We now show that GP(n, k) is not strongly distance–balanced. In what
follows, the same symbols are used for vertices in GP(n0, k) and those in GP(n, k).
Observe that kb < n0/2. By (2.1), for i ∈ {1, 2, . . . , b}we have that uj ∈ V (GP(n, k))
(vj ∈ V (GP(n, k)), respectively) is at distance i from u0 ∈ V (GP(n, k)) if and only
if uj ∈ V (GP(n0, k)) (vj ∈ V (GP(n0, k)), respectively) is at distance i from u0 ∈
V (GP(n0, k)). Therefore, the number of vertices which are at distance i from u0 ∈
K. Kutnar et al.: The strongly distance–balanced property of the generalized Petersen graphs 47
V (GP(n, k)) is the same as the number of vertices which are at distance i from u0 ∈
V (GP(n0, k)). Similarly, for i ∈ {1, 2, . . . , b}, we have that uj ∈ V (GP(n, k)) (vj ∈
V (GP(n, k)), respectively) is at distance i from v0 ∈ V (GP(n, k)) if and only if uj ∈
V (GP(n0, k)) (vj ∈ V (GP(n0, k)), respectively) is at distance i from v0 ∈ V (GP(n0, k)).
Hence the number of vertices which are at distance i from the vertex v0 ∈ V (GP(n, k)) is
the same as the number of vertices which are at distance i from the vertex v0 ∈ V (GP(n0,
k)). Therefore, by Corollary 2.5, |Sb(u0)| 6= |Sb(v0)| for u0, v0 ∈ V (GP(n, k)). By
Proposition 1.1, GP(n, k) is not strongly distance–balanced.
References
[1] K. Handa, Bipartite graphs with balanced (a, b)-partitions, Ars Combin. 51 (1999), 113–119.
[2] T. Hilado and K. Nomura, Distance Degree Regular Graphs, J. Combin. Theory B 37 (1984),
96–100.
[3] J. Jerebic, S. Klavžar, D. F. Rall, Distance–balanced graphs, Ann. Combin. 12 (2008), 71–79.
[4] K. Kutnar, A. Malnič, D. Marušič, Š. Miklavič, Distance–balanced graphs: symmetry conditions,
Discrete Math. 306 (2006), 1881–1894.