Representations of Borel Cayley Graphs
Copyright policy )Representations of Borel Cayley Graphs
Summary: There is a continuing search for dense \((\delta, D)\) interconnection graphs, that is, regular, undirected, degree \(\delta\) graphs with diameter \(D\) and having a large number of nodes. Cayley graphs formed by Borel subgroups currently contribute to some of the densest known \((\delta =4,D)\) graphs for a range of \(D\). However, the group theoretic representation of these graphs makes the development of efficient routing algorithms difficult. In an earlier report, it was shown that all Cayley graphs have generalized chordal ring (GCR) representations [IEEE Trans. Commun. 39, No. 11, 1533-1537 (1991; Zbl 0737.05072)]. In this paper, it is shown that all degree-4 Borel Cayley graphs can also be represented by the more restrictive chordal rings (CR) through a constructive proof. A step-by-step algorithm to transform any degree-4 Borel Cayley graph into a CR graph is provided. Examples are used to illustrate this concept.
- State University of New York System United States
- University of Rochester United States
massively parallel computer, generalized chordal ring, Borel Cayley graph, routing algorithms, Cayley graphs, Graphs and abstract algebra (groups, rings, fields, etc.), Graph theory (including graph drawing) in computer science, interconnection graphs, Mathematical problems of computer architecture, interconnection network
massively parallel computer, generalized chordal ring, Borel Cayley graph, routing algorithms, Cayley graphs, Graphs and abstract algebra (groups, rings, fields, etc.), Graph theory (including graph drawing) in computer science, interconnection graphs, Mathematical problems of computer architecture, interconnection network
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).16 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!