Size of graphs and digraphs with given diameter and connectivity constraints

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)178-199
Number of pages22
JournalActa Mathematica Hungarica
Volume164
Issue number1
DOIs
Publication statusPublished - Jun 2021

Keywords

  • Eulerian digraph
  • connectivity
  • diameter
  • digraph
  • edge-connectivity
  • graph

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Size of graphs and digraphs with given diameter and connectivity constraints'. Together they form a unique fingerprint.

Cite this