Optimal generalized Petersen graphs

E. A. Monakhova

Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 4, pp. 47-60.

Résumé

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.

Détail

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

Bibliographie

[1] Artamonov G. T., Topologiya regulyarnykh vychislitelnykh setei i sred, Radio i svyaz, M., 1985, 192 pp. | MR | Zbl

[2] Artamonov G. T., Tyurin V. D., Topologiya setei EVM i mnogoprotsessornykh sistem, Radio i svyaz, M., 1991, 248 pp.

[3] Korneev V. V., “O makrostrukture odnorodnykh vychislitelnykh sistem”, Vychisl. sistemy, 60, 1974, 17–34 | Zbl

[4] Monakhov O. G., “Parametricheskoe opisanie struktur odnorodnykh vychislitelnykh sistem”, Vychisl. sistemy, 80, 1979, 3–17 | MR | Zbl

[5] Monakhov O. G., Monakhova E. A., Parallelnye sistemy s raspredelennoi pamyatyu: struktury i organizatsiya vzaimodeistvii, Izd-vo SO RAN, Novosibirsk, 2000, 242 pp. | Zbl

[6] Monakhova E. A., “Ob analiticheskom opisanii optimalnykh dvumernykh diofantovykh struktur odnorodnykh vychislitelnykh sistem”, Vychisl. sistemy, 90, 1981, 81–91 | MR | Zbl

[7] Monakhova E. A., “Algoritmy mezhmashinnykh vzaimodeistvii i rekonfiguratsii grafov svyazei v vychislitelnykh sistemakh s programmiruemoi strukturoi”, Vychisl. sistemy, 94, 1982, 81–102 | MR | Zbl

[8] Balaban A. T., “Reaction graphs”, Graph theoretical approaches to chemical reactivity, Kluwer Acad. Publ., Amsterdam, 1994, 137–180

[9] Beivide R., Martinez C., Izu C., Gutierrez J., Gregorio J. A., Miguel-Alonso J., “Chordal topologies for interconnection networks”, Lett. Notes Comp. Sci., 2858, 2003, 385–392

[10] Bermond J.-C., Comellas F., Hsu D. F., “Distributed loop computer networks: a survey”, J. Parallel Distributed Comp., 24 (1995), 2–10 | DOI

[11] Bermond J.-C., Delorme C., Farhi G., “Large graphs with given degree and diameter. II”, J. Combinat. Theory. Series B, 36 (1984), 32–48 | DOI | MR | Zbl

[12] Bermond J.-C., Illiades G., Peyrat C., “An optimization problem in distributed loop computer networks”, Proc. of the 3rd international conference on combinatorial mathematics (New York, USA, June 1985), Ann. New York Acad. Sci., 555, New York Acad. Sci., New York, 1989, 45–55 | MR | Zbl

[13] Boesch F. T., Wang J.-F., “Reliable circulant networks with minimum transmission delay”, IEEE Trans. Circuits Syst., CAS-32 (1985), 1286–1291 | DOI | MR

[14] Fabrega J., Zaragoza M., “Fault-tolerant routings in double fixed-step networks”, Discrete Appl. Math., 78 (1997), 61–74 | DOI | MR | Zbl

[15] Hwang F. K., “A survey on multi-loop networks”, Theoret. Comput. Sci., 299 (2003), 107–121 | DOI | MR | Zbl

[16] Monakhov O. G., Monakhova E. A., “Computer discovery of analytical descriptions of families of circulant networks”, Proc. of the 6th Inter. Conf. on soft computing and measurements, SCM' 2003, Vol. 1, St.-Petersburg, Russia, 2003, 345–348

[17] Nedela R., Skoviera M., “Which generalized Petersen graphs are Cayley graphs?”, J. Graph Theory, 19:1 (2006), 1–11 | DOI | MR

[18] Pedersen J. M., Riaz T. M., Madsen O. B., “Distances in generalized double rings and degree three chordal rings”, Proc. of the IASTED Inter. Conf. on parallel, and distributed computing, and networks, IASTED PDCN2005 (Austria, 2005), ACTA Press, Calgary, Canada, 2005, 153–158

[19] Pedersen J. M., Riaz T. M., Madsen O. B., “Five novel selection policies for N2R network structures”, Proc. of IEEE/ICACT' 2006, the 8th inter. conf. on advanced communication technology, Vol. 3 (Korea, 2006), IEEE Press, New York, 2006, 2174–2179

[20] Yang Y., Funashashi A., Jouraku A., Nishi H., Amano H., Sueyoshi T., “Recursive diagonal torus: An interconnection network for massively parallel computers”, IEEE Transactions on Parallel and Distributed Systems, 12:7 (2001), 701–715 | DOI

[21] Yang N., Jan G. E., Leu S.-W., Lin I.-J., “A study of the generalized Petersen graph and a novel graph Y”, Worshop on algorithms and computational molecular biology, (ICS2002), Taipei, Taiwan, 2002, 1–18

[22] Yebra J. L. A., Fiol M. A., Morillo P., Alegre I., “The diameter of undirected graphs associated to plane tessellations”, Ars Combinatoria, 20B (1985), 159–172 | MR

[23] Watkins M. E., “A theorem on Tait colorings with an application to the generalized Petersen graphs”, J. Combin. Theory, 6 (1969), 152–164 | DOI | MR | Zbl

[24] Wong C. K., Coppersmith D., “A combinatorial problem related to multimodule memory organizations”, J. Assoc. Comput. Mach., 21 (1974), 392–402 | MR | Zbl