Arrangement graphs: a class of generalized star graphs

Khaled Day*, Anand Tripathi

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

151 Citations (Scopus)


We present a new interconnection topology, called the arrangement graph, as a generalization of the star graph topology and prove many of its properties such as: hierarchical structure, vertex and edge symmetry, simple and optimal routing, and many fault tolerance properties. The arrangement graph presents more flexibility than the star graph in terms of choosing the major design parameters: degree, diameter, and number of nodes.

Original languageEnglish
Pages (from-to)235-241
Number of pages7
JournalInformation Processing Letters
Issue number5
Publication statusPublished - Jul 3 1992
Externally publishedYes


  • Fault tolerance
  • routing
  • star graphs
  • symmetry

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Arrangement graphs: a class of generalized star graphs'. Together they form a unique fingerprint.

Cite this