On the connectivity of bipartite distance-balanced graphs

A connected graph ΓΓ is said to be distance-balanced   whenever for any pair of adjacent vertices u,vu,v of ΓΓ the number of vertices closer to uu than to vv is equal to the number of vertices closer to vv than to uu. In [K. Handa, Bipartite graphs with balanced (a,b)(a,b)-partitions, Ars Combin.51 (1999), 113–119] Handa asked whether every bipartite distance-balanced graph, that is not a cycle, is 3-connected. In this paper the Handa question is answered in the 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≥3k≥3 there exists an infinite family of such graphs which are kk-regular.Furthermore, we determine a number of structural properties that a bipartite distance-balanced graph, which is not 3-connected, must have. As an application, we give a positive answer to the Handa question for the subfamily of bipartite strongly distance-balanced graphs.