The Problem of a Symmetric Graph with a Maximum Number of Vertices and Minimum Diameter
Andrei M. Sukhov, A. Yu. Romanov, Aleksandr A. Amerikanov · Lobachevskii Journal of Mathematics · 2023
The paper gives a solution for the problem of the topology of the communication subsystem graph for high-performance multi-core computing systems. In this graph, each vertex is connected to four neighbors, and the number of vertices is the maximum for a given graph diameter. The solution to this problem is the family of circulants $$C(2D(D+1)+1;1,2D+1)$$ , $$D$$ is diameter. This graph is invariant under transforming its arbitrary vertex into any other, and its vertices are located densely in the vicinity of the root vertex, which determines its compliance with the diameter optimality criterion. All statements formulated during the solution of the problem are proven.