Brinkmann Graph


The Brinkmann graph (misspelled by Cancela et al. (2004) as "Brinkman") is a weakly regular quartic graph on 21 vertices and 42 edges. It was first mentioned in Brinkmann (1992) and first published as a note in Brinkmann and Meringer (1997). It is implemented in the Wolfram Language as GraphData["BrinkmannGraph"].

Grünbaum conjectured that for every integer m>1, n>2, there exists an m-regular, m-chromatic graph of girth at least n. This result is trivial for n=2 and m=2,3, but only a small number of other such graphs are known, including the Brinkmann graph, illustrated above, Chvátal graph, and 25-Grünbaum graph.


The plots above show the adjacency, incidence, and distance matrices of the graph.

See also

Chvátal Graph, Grünbaum Graphs, Quartic Graph, Weakly Regular Graph

Explore with Wolfram|Alpha


Bollobás, B. Modern Graph Theory. New York: Springer-Verlag, 1998.Brinkmann, G. "Generating Cubic Graphs Faster Than Isomorphism Checking." Preprint 92-047 SFB 343. Bielefeld, Germany: University of Bielefeld, 1992.Brinkmann, G. and Meringer, M. "The Smallest 4-Regular 4-Chromatic Graphs with Girth 5." Graph Theory Notes of New York 32, 40-41, 1997.Cancela, H.; Robledo, F.; and Rubino, G. "A GRASP Algorithm with Tree Based Local Search for Designing a Survivable Wide Area Network Backbone." J. Computer Sci. Technol. 4, 52-58, 2004.ünbaum, B. "A Problem in Graph Coloring." Amer. Math. Monthly 77, 1088-1092, 1970.

Cite this as:

Weisstein, Eric W. "Brinkmann Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications