Applied Graph Theory

On the problem of circulant networks with the maximal number of nodes for any diameter

E. A. Monakhova, O. G. Monakhov

Institute of Computational Mathematics and Mathematical Geophysics (Computing Center), Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia

Abstract: For undirected circulant networks, the problem of the maximal reachable number of nodes under given dimension and diameter of a graph is considered. In 1994, F. P. Muga proved the theorem that this number is odd for any dimension and any diameter of a circulant graph. Later, R. R. Lewis has presented a counterexample of four-dimensional circulant. In the present paper, a mistake in the proof of this theorem is pointed. Based on the new results, the early presented table of the maximal reachable orders of four-dimensional circulants is corrected.

Keywords: undirected circulant graphs, diameter, maximum order of a graph.

UDC: 519.87+519.6+519.178