Volume 16, No 4, 2009, P. 47-60
E. A. Monakhova
Optimal generalized Petersen graphs
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
1. Institute of Computational Mathematics and Mathematical Geophysics, SB RAS,
6 Acad. M. A. Lavrent’eva ave., 630090 Novosibirsk, Russia