Vertex-transitivity and routing for Cayley graphs in GCR representations

K. Wendy Tang; Bruce W. Arden

doi:10.1145/130069.130147

Vertex-transitivity and routing for Cayley graphs in GCR representations

K. Wendy Tang
, Bruce W. Arden

Electrical Engineering

Stony Brook University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

16 Scopus citations

Abstract

Dense, symmetric graphs are good candidates for effective interconnection networks. Cayley graphs, formed by Borel subgroups, are the densest, symmetric graphs known for a range of diameters [1]. Every Cayley graph can be represented with integer node labels by transforming into another existing topology, Generalized Chordal Ring (GCR) [2]. However, generally speaking, GCR graphs are not fully symmetric. In this paper, we provide a framework for the formulation of the complete symmetry (or vertex-transitivity) of Cayley graphs in the integer domain of GCR representations. Successful realization of such formulation offers a simple, iterative routing algorithm that is capable of determining multiple, shortest paths between any source and destination pairs. An example from a Borel Cayley graph is used to illustrate this concept.

Original language	English
Title of host publication	Applied Computing
Subtitle of host publication	Technological Challenges of the 1990's
Publisher	Publ by ACM
Pages	1180-1187
Number of pages	8
ISBN (Print)	089791502X, 9780897915021
DOIs	https://doi.org/10.1145/130069.130147
State	Published - 1992
Event	Proceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing SAC '92 - Kansas City, KS, USA Duration: Mar 1 1992 → Mar 3 1992

Publication series

Name	Applied Computing: Technological Challenges of the 1990's

Conference

Conference	Proceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing SAC '92
City	Kansas City, KS, USA
Period	03/1/92 → 03/3/92

Access to Document

10.1145/130069.130147

Cite this

@inproceedings{72fcfef81f884c8ba23f57461cdaa788,

title = "Vertex-transitivity and routing for Cayley graphs in GCR representations",

abstract = "Dense, symmetric graphs are good candidates for effective interconnection networks. Cayley graphs, formed by Borel subgroups, are the densest, symmetric graphs known for a range of diameters [1]. Every Cayley graph can be represented with integer node labels by transforming into another existing topology, Generalized Chordal Ring (GCR) [2]. However, generally speaking, GCR graphs are not fully symmetric. In this paper, we provide a framework for the formulation of the complete symmetry (or vertex-transitivity) of Cayley graphs in the integer domain of GCR representations. Successful realization of such formulation offers a simple, iterative routing algorithm that is capable of determining multiple, shortest paths between any source and destination pairs. An example from a Borel Cayley graph is used to illustrate this concept.",

author = "Tang, \{K. Wendy\} and Arden, \{Bruce W.\}",

year = "1992",

doi = "10.1145/130069.130147",

language = "English",

isbn = "089791502X",

series = "Applied Computing: Technological Challenges of the 1990's",

publisher = "Publ by ACM",

pages = "1180--1187",

booktitle = "Applied Computing",

note = "Proceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing SAC '92 ; Conference date: 01-03-1992 Through 03-03-1992",

}

Tang, KW & Arden, BW 1992, Vertex-transitivity and routing for Cayley graphs in GCR representations. in Applied Computing: Technological Challenges of the 1990's. Applied Computing: Technological Challenges of the 1990's, Publ by ACM, pp. 1180-1187, Proceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing SAC '92, Kansas City, KS, USA, 03/1/92. https://doi.org/10.1145/130069.130147

TY - GEN

T1 - Vertex-transitivity and routing for Cayley graphs in GCR representations

AU - Tang, K. Wendy

AU - Arden, Bruce W.

PY - 1992

Y1 - 1992

N2 - Dense, symmetric graphs are good candidates for effective interconnection networks. Cayley graphs, formed by Borel subgroups, are the densest, symmetric graphs known for a range of diameters [1]. Every Cayley graph can be represented with integer node labels by transforming into another existing topology, Generalized Chordal Ring (GCR) [2]. However, generally speaking, GCR graphs are not fully symmetric. In this paper, we provide a framework for the formulation of the complete symmetry (or vertex-transitivity) of Cayley graphs in the integer domain of GCR representations. Successful realization of such formulation offers a simple, iterative routing algorithm that is capable of determining multiple, shortest paths between any source and destination pairs. An example from a Borel Cayley graph is used to illustrate this concept.

AB - Dense, symmetric graphs are good candidates for effective interconnection networks. Cayley graphs, formed by Borel subgroups, are the densest, symmetric graphs known for a range of diameters [1]. Every Cayley graph can be represented with integer node labels by transforming into another existing topology, Generalized Chordal Ring (GCR) [2]. However, generally speaking, GCR graphs are not fully symmetric. In this paper, we provide a framework for the formulation of the complete symmetry (or vertex-transitivity) of Cayley graphs in the integer domain of GCR representations. Successful realization of such formulation offers a simple, iterative routing algorithm that is capable of determining multiple, shortest paths between any source and destination pairs. An example from a Borel Cayley graph is used to illustrate this concept.

UR - https://www.scopus.com/pages/publications/0026981806

U2 - 10.1145/130069.130147

DO - 10.1145/130069.130147

M3 - Conference contribution

AN - SCOPUS:0026981806

SN - 089791502X

SN - 9780897915021

T3 - Applied Computing: Technological Challenges of the 1990's

SP - 1180

EP - 1187

BT - Applied Computing

PB - Publ by ACM

T2 - Proceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing SAC '92

Y2 - 1 March 1992 through 3 March 1992

ER -

Vertex-transitivity and routing for Cayley graphs in GCR representations

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this