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)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | 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 |
scientific article |
Statements
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 (English)
0 references
3 August 2021
0 references
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}\).
0 references
undirected graph
0 references
cubic graph
0 references
diameter of a graph
0 references
0 references
0 references
0 references