Научная электронная библиотека ULRICH'S Periodicals Directory

Сибирский государственный университет
науки и технологий имени академика М.Ф. Решетнева

Сибирский аэрокосмический журнал
ISSN 2712-8970 (Print) ISSN 2782-5760 (on-line)

Сведения об образовательной организации

UDK 519.6 Doi: 10.31772/2587-6066-2018-19-2-217-222
THE CAYLEY GRAPHS OF FINITE TWO-GENERATOR BURNSIDE GROUPS OF EXPONENT 7
А. A. Kuznetsov, V. V. Kishkan
Reshetnev Siberian State University of Science and Technology; 31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation
For the first time the definition of the Cayley graph was given by the famous English mathematician Arthur Cayley in the XIX century to represent algebraic group defined by a fixed set of generating elements. Now the Cayley graphs are widely used both in mathematics and in applications. In particular, these graphs are used to represent computer networks, including the modeling of topologies of multiprocessor computer systems (MCS) – supercomputers. This is due to the fact that Cayley graphs possess many attractive properties such as regularity, vertex transitive, small diame-ter and degree at a sufficiently large number of vertices in the graph. For example, such a basic network topology as the ”ring”, ”hypercube” and ”torus” are the Cayley graphs. One of the widely used topologies of MCS is a k-dimensional hypercube. This graph is given by a k-generated Burnside group of exponent 2. This group has a simple structure and is equal to the direct product of k copies of the cyclic group of order 2. Now the Cayley graphs of groups of exponent 3, 4, and 5 have already been studied. In this paper we research the Cayley graphs of some finite two-generated Burnside groups of exponent 7. The computation of the diameter of the Cayley graph of a large finite group is a solvable but very difficult problem. In the general case the problem of determining the minimal word in a group is NP-hard (nondeterministic polynomial). Thus, in the worst case, the number of elementary operations that must be per-formed to solve this problem is an exponential function of the number of generating elements. Therefore, to effectively solve problems on Cayley graphs having a large number of vertices, it is necessary to use MCS.
Keywords: the Cayley graph, a multiprocessor computing system.
References

1.     Akers S., Krishnamurthy B. A group theoretic model for symmetric interconnection networks. Proceedings of the International Conference on Parallel Processing. 1986, P. 216–223.

2.     Schibell S., Stafford R. Processor interconnection networks and Cayley graphs. Discrete Applied Mathematics. 1992, Vol. 40, P. 337–357.

3.     Cooperman G., Finkelstein L. New methods for using Cayley graphs in interconnection networks. Discrete Applied Mathematics. 1992, Vol. 37, P. 95–118.

4.     Lakshmivarahan S., Jho J., Dhall S. Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey. Parallel Computing. 1993, Vol. 19, P. 361–407.

5.     Heydemann M. Cayley graphs and interconnection networks, in Graph symmetry: algebraic methods and applications. Dordrecht: Kluwer Academic Publishers. 1997, P. 167–226.

6.     Xu J. Topological Structure and Analysis of Interconnection Networks. Dordrecht: Kluwer Academic Publishers, 2001, 352 p.

7.     Parhami B. Swapped interconnection networks: Topological, performance, and robustness attributes. Journal of Parallel and Distributed Computing. 2005, Vol. 65, P. 1443–1452.

8.     Asai S., Kounoike, Shinano Y., Kaneko K. Computing the diameter of 17–pancake graphs using a PC cluster. LNSC. 2006, Vol. 4128, P. 1114–1124.

9.     Chen B., Xiao W., Parhami B. Internode distance and optimal routing in a class of alternating group networks. IEEE Transactionson Computers. 2006, Vol. 55, P. 1645–1648.

10.      Wang L., Tang K. The Cayley Graph implementation in TinyOS for dense wireless sensor networks. Proc. of the 6th Wireless Telecommunications Symposium, 2007.

11.      Camelo M., Papadimitriou D., Fabrega L., Vila P. Efficient Routing in Data Center with Underlying Cayley Graph. Proceedings of the 5th Workshop on Complex Networks CompleNet. 2014, P. 189–197.

12.      Kuznetsov A. A., Kuznetsova A. S. [A parallel algorithm for study of the Cayley graphs of permutation groups]. Vestnik SibGAU. 2014, No. 1(53), P. 34–39 (In Russ.).

13.      Even S., Goldreich O. The Minimum Length Generator Sequence is NP–Hard. Journal of Algorithms. 1981, Vol. 2, P. 311–313.

14.      Kuznetsov A. A. [The Cayley graphs of Burnside groups of exponent 3]. Siberian Electronic Mathematical Reports. 2015, Vol. 12, P. 248–254 (In Russ.).

15.      Kuznetsov A. A., Kuznetsova A. S. [Perspective topologies of multiprocessor computing systems based on the Cayley graphs of groups of period 4]. Vestnik SibGAU. 2016, No. 3(17), P. 575–578 (In Russ.).

16.      Kuznetsov A. A. [An algorithm of computation of the growth functions in finite two-generated groups of exponent five]. Prikladnaya Diskretnaya Matematika. 2016, No. 3(33), P. 116–125 (In Russ.).

17.      Holt D., Eick B., O’Brien E. Handbook of computational group theory. Boca Raton: Chapman & Hall/CRC Press, 2005. 514 p.

18.      Sims C. Computation with Finitely Presented Groups. Cambridge: Cambridge University Press, 1994, 628 p.

19.      Hall P. Nilpotent groups, Notes of lectures given at the Canadian Mathematical Congress 1957 Summer Seminar, in the collected works of Philip Hall. Oxford: Clarendon Press, 1988. P. 415–462.

20.      Kuznetsov A. A., Safonov K. V. Hall’s polynomials of finite two-generator groups of exponent seven. Journal of Siberian Federal University: Mathematics and Physics, 2014, No. 2(7), P. 186–190.


Kuznetsov Alexander Alexeevich – Dr. Sc., professor, head of Institute of Space Research and High Technologies,

Reshetnev Siberian State University of Science and Technology. E-mail: kuznetsov@sibsau.ru.

Kishkan Vladimir Vladimirovich – postgraduate student, Reshetnev Siberian State University of Science and

Technology. E-mail: kishkan@mail.ru.


  THE CAYLEY GRAPHS OF FINITE TWO-GENERATOR BURNSIDE GROUPS OF EXPONENT 7