The k-valent graph: A new family of cayley graphs for interconnection networks

Sun Yuan Hsieh, Tien Te Hsiao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

This paper introduces a new family of Cayley graphs, named the k-valent graphs, for building interconnection networks. It includes the trivalent Cayley graphs (Vadapalli and Srimani, 1995) as a subclass. These new graphs are shown to be regular with the node-degree k, to have logarithmic diameter subject to the number of nodes, and to be k-connected as well as maximally fault tolerant. We also propose a shortest path routing algorithm and investigate some algebraic properties like cycles or cliques embedding.

Original languageEnglish
Title of host publicationProceedings - 2004 International Conference on Parallel Processing, ICPP 2004
EditorsR. Eigenmann
Pages206-213
Number of pages8
DOIs
Publication statusPublished - 2004 Dec 17
EventProceedings - 2004 International Conference on Parallel Processing, ICPP 2004 - Montreal, Que, Canada
Duration: 2004 Aug 152004 Aug 18

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Other

OtherProceedings - 2004 International Conference on Parallel Processing, ICPP 2004
CountryCanada
CityMontreal, Que
Period04-08-1504-08-18

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Engineering(all)

Fingerprint Dive into the research topics of 'The k-valent graph: A new family of cayley graphs for interconnection networks'. Together they form a unique fingerprint.

Cite this