The largest graphs with given order and diameter: A simple proof

2018/11/10 by Pu Qiao, Qiao, Pu, Xingzhi Zhan +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1811.05314

openalex publication_date 2018/11/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A consequence of Ore's classic theorem characterizing the maximal graphs with given order and diameter is a determination of the largest such graphs. We give a very short and simple proof of this smaller result, based on a well-known elementary observation.

Related

• A simple proof of Ore's theorem on the maximum size of k-connected graphs with given order and diameter
• New large graphs with given degree and diameter
• The maximum size of a graph with prescribed order, circumference and minimum degree
• The maximum size of a nonhamiltonian-connected graph with given order and minimum degree
• Table of large graphs with given degree and diameter