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

Authors:

Jerrum, Mark ;
Close
unknown
Skyum, Sven
Close
Department of Computer Science, Science and Technology, Aarhus University

DOI:

10.1109/TC.1984.1676410

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).

Type:

Journal article

Language:

English

Published in:

I E E E Transactions on Computers, 1984, Vol C-33, Issue 2, p. 190-194

Main Research Area:

Science/technology

Publication Status:

Published

Review type:

Peer Review

Submission year:

1984

Scientific Level:

Scientific

ID:

2185906539

Families of Fixed Degree Graphs for Processor Interconnection

Full text access

On-site access

At institution

Example	Finds records
water{}	containing the word "water".
water supplies"{}"	containing the phrase "water supplies".
author:"Doe, John"author:"{}"	containing the prase "Doe, John" in the author field.
title:IEEEtitle:{}	containing the word "IEEE" in the title field.
Need more help?	Advanced search tutorial