Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.01825 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916929860534272 |
|---|---|
| author | Mafunda, Sonwabile |
| author_facet | Mafunda, Sonwabile |
| contents | 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 $\frac{1}{4}\left(n-\frac{(λ+c) d}{2}\right)^2+O(n)$, where $c\in\{0, \frac{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 $λ\geq 5$, there exists $\ell$-edge-connected bipartite graphs of given order and diameter whose size differs from the maximal size for given minimum degree $\ell$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_01825 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Size of bipartite graphs with given diameter and connectivity constraints Mafunda, Sonwabile Combinatorics 05C12 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 $\frac{1}{4}\left(n-\frac{(λ+c) d}{2}\right)^2+O(n)$, where $c\in\{0, \frac{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 $λ\geq 5$, there exists $\ell$-edge-connected bipartite graphs of given order and diameter whose size differs from the maximal size for given minimum degree $\ell$ 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. |
| title | Size of bipartite graphs with given diameter and connectivity constraints |
| topic | Combinatorics 05C12 |
| url | https://arxiv.org/abs/2509.01825 |