Description
A graph X is said to be distance-balanced if for any edge uv of X, the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. These graphs were, at least implicitly, first studied by Handa who considered distance-balanced partial cubes. The term itself, however, is due to Jerebic, Klavžar, and Rall who studied distance-balanced graphs in the framework of various kinds of graph products.
We can generalize the definition of distance-balanced graphs to n-distance-balanced as follows. A graph X is said to be n-distance-balanced if for any two vertices u and v of X 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 talk we present some results about 2-distance-balanced graphs. In particular, we present the characterization of connected 2-distance-balanced graphs which are not 2-connected, and characterizations of 2-distance-balanced cartesian and lexicographic products of two graphs.
Primary author
Dr
Boštjan Frelih
(University of Primorska)
