19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Not all bipartite distance-balanced graphs are $3$-connected
Presented by Dr. Primož ŠPARL
Type: Oral presentation
Track: General session
Content
A connected graph $\G$ is said to be {\it distance-balanced} whenever for any pair of adjacent vertices $u,v$ of
$\G$ the number of vertices closer to $u$ than to $v$ is equal to the number of vertices closer to $v$ than to $u$.
In [Bipartite graphs with balanced $(a,b)$-partitions, {\em Ars Combin.} {\bf 51} (1999), 113--119]
Handa asked whether every bipartite distance-balanced graph that is not a cycle is 3-connected.
In this talk we show that the answer to the Handa question is negative. Moreover, we show that a minimal
bipartite distance-balanced graph that is not a cycle and is not 3-connected has $18$ vertices and is unique.
In addition, we give a complete classification of non-$3$-connected bipartite distance-balanced graphs for which the minimal distance between
two vertices in a $2$-cut is three. All such graphs are regular and for each $k \geq 3$ there exists an infinite family of such graphs which are $k$-regular.
Joint work with \v Stefko Miklavi\v c
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled