Volume 20, No 1, 2013, P. 37-44

UDC 519.87
Monakhova E. A.
A new attainable lower bound on the number of nodes in quadruple circulant networks

We consider the problem of maximization of the number of nodes for fixed degree and diameter of undirected circulant networks. The known lower bound on the maximum order of quadruple circulant networks is improved by $O(d^3)$ for any even diameter $d\equiv0\pmod4$. The family of circulant networks achieving the obtained estimate is found. As we conjecture, the found graphs are the largest circulants for the dimension four.
Tab. 2, bibliogr. 9.

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

Monakhova Emilia Anatol’evna 1
1. Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 
6 Acad. Lavrent’ev Ave., 630090 Novosibirsk, Russia
e-mail: emilia@rav.sscc.ru

 © Sobolev Institute of Mathematics, 2015