TOPICS
Search

Weakly Regular Graph


WeaklyRegularGraphs

A weakly regular graph is a regular graph that is not strongly regular. Under the convention used here, K_2 is weakly regular and is the only such simple graph on fewer than six nodes. The numbers of nonisomorphic weakly regular graphs on n=6, 7, ... nodes are 2, 4, 16, 21, ... (OEIS A076434, restricted here to n>=6).

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 numbers lambda of common neighbors of adjacent vertices, and the possible numbers mu of common neighbors of nonadjacent vertices. Except for K_2, at least one of the latter two parameters takes two or more distinct values for a weakly regular graph (otherwise, the graph would be strongly regular).

parametersgraph
(8,(3),(0),(0,2))cubical graph Q_3
(12,(3),(0),(0,1,2))Franklin graph
(12,(3),(0,1),(0,1))Tietze 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 Q_4
(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 polyhedron graph of the cube
(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 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

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