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 (Q2043762)

The solution of a long-standing open question is presented by giving an explicit construction of an infinite family of \(\mathbb{M}\)-vertex cubic graphs that have diameter \([1+o(1)]\log_{K-1}\mathbb{M}\). For every \(K = p^s + 1\), where \(p\) is any prime number (including \(2\)) and \(s\) any positive integer, the author extends the techniques to construct an infinite family of \(K\)-regular graphs on \(\mathbb{M}\) vertices with diameter \([1+o(1)]\log_{K-1}\mathbb{M}\).