Largest Known (Degree, Diameter)-Graphs (Description)

Largest Known (Degree, Diameter)-Graphs

Diameter 9

Last modification: May 25, 2005.

http://www-mat.upc.es/grup_de_grafs/desc_g.html

CG_570

Degree= 3, Diameter = 9; Order =570; Moore bound=1534.

   Chordal ring with repeated set of chords:  
         -255  -58  -164  58  -237  255  -47  237  164  47

Final Project (Master Thesis) Xavier Guarch (supervisor: Francesc Comellas) Construcció de xarxes d'interconnexió denses i cages mitjançant simulated annealing (Contruction of dense interconnection networks and cages using simulated annealing) 2000. PFC ETSETB. Xavier Guarch Domingo

Download the adjacency list of the graph.

DH_7550

Degree= 4, Diameter = 9; Order =7550; Moore bound=39365.

Obtained as a Cayley graph for semidirect product of Zm with Zn

Group             Generators        Inverses        Order of Generator
25*(171)302       [8 156]           [17 82]         25
                  [10 31]           [15 285]        10

M.J. Dinneen & P.R. Hafner. New results for the degree/diameter problem. Networks, 24 (1994) 359-367.

H_53020

Degree= 5, Diameter = 9; Order =53020; Moore bound=436906

Obtained as a Cayley graph for semidirect product of Zm with Zn.

             m  =      20
             n  =    2651
             a  =    2645
            m*n =   53020


[    1, 1406 ] ,    [   19, 1118 ]        20
[   13, 1904 ] ,    [    7, 1339 ]        20
[   10,    0 ]                             2


Degree   =  5
Diameter =  9

P.R.Hafner (1998-1999)

See also: P.R. Hafner; Large Cayley graphs and digraphs with small degree and diameter. CDMTCS report 005, June 1995.

H_294679

Degree= 6, Diameter = 8; Order =294679; Moore bound=585937.

Obtained as a Cayley graph for semidirect product of Zm with Zn.


             m  =      77
             n  =    3827
             a  =      97
            m*n =  294679

[   53, 3812 ] ,    [   24, 2206 ]        77
[   68, 2231 ] ,    [    9, 1766 ]        77
[    1, 3083 ] ,    [   76, 1428 ]        77

Degree   =  6
Diameter =  9

P.R.Hafner (1998-1999)

See also: P.R. Hafner; Large Cayley graphs and digraphs with small degree and diameter. CDMTCS report 005, June 1995.

H_1085580

Degree= 7, Diameter = 9; Order =1085580; Moore bound=14108774.

Obtained as a Cayley graph for semidirect product of Zm with Zn.

             m  =      36
             n  =   30155
             a  =     133
            m*n = 1085580


[   17, 6062 ] ,    [   19, 15926 ]        36
[   15, 20130 ] ,    [   21, 29695 ]        12
[   26, 17252 ] ,    [   10, 23507 ]        18
[   18,    0 ]                             2

Degree   =  7
Diameter =  9

P.R.Hafner (1998-1999)

See also: P.R. Hafner; Large Cayley graphs and digraphs with small degree and diameter. CDMTCS report 005, June 1995.

H_4039649

Degree= 8, Diameter = 9; Order =4039649; Moore bound=53804809.

Obtained as a Cayley graph for semidirect product of Zm with Zn.


             m  =     109
             n  =   37061
             a  =     555
            m*n = 4039649

[   48, 12996 ] ,    [   61, 35891 ]       109
[   80, 11394 ] ,    [   29, 6069 ]       109
[   88, 7039 ] ,    [   21, 19501 ]       109
[   28, 13191 ] ,    [   81, 36170 ]       109

Degree   =  8
Diameter =  9

P.R.Hafner (1998-1999)

See also: P.R. Hafner; Large Cayley graphs and digraphs with small degree and diameter. CDMTCS report 005, June 1995.

H_8911766

Degree= 9, Diameter = 9; Order =8911766; Moore bound=172565650.

Obtained as a Cayley graph for semidirect product of Zm with Zn.


             m  =     206
             n  =   43261
             a  =     370
            m*n = 8911766

[  128, 6824 ] ,    [   78, 17412 ]       103
[  152, 29426 ] ,    [   54, 7128 ]       103
[   27, 30522 ] ,    [  179, 21157 ]       206
[   40,  259 ] ,    [  166, 34366 ]       103
[  103,    0 ]                             2

Degree   =  9
Diameter =  9

P.R.Hafner (1998-1999)

See also: P.R. Hafner; Large Cayley graphs and digraphs with small degree and diameter. CDMTCS report 005, June 1995.

H_13964808

Degree= 10, Diameter = 9; Order =13964808; Moore bound=484275611. .

Obtained as a Cayley graph for semidirect product of Zm with Zn.


             m  =     312
             n  =   44759
             a  =    6346
            m*n = 13964808

[   40, 44370 ] ,    [  272, 39901 ]       429
[  219, 26901 ] ,    [   93, 26747 ]       104
[  282, 24508 ] ,    [   30, 44242 ]        52
[  163, 9984 ] ,    [  149, 35724 ]       312
[  151, 19190 ] ,    [  161, 32566 ]       312

Degree   = 10
Diameter =  9

P.R.Hafner (1998-1999)

See also: P.R. Hafner; Large Cayley graphs and digraphs with small degree and diameter. CDMTCS report 005, June 1995.

DG_48626760

Degree= 11, Diameter = 9; Order =48626760; Moore bound=1222222222.

Compound graph from generalized hexagons.

C.Delorme, J. Gomez; Some new large compound graphs. LRI Rapport 905 (05/1994), Laboratoire de Recherche en Informatique, Orsay, France.

DG_97.386.380

Degree= 12, Diameter = 9; Order =97.386.380; Moore bound=2829537229.

Compound graph from generalized hexagons.

C.Delorme, J. Gomez; Some new large compound graphs. LRI Rapport 905 (05/1994), Laboratoire de Recherche en Informatique, Orsay, France.

DG_145.880.280

Degree= 13, Diameter = 9; Order =145.880.280; Moore bound=.

Compound graph from generalized hexagons.

C.Delorme, J. Gomez; Some new large compound graphs. LRI Rapport 905 (05/1994), Laboratoire de Recherche en Informatique, Orsay, France.

DG_194.639.900

Degree= 14, Diameter = 9; Order =194.639.900; Moore bound=12371915935.

Compound graph from generalized hexagons.

C.Delorme, J. Gomez; Some new large compound graphs. LRI Rapport 905 (05/1994), Laboratoire de Recherche en Informatique, Orsay, France.