On 2-distance-balanced graphs

2013-05-27
10:00-11:00
FAMNIT-SEMIN (Kettejeva 1, Koper)
Boštjan Frelih
On 2-distance-balanced graphs

 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.

This is a joint work with  Štefko Miklavič.