Weakly Regular Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

WeaklyRegularGraphs

A regular graph that is not strongly regular is known as a weakly regular graph. There are no weakly regular simple graphs on fewer than six nodes, and the numbers on n=6, 7, ... nodes are 2, 4, 16, 21, ... (OEIS A076434).

The following table lists some named weakly regular graphs. Here, the parameters (n,k,lambda,mu) give the vertex count n, the degree k, the possible common neighbors of adjacent vertices lambda, and the possible common neighbors of nonadjacent vertices mu. At least one of the latter two parameters will have two values for a weakly regular graph (otherwise, the graph would be strongly regular).

parameters graph

(8,(3),(0),(0,2)) cubical graph

(12,(3),(0),(0,1,2)) Franklin graph

(12,(3),(0,1),(0,1)) Tietze's graph

(12,(3),(0,1),(0,1)) truncated tetrahedral graph

(12,(3),(0,1),(0,1,2)) Frucht graph

(12,(4),(0),(1,2,3)) Chvátal graph

(12,(4),(1),(0,1,2)) cuboctahedral graph

(12,(5),(2),(0,2)) icosahedral graph

(14,(3),(0),(0,1)) Heawood graph

(16,(3),(0),(0,1)) Möbius-Kantor graph

(16,(4),(0),(0,2)) tesseract graph

(16,(4),(0),(0,1,2,3)) Hoffman graph

(18,(3),(0),(0,1)) Pappus graph

(18,(3),(0,1),(0,1)) truncated prism graph

(18,(5),(0,1),(0,2,3)) K_(3,3)×K_3

(19,(4),(0),(0,1)) Robertson graph

(20,(3),(0),(0,1)) Desargues graph

(20,(3),(0),(0,1)) dodecahedral graph

(20,(3),(0),(0,1)) flower snark J_5

(20,(4),(0),(0,1,2,4)) Folkman graph

(21,(4),(0),(0,1)) Brinkmann graph

(22,(3),(0),(0,1)) first Loupekine snark

(24,(3),(0),(0,1)) McGee graph

(24,(3),(0),(0,1,2)) truncated octahedral graph

(24,(3),(0,1),(0,1)) 3-Goldberg snark

(24,(3),(0,1),(0,1)) truncated cubical graph

(24,(4),(0),(0,1,2)) rolling cube graph

(24,(4),(0,1),(0,1,2)) small rhombicuboctahedral graph

(24,(5),(1,2),(0,1,2)) snub cubical graph

(24,(6),(0),(0,2,3)) Reye graph

(24,(7),(2),(0,2)) 24-Klein graph

(24,(8),(3),(0,1,4)) 24-cell graph

(24,(12),(0,4),(8,12)) Kronecker product of the icosahedral graph complement and the ones matrix J_2

(24,(14),(8),(7,8)) distance-2 graph of the 24-Klein graph

(25,(4),(0),(0,1)) 25-Grünbaum graph

(26,(3),(0),(0,1)) Celmins-Swart snarks

(26,(3),(0),(0,1)) edge-excised Coxeter graph

(27,(4),(0),(0,1)) Doyle graph

(27,(6),(1),(0,1,3)) Menger dual of the Gray configuration

(28,(3),(0),(0,1)) Coxeter graph

(28,(3),(0),(0,1)) flower snark J_7

(30,(3),(0),(0,1)) double star snark

(30,(3),(0),(0,1)) Tutte 8-cage

(30,(4),(1),(0,1)) icosidodecahedral graph

(30,(5),(0),(0,1)) Meringer graph

(30,(5),(0),(0,1)) Robertson-Wegner graph

(30,(5),(0),(0,1)) Wong graph

(30,(8),(3,4),(0,1,2,3)) line graph of the icosahedral graph

(30,(20),(10,12),(16,20)) Kronecker product of the Petersen line graph complement and the ones matrix J_2

(32,(3),(0),(0,1)) Dyck graph

(32,(5),(0),(0,1)) Wells graph

(32,(6),(0),(0,2)) Kummer graph

(36,(3),(0),(0,1)) 36-Zamfirescu graph

(36,(5),(0),(0,1)) Sylvester graph

(38,(3),(0),(0,1,2)) Barnette-Bosák-Lederberg graph

(40,(3),(0),(0,1)) 5-Goldberg snark

(42,(3),(0),(0,1,2)) 42-Faulkner-Younger graph

(42,(3),(0),(0,1,2)) 42-Grinberg graph

(42,(6),(0),(0,1)) Hoffman-Singleton graph minus star

(44,(3),(0),(0,1)) 44-Faulkner-Younger graph

(44,(3),(0),(0,1)) 44-Grinberg graph

(45,(6),(1),(0,1)) halved Foster graph

(46,(3),(0),(0,1)) 46-Grinberg graph

(46,(3),(0),(0,1,2)) Tutte's graph

(48,(3),(0),(0,1,2)) great rhombicuboctahedral graph

(50,(3),(0),(0,1)) Szekeres snark

(50,(3),(0),(0,1)) Watkins snark

(52,(4),(0,1,2),(0,1,2)) Harborth graph

(54,(3),(0),(0,1)) 54-Ellingham-Horton graph

(54,(3),(0),(0,1)) Gray graph

(56,(3),(0),(0,1)) 7-Goldberg snark

(56,(27),(16),(0,10)) Gosset graph

(57,(6),(0),(0,1)) Perkel graph

(60,(3),(0),(0,1)) truncated icosahedral graph

(60,(3),(0,1),(0,1)) truncated dodecahedral graph

(60,(4),(0,1),(0,1,2)) small rhombicosidodecahedral graph

(60,(5),(1,2),(0,1,2)) snub dodecahedral graph

(63,(10),(3),(0,2)) Conway-Smith graph

(70,(3),(0),(0,1)) Balaban 10-cage

(70,(3),(0),(0,1)) Harries graph

(70,(3),(0),(0,1)) Harries-Wong graph

(70,(4),(0),(0,1,3,4)) Meredith graph

(78,(3),(0),(0,1)) 78-Ellingham-Horton graph

(84,(3),(0,1),(0,1)) triangle-replaced Coxeter graph

(92,(3),(0),(0,1)) Horton's nonhamiltonian bicubic graph

(94,(3),(0),(0,1,2)) 94-Thomassen graph

(96,(3),(0),(0,1)) Horton's nonhamiltonian bipartite graph

(100,(7),(0),(0,1)) bipartite double of the Hoffman-Singleton graph

(102,(3),(0),(0,1)) Biggs-Smith graph

(112,(3),(0),(0,1)) Balaban 11-cage

(112,(3),(0),(0,1)) Ljubljana graph

(112,(10),(0),(0,2)) bipartite double of the Gewirtz graph

(120,(3),(0),(0,1,2)) great rhombicosidodecahedral graph

(120,(12),(5),(0,1,3)) 600-cell graph

(124,(3),(0,1),(0,1)) 124-Grinberg graph

(126,(3),(0),(0,1)) Tutte 12-cage

(154,(16),(0),(0,4)) bipartite double of the M_(22) graph

(175,(12),(5),(0,1)) line graph of the Hoffman-Singleton graph

(200,(22),(0),(0,6)) bipartite double of the Higman-Sims graph

(315,(10),(1),(0,1)) Hall-Janko near octagon

(330,(7),(0),(0,1)) doubly truncated Witt graph

(506,(15),(0),(0,1)) truncated Witt graph

(600,(4),(0),(0,1)) 120-cell graph

See also

Regular Graph, Strongly Regular Graph

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Sloane, N. J. A. Sequence A076434 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Weakly Regular Graph

Cite this as:

Weisstein, Eric W. "Weakly Regular Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/WeaklyRegularGraph.html

Subject classifications