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 
, 
, there exists an 
-regular, 
-chromatic graph of girth at least
. This result is trivial for 
and 
, 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
References
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. http://journal.info.unlp.edu.ar/journal/journal10/papers/JCST-Apr04-8.pdf.Grünbaum, B. "A Problem in Graph Coloring." Amer. Math. Monthly 77, 1088-1092, 1970.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Brinkmann Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BrinkmannGraph.html