This page provides topological information about a number of
interconnection topologies. The diagrams are computer-generated
and often differ from the customary layouts. Vertices that are
rendered using the same color and shape are topologically equivalent as determined
by the NAUTY package. Besides determining the vertex equivalence classes (vecs),
NAUTY also determines the number of automorphisms for the graph.
The gifs provided here are output from AT&T's NEATO.
The diameter (of undirected graphs) is indicated by a path with bi-directional edges.
The bisection width is indicated by using black edges to indicate a cluster of vertices
and blue edges to indicate the other cluster. Red edges are in a bisector.
The bisector is minimum when the number of vertices does not exceed 40. For larger
cases, the bisector is approximated using the METIS package.
linear(5) 5 vertices undirected
autos (nty) 2.000000E0
v.e.c. (nty) 3
diameter (alg) 4
in-degree (alg) 2
out-degree (alg) 2
bisection width (alg) 1
linear(6) 6 vertices undirected
autos (nty) 2.000000E0
v.e.c. (nty) 3
diameter (alg) 5
in-degree (alg) 2
out-degree (alg) 2
bisection width (alg) 1
ring(5) 5 vertices undirected
autos (nty) 10.000000E0
v.e.c. (nty) 1
diameter (alg) 2
in-degree (alg) 2
out-degree (alg) 2
bisection width (alg) 2
ring(6) 6 vertices undirected
autos (nty) 12.000000E0
v.e.c. (nty) 1
diameter (alg) 3
in-degree (alg) 2
out-degree (alg) 2
bisection width (alg) 2
chordalRing(8,3) 8 vertices undirected
autos (nty) 48.000000E0
v.e.c. (nty) 1
diameter (alg) 3
in-degree (alg) 3
out-degree (alg) 3
bisection width (alg) 4
chordalRing(14,5) 14 vertices undirected
autos (nty) 336.000000E0
v.e.c. (nty) 1
diameter (alg) 3
in-degree (alg) 3
out-degree (alg) 3
bisection width (alg) 7
twoDmesh2(3,6) 18 vertices undirected
autos (nty) 4.000000E0
v.e.c. (nty) 6
diameter (alg) 7
in-degree (alg) 4
out-degree (alg) 4
bisection width (alg) 3
twoDmesh2(4,7) 28 vertices undirected
autos (nty) 4.000000E0
v.e.c. (nty) 8
diameter (alg) 9
in-degree (alg) 4
out-degree (alg) 4
bisection width (alg) 5
twoDtorus2(3,6) 18 vertices undirected
autos (nty) 72.000000E0
v.e.c. (nty) 1
diameter (alg) 4
in-degree (alg) 4
out-degree (alg) 4
bisection width (alg) 6
twoDtorus2(4,7) 28 vertices undirected
autos (nty) 112.000000E0
v.e.c. (nty) 1
diameter (alg) 5
in-degree (alg) 4
out-degree (alg) 4
bisection width (alg) 10
twoDtorus(5) 25 vertices undirected
autos (nty) 200.000000E0
v.e.c. (nty) 1
diameter (alg) 4
in-degree (alg) 4
out-degree (alg) 4
bisection width (alg) 12
twoDtorus(6) 36 vertices undirected
autos (nty) 288.000000E0
v.e.c. (nty) 1
diameter (alg) 6
in-degree (alg) 4
out-degree (alg) 4
bisection width (alg) 12
tree(15) 15 vertices undirected
autos (nty) 128.000000E0
v.e.c. (nty) 4
diameter (alg) 6
in-degree (alg) 3
out-degree (alg) 3
bisection width (alg) 1
tree(18) 18 vertices undirected
METIS returned unbalanced partitions 10 8!!!
autos (nty) 32.000000E0
v.e.c. (nty) 12
diameter (alg) 7
in-degree (alg) 3
out-degree (alg) 3
bisection width (alg) 1
tree(21) 21 vertices undirected
METIS returned disconnected cluster!!!
autos (nty) 128.000000E0
v.e.c. (nty) 12
diameter (alg) 7
in-degree (alg) 3
out-degree (alg) 3
bisection width (alg) 2
meshCBT(2,2) 40 vertices undirected
autos (nty) 128.000000E0
v.e.c. (nty) 3
diameter (alg) 8
in-degree (alg) 3
out-degree (alg) 3
bisection width (alg) 4
CBTmesh(2) 80 vertices undirected
autos (nty) 4.000000E0
v.e.c. (nty) 20
diameter (alg) 18
in-degree (alg) 4
out-degree (alg) 4
bisection width (alg) 4
shuffleExchange(3) 8 vertices directed
autos (nty) 2.000000E0
v.e.c. (nty) 4
diameter (alg) 5
in-degree (alg) 2
out-degree (alg) 2
bisection width (alg) 0
shuffleExchange(4) 16 vertices directed
autos (nty) 2.000000E0
v.e.c. (nty) 8
diameter (alg) 7
in-degree (alg) 2
out-degree (alg) 2
bisection width (alg) 0
shuffleExchange(6) 64 vertices directed
autos (nty) 2.000000E0
v.e.c. (nty) 32
diameter (alg) 11
in-degree (alg) 2
out-degree (alg) 2
bisection width (alg) 0
butterfly(2) 4 vertices undirected
autos (nty) 8.000000E0
v.e.c. (nty) 1
diameter (alg) 2
in-degree (alg) 2
out-degree (alg) 2
bisection width (alg) 2
butterfly(3) 12 vertices undirected
autos (nty) 128.000000E0
v.e.c. (nty) 2
diameter (alg) 4
in-degree (alg) 4
out-degree (alg) 4
bisection width (alg) 4
butterfly(4) 32 vertices undirected
autos (nty) 32768.000000E0
v.e.c. (nty) 2
diameter (alg) 6
in-degree (alg) 4
out-degree (alg) 4
bisection width (alg) 8
butterfly(5) 80 vertices undirected
autos (nty) 2147483648.000000E0
v.e.c. (nty) 3
diameter (alg) 8
in-degree (alg) 4
out-degree (alg) 4
bisection width (alg) 16
wrappedButterfly(2) 8 vertices undirected
autos (nty) 48.000000E0
v.e.c. (nty) 1
diameter (alg) 3
in-degree (alg) 3
out-degree (alg) 3
bisection width (alg) 4
wrappedButterfly(3) 24 vertices undirected
autos (nty) 48.000000E0
v.e.c. (nty) 1
diameter (alg) 4
in-degree (alg) 4
out-degree (alg) 4
bisection width (alg) 8
wrappedButterfly(4) 64 vertices undirected
autos (nty) 128.000000E0
v.e.c. (nty) 1
diameter (alg) 6
in-degree (alg) 4
out-degree (alg) 4
bisection width (alg) 16
wrappedButterfly(5) 160 vertices undirected
autos (nty) 320.000000E0
v.e.c. (nty) 1
diameter (alg) 7
in-degree (alg) 4
out-degree (alg) 4
bisection width (alg) 32
cubeConnection(2) 8 vertices undirected
autos (nty) 16.000000E0
v.e.c. (nty) 1
diameter (alg) 4
in-degree (alg) 2
out-degree (alg) 2
bisection width (alg) 2
cubeConnection(3) 24 vertices undirected
autos (nty) 48.000000E0
v.e.c. (nty) 1
diameter (alg) 6
in-degree (alg) 3
out-degree (alg) 3
bisection width (alg) 4
cubeConnection(4) 64 vertices undirected
autos (nty) 128.000000E0
v.e.c. (nty) 1
diameter (alg) 8
in-degree (alg) 3
out-degree (alg) 3
bisection width (alg) 8
cubeConnection(5) 160 vertices undirected
autos (nty) 320.000000E0
v.e.c. (nty) 1
diameter (alg) 10
in-degree (alg) 3
out-degree (alg) 3
bisection width (alg) 16
hypercube(2) 4 vertices undirected
autos (nty) 8.000000E0
v.e.c. (nty) 1
diameter (alg) 2
in-degree (alg) 2
out-degree (alg) 2
bisection width (alg) 2
hypercube(3) 8 vertices undirected
autos (nty) 48.000000E0
v.e.c. (nty) 1
diameter (alg) 3
in-degree (alg) 3
out-degree (alg) 3
bisection width (alg) 4
hypercube(4) 16 vertices undirected
autos (nty) 384.000000E0
v.e.c. (nty) 1
diameter (alg) 4
in-degree (alg) 4
out-degree (alg) 4
bisection width (alg) 8
hypercube(5) 32 vertices undirected
autos (nty) 3840.000000E0
v.e.c. (nty) 1
diameter (alg) 5
in-degree (alg) 5
out-degree (alg) 5
bisection width (alg) 16
hypercube(6) 64 vertices undirected
autos (nty) 46080.000000E0
v.e.c. (nty) 1
diameter (alg) 6
in-degree (alg) 6
out-degree (alg) 6
bisection width (alg) 32