On the connectivity of bipartite distance-balanced graphs

DOI10.1016/J.EJC.2011.10.002zbMATH Open1233.05129arXiv1102.0127OpenAlexW2039960133MaRDI QIDQ658007FDOQ658007

Authors: Štefko Miklavič, Primož Šparl 

Publication date: 11 January 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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.} {�f 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 $kgeq3$ there exists an infinite family of such graphs which are $k$-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.

Full work available at URL: https://arxiv.org/abs/1102.0127

Recommendations

• On distance-balanced graphs
• On some problems regarding distance-balanced graphs
• The \(k\)-restricted edge connectivity of balanced bipartite graphs
• scientific article; zbMATH DE number 4051668
• scientific article; zbMATH DE number 1390507
• On 2-distance-balanced graphs
• \(\ell\)-distance-balanced graphs
• Further results on distance-balanced graphs
• On extremal bipartite graphs with a given connectivity
• On the distance connectivity of graphs and digraphs

zbMATH Keywords

minimal bipartite distance-balanced graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Connectivity (05C40)

Cites Work

• Distance-preserving subgraphs of hypercubes
• On distance-balanced graphs
• Bipartite graphs with balanced \((a,b)\)-partitions
• Distance-balanced graphs
• Distance-balanced graphs: symmetry conditions
• Strongly distance-balanced graphs and graph products
• Distance degree regular graphs
• The strongly distance-balanced property of the generalized Petersen graphs

Cited In (16)

• Status connectivity indices and co-indices of graphs and its computation to some distance-balanced graphs
• Equal opportunity networks, distance-balanced graphs, and Wiener game
• Quasi-\(\lambda\)-distance-balanced graphs
• On \(\ell\)-distance-balanced product graphs
• \(\ell\)-distance-balanced graphs
• On the new extension of distance-balanced graphs
• On some properties of edge quasi-distance-balanced graphs
• Nicely distance-balanced graphs
• On some properties of quasi-distance-balanced graphs
• Bipartite graphs with balanced \((a,b)\)-partitions
• On distance-balanced generalized Petersen graphs
• On some problems regarding distance-balanced graphs
• On 2-distance-balanced graphs
• Title not available (Why is that?)
• Further remarks on \(n\)-distance-balanced graphs
• On certain regular nicely distance-balanced graphs

This page was built for publication: On the connectivity of bipartite distance-balanced graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q658007)