On 2-distance-balanced graphs

Abstract

Let n denote a positive integer. A graph Γ of diameter at least n is said to be n-distance-balanced whenever for any pair of vertices u, v of Γ at distance n, the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. In this article we consider n = 2 (e.g. we consider 2-distance-balanced graphs). We show that there exist 2-distance-balanced graphs that are not 1-distance-balanced (e.g. distance-balanced). We characterize all connected 2-distance-balanced graphs that are not 2-connected. We also characterize 2-distance-balanced graphs that can be obtained as cartesian product or lexicographic product of two graphs.