This article is cited in 1 paper

Optimal generalized Petersen graphs

E. A. Monakhova

Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk, Russia

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.

UDC: 519.176

Received: 26.01.2009
Revised: 30.04.2009

Bibliographic databases:

• 
•