Abstract
We determine the maximum size of a graph of given order, diameter, and edge-connectivity λ for 2 ≤ λ≤ 7. This completes the determination of the maximum size of graphs with given order, diameter and edge-connectivity λ which had previously been done for λ= 1 and λ≥ 8. We further prove that upper bounds on the size of a graph of given order and diameter having certain additional properties can be extended to Eulerian digraphs, provided the additional properties satisfy some mild conditions. As an application of this result we prove that upper bounds on the size of graphs with given order, diameter and either edge-connectivity, connectivity, or minimum degree can be extended to Eulerian digraphs.
Original language | English |
---|---|
Pages (from-to) | 178-199 |
Number of pages | 22 |
Journal | Acta Mathematica Hungarica |
Volume | 164 |
Issue number | 1 |
DOIs | |
Publication status | Published - Jun 2021 |
Keywords
- Eulerian digraph
- connectivity
- diameter
- digraph
- edge-connectivity
- graph
ASJC Scopus subject areas
- General Mathematics