On Reconstruction of Normal Edge-Transitive Cayley Graphs
- PDF / 389,356 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 84 Downloads / 188 Views
Annals of Combinatorics
On Reconstruction of Normal Edge-Transitive Cayley Graphs Behnam Khosravi, Behrooz Khosravi and Bahman Khosravi Abstract. The main idea of this paper is to provide an algebraic algorithm for constructing symmetric graphs with optimal fault tolerance. For this purpose, we use normal edge-transitive Cayley graphs and the idea of reconstruction question posed by Praeger to present a special factorization of groups which induces a graphical decomposition of normal edge-transitive Cayley graphs to simpler normal edge-transitive Cayley graphs. Then as a consequence of our results, we continue the study of normal edge-transitive Cayley graphs of abelian groups and we show that knowing normal edge-transitive Cayley graphs of abelian p-groups, we can determine all normal edge-transitive Cayley graphs of abelian groups. Mathematics Subject Classification. Primary 05C25; Secondary 08A30, 08A35. Keywords. Normal edge-transitive Cayley graphs, Factorization of groups, Optimal fault tolerance.
1. Introduction and Main Results There are many known networks based on symmetric graphs which are used in designing very fast computers (e.g. hypercubes or folded hypercubes). Most of these graphs are chosen because of their well-behavior structures and their symmetric properties. In fact, since in an interconnection network, it is very possible to lose some processors or direct links between them, symmetric graphs are very good choices because they have optimal fault tolerance. On the other hand, note that a network which can be easily divided to smaller networks, is a good choice for designing supercomputers, because this property makes it possible to run different tasks simultaneously by different users on the same machine. Cayley graphs of groups have been always among the best graphs used in computer science and networks, because they are algebraic and vertextransitive. In fact, the algebraic structure of a Cayley graph makes working 0123456789().: V,-vol
B. Khosravi et al.
with them easy, specially in presenting very effective routing algorithms. Furthermore, edge-transitive Cayley graphs are more interesting because they are symmetric (vertex- and edge-transitive) and so they have optimal fault tolerance. Now it is natural to ask that “Is it possible to design a network based on Cayley graphs which is capable to improve its performance by reorganizing itself every moment based on its active nodes (or direct links), to have a symmetric structure which contains the maximum possible active nodes? Or based on its tasks which must be done at every moment simultaneously, can it divide itself to smaller symmetric networks or merge some of them to construct a bigger symmetric network? (What we can call it somehow an intelligent network)”. Clearly for answering these questions, the first logical step is to find an algebraic algorithm for constructing symmetric graphs (and as we will see, it yields to an algorithm for constructing graphs with optimal fault tolerance), because such an algorithm can give machines the ab
Data Loading...
