Families of Fixed Degree Graphs for Processor Interconnection

Mark Jerrum; Sven Skyum

doi:10.1109/TC.1984.1676410

Families of Fixed Degree Graphs for Processor Interconnection

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

Abstract

A construction is presented which, given a fixed undirected graph of low degree and small average path length, yields an infinite sequence of low diameter graphs of increasing order and fixed degree. As examples of the construction, infinite sequences of low diameter graphs are presented with degrees in the range 3 to 30. Expressed as a function of the order of the graphs, the degree 3 sequence has diameter bounded above by 1.4722 log2 N + O(1), and the degree 4 sequence by 0.9083 log2N + O(1).

Original language	English
Journal	I E E E Transactions on Computers
Volume	C-33
Issue	2
Pages (from-to)	190-194
Number of pages	5
ISSN	0018-9340
DOIs	https://doi.org/10.1109/TC.1984.1676410
Publication status	Published - 1984

Access to Document

10.1109/TC.1984.1676410

Cite this

@article{1b4773a553354162acf0b7166bc26fff,

title = "Families of Fixed Degree Graphs for Processor Interconnection",

abstract = "A construction is presented which, given a fixed undirected graph of low degree and small average path length, yields an infinite sequence of low diameter graphs of increasing order and fixed degree. As examples of the construction, infinite sequences of low diameter graphs are presented with degrees in the range 3 to 30. Expressed as a function of the order of the graphs, the degree 3 sequence has diameter bounded above by 1.4722 log2 N + O(1), and the degree 4 sequence by 0.9083 log2N + O(1).",

author = "Mark Jerrum and Sven Skyum",

year = "1984",

doi = "10.1109/TC.1984.1676410",

language = "English",

volume = "C-33",

pages = "190--194",

journal = "I E E E Transactions on Computers",

issn = "0018-9340",

publisher = "Institute of Electrical and Electronics Engineers",

number = "2",

}

TY - JOUR

T1 - Families of Fixed Degree Graphs for Processor Interconnection

AU - Jerrum, Mark

AU - Skyum, Sven

PY - 1984

Y1 - 1984

N2 - A construction is presented which, given a fixed undirected graph of low degree and small average path length, yields an infinite sequence of low diameter graphs of increasing order and fixed degree. As examples of the construction, infinite sequences of low diameter graphs are presented with degrees in the range 3 to 30. Expressed as a function of the order of the graphs, the degree 3 sequence has diameter bounded above by 1.4722 log2 N + O(1), and the degree 4 sequence by 0.9083 log2N + O(1).

AB - A construction is presented which, given a fixed undirected graph of low degree and small average path length, yields an infinite sequence of low diameter graphs of increasing order and fixed degree. As examples of the construction, infinite sequences of low diameter graphs are presented with degrees in the range 3 to 30. Expressed as a function of the order of the graphs, the degree 3 sequence has diameter bounded above by 1.4722 log2 N + O(1), and the degree 4 sequence by 0.9083 log2N + O(1).

U2 - 10.1109/TC.1984.1676410

DO - 10.1109/TC.1984.1676410

M3 - Journal article

SN - 0018-9340

VL - C-33

SP - 190

EP - 194

JO - I E E E Transactions on Computers

JF - I E E E Transactions on Computers

IS - 2

ER -

Families of Fixed Degree Graphs for Processor Interconnection

Abstract

Access to Document

Fingerprint

Cite this