THE CAYLEY GRAPHS OF FINITE TWO-GENERATOR BURNSIDE GROUPS OF EXPONENT 7
Александр А. Кузнецов, Vladimir V. Kishkan · Siberian Aerospace Journal · 2018
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 diameter 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 kdimensional 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 twogenerated 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 performed 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.