Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!pasteur!agate!ucbvax!vax1.esprit.southampton.ac.uk!JRA
From: JRA@vax1.esprit.southampton.ac.uk
Newsgroups: comp.sys.transputer
Subject: RE: Sigma networks
Message-ID: <00002E9E_000931AC.0092006F2CE794A0$8_1@UK.AC.SOTON.ESP.V1>
Date: 7 Feb 89 14:40:12 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The Internet
Lines: 27


   I think I was the person who Conor O'Neill heard talking about sigma
networks at the Southampton Occam User Group. I believe they are more 
widely known as delta networks (I chose the wrong Greek symbol at some point).
The generalization of these to any even valency can safely be referred to as 
de Bruijn graphs.
   The largest known 4-valent graph of diameter does indeed have over 10,000
nodes. A table of the current largest known graphs of small valency and
diameter is maintained by J.-C. Bermond of Universite de Paris-Sud. Here is the
most up-to-date version of this table that I have for 3, 4 and 5-valent graphs.

             3-valent   4-valent     5-valent
Diameter 2    10 nodes     15 nodes      24 nodes
   ''    3    20  ''       40  ''        70  ''
   ''    4    38  ''       95  ''       182  ''
   ''    5    70  ''      364  ''       532  ''
   ''    6   128  ''      734  ''      2742  ''
   ''    7   184  ''     1081  ''      4368  ''
   ''    8   320  ''     2943  ''     11200  ''
   ''    9   540  ''     7439  ''     33600  ''
   ''   10   938  ''    15657  ''    123120  '' 
                                                 James Allwright

James Allwright
Dept. of Electronics & Computer Science
Southampton University
JRA@UK.AC.SOTON.ESP.V1 or JRA@UK.AC.SOTON.CM