DocumentCode
775086
Title
A well-behaved enumeration of star graphs
Author
Bagherzadeh, Nader ; Dowd, Martin ; Latifi, Shahram
Author_Institution
California Univ., Irvine, CA, USA
Volume
6
Issue
5
fYear
1995
fDate
5/1/1995 12:00:00 AM
Firstpage
531
Lastpage
535
Abstract
An enumeration of star graphs is given which has many useful properties. For example an arbitrary prefix or suffix is connected; indeed the diameter is O(n). As a consequence, there is an O(n) interval broadcast algorithm. Prefixes which have t(n-1)! vertices for some t are especially well-behaved. The topology of, embeddings in, and algorithms for these graphs are considered, making use of the enumeration
Keywords
graph theory; graphs; multiprocessor interconnection networks; Hamiltonian cycles; algorithms; embeddings; enumeration; incomplete star graph; interconnection network; interval broadcast; interval broadcast algorithm; prefix; star graphs; suffix; topology; Algorithms; Broadcasting; Communication networks; Fourier transforms; Hypercubes; Multiprocessor interconnection networks; Network topology; Orbits; Routing; Tree graphs;
fLanguage
English
Journal_Title
Parallel and Distributed Systems, IEEE Transactions on
Publisher
ieee
ISSN
1045-9219
Type
jour
DOI
10.1109/71.382321
Filename
382321
Link To Document