Explicit 𝑁-vertex graphs with maximum degree 𝐾 and diameter [1+𝑜(1)]log 𝐾-1 𝑁 for each 𝐾-1 a prime power

DOI10.1145/3313276.3316399zbMath1437.05111OpenAlexW2949481032MaRDI QIDQ5212858

Michael Capalbo

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3313276.3316399

zbMATH Keywords

explicit constructionsextremal graph theory

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Related Items (1)

An explicit infinite family of \(\mathbb{M}\)-vertex graphs with maximum degree \(K\) and diameter \([1+o(1)\log_{K-1}\mathbb{M}\) for each \(K-1\) a prime power]

This page was built for publication: Explicit 𝑁-vertex graphs with maximum degree 𝐾 and diameter [1+𝑜(1)]log _𝐾-1 𝑁 for each 𝐾-1 a prime power