2025/09/01 by Sonwabile Mafunda, Mafunda, Sonwabile
Computer Science · #Interconnection Networks and Systems #Advanced Graph Theory Research #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2509.01825
In the first part of this paper we determine the maximum size of a (finite, simple, connected) bipartite graph of given order, diameter d, and connectivity κ. It was shown by Ali, Mazorodze, Mukwembi and Vetrík [On size, order, diameter and edge-connectivity of graphs. Acta Math. Hungar. \bf 152, (2017)] that for a connected triangle-free graph of order n, diameter d and edge-connectivity λ, the size is bounded from above by about (1)/(4)(n-((λ+c) d)/(2))2+O(n), where c∈\0, (1)/(3), 1\ for different values of λ. In the second part of this paper we show that this bound by Ali et al. on the size can be improved significantly for a much larger subclass of triangle-free graphs, namely, bipartite graphs of order n, diameter d and edge-connectivity λ. We prove our result only for λ= 2, 3, 4 because it can be observed from this paper by Ali et al. that for λ≥ 5, there exists ℓ-edge-connected bipartite graphs of given order and diameter whose size differs from the maximal size for given minimum degree ℓ only by at most a constant. Also, unlike the approach in the proof on the size of triangle-free graphs by Ali et al., our proof employs a completely different technique, which enables us to identify the extremal graphs; hence the bounds presented here are sharp.