Volume 16, No 4, 2009, P. 47-60

UDC 519.176
E. A. Monakhova
Optimal generalized Petersen graphs

Abstract:
The generalized Petersen graphs are considered as a model for interconnection networks of computer systems. We consider the problem of minimization of the diameter (the maximal delay in a network) for a given number of nodes of a graph. A mapping of optimal circulant networks of degree four into the class of generalized Petersen graphs is found which preserves the optimality of a graph. Analytical descriptions of optimal generalized Petersen graphs are given for any order of a graph. An analytical solution of a problem of the shortest paths routing is presented for the obtained optimal graphs.
Il. 2, tabl. 1, bibl. 24.

Keywords: generalized Petersen graphs, circulant graphs of degree four, diameter, optimal graphs, shortest paths.

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