The strongly distance-balanced property of the generalized Petersen graphs

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 ≥ k² + 4k + 1, the generalized Petersen graph GP(n, k) is not strongly distance-balanced.