19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details
PDF | XML

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

Primary authors

More