×

Representations of Borel Cayley graphs. (English) Zbl 0820.68091

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.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
68M07 Mathematical problems of computer architecture

Citations:

Zbl 0737.05072
PDFBibTeX XMLCite
Full Text: DOI