A Well-behaved Enumeration of Star Graphs

Authors

Nader Bagherzadeh, University of California, IrvineFollow
Martin Dowd, University of California, IrvineFollow
Shahram Latifi, University of Nevada, Las VegasFollow

Document Type

Article

Publication Date

5-1995

Publication Title

IEEE Transactions on Parallel and Distributed Systems (TPDS)

Volume

6

First page number:

531

Last page number:

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

Cayley graphs; Computer algorithms; Hamiltonian graph theory; Hypercube networks (Computer networks); Parallel computers

Disciplines

Computer and Systems Architecture | Digital Circuits | Digital Communications and Networking | Power and Energy | Systems and Communications

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

Repository Citation

Bagherzadeh, N., Dowd, M., Latifi, S. (1995). A Well-behaved Enumeration of Star Graphs. IEEE Transactions on Parallel and Distributed Systems (TPDS), 6 531-535.