TOPICS

# 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 , , 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.

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

## Explore with Wolfram|Alpha

More things to try:

## 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.

## Cite this as:

Weisstein, Eric W. "Brinkmann Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BrinkmannGraph.html