From Surf Wiki (app.surf) — the open knowledge base
Brinkmann graph
| Field | Value | |
|---|---|---|
| name | Brinkmann graph | |
| image | Brinkmann graph LS.svg | |
| image_caption | The Brinkmann graph | |
| namesake | Gunnar Brinkmann | |
| vertices | 21 | |
| edges | 42 | |
| automorphisms | 14 (D7) | |
| girth | 5 | |
| radius | 3 | |
| diameter | 3 | |
| chromatic_number | 4 | |
| chromatic_index | 5 | |
| properties | Eulerian | |
| Hamiltonian | ||
| book thickness | 3 | queue number=2 |
Hamiltonian
In the mathematical field of graph theory, the Brinkmann graph is a 4-regular graph with 21 vertices and 42 edges discovered by Gunnar Brinkmann in 1992. It was first published by Brinkmann and Meringer in 1997.
It has chromatic number 4, chromatic index 5, radius 3, diameter 3 and girth 5. It is also a 3-vertex-connected graph and a 3-edge-connected graph. It is the smallest 4-regular graph of girth 5 with chromatic number 4. It has book thickness 3 and queue number 2.
By Brooks’ theorem, every k-regular graph (except for odd cycles and cliques) has chromatic number at most k. It was also known since 1959 that, for every k and l there exist k-chromatic graphs with girth l.{{citation
The chromatic polynomial of the Brinkmann graph is x21 − 42x20 + 861x19 − 11480x18 + 111881x17 − 848708x16 + 5207711x15 − 26500254x14 + 113675219x13 − 415278052x12 + 1299042255x11 − 3483798283x10 + 7987607279x9 − 15547364853x8 + 25384350310x7 − 34133692383x6 + 36783818141x5 − 30480167403x4 + 18168142566x3 − 6896700738x2 + 1242405972x .
Algebraic properties
The Brinkmann graph is not a vertex-transitive graph and its full automorphism group is isomorphic to the dihedral group of order 14, the group of symmetries of a heptagon, including both rotations and reflections.
The characteristic polynomial of the Brinkmann graph is (x-4)(x-2)(x+2)(x^3-x^2-2x+1)^2(x^6+3x^5-8x^4-21x^3+27x^2+38x-41)^2.
Gallery
File:Brinkmann graph.svg|Alternative drawing of Brinkmann Graph. File:Brinkmann graph 4COL.svg|The chromatic number of the Brinkmann graph is 4. File:Brinkmann graph 5color edge.svg|The chromatic index of the Brinkmann graph is 5.
References
References
- 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.
- Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018
This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.
Ask Mako anything about Brinkmann graph — get instant answers, deeper analysis, and related topics.
Research with MakoFree with your Surf account
Create a free account to save articles, ask Mako questions, and organize your research.
Sign up freeThis content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.
Report