Gewirtz graph
The Gewirtz graph is a strongly regular graph with 56 vertices and valency 10. It is named after the mathematician Allan Gewirtz, who described the graph in his dissertation.[1]
| Gewirtz graph | |
|---|---|
 Some embeddings with 7-fold symmetry. No 8-fold or 14-fold symmetry are possible. | |
| Vertices | 56 |
| Edges | 280 |
| Radius | 2 |
| Diameter | 2 |
| Girth | 4 |
| Automorphisms | 80,640 |
| Chromatic number | 4 |
| Properties | Strongly regular Hamiltonian Triangle-free Vertex-transitive Edge-transitive Distance-transitive. |
| Table of graphs and parameters | |
Construction
The Gewirtz graph can be constructed as follows. Consider the unique S(3, 6, 22) Steiner system, with 22 elements and 77 blocks. Choose a random element, and let the vertices be the 56 blocks not containing it. Two blocks are adjacent when they are disjoint.
With this construction, one can embed the Gewirtz graph in the Higman–Sims graph.
Properties
The characteristic polynomial of the Gewirtz graph is
Therefore, it is an integral graph. The Gewirtz graph is also determined by its spectrum.
The independence number is 16.
Notes
- Allan Gewirtz, Graphs with Maximal Even Girth, Ph.D. Dissertation in Mathematics, City University of New York, 1967.
gollark: You probably want to revert that when the program *exits*.
gollark: > Which is exactly what they wanted here!Not necessarily, this actually does sound like a case where they might want each task to run in its own coroutines (or would, if their pathfinding did yields).
gollark: I mean, it's great for very simple situations where you want to run two things at once in the simplest case, but often projects want to run a listener "thread" and temporarily spawn tasks to handle them or something and this ends up being constantly reinvented.
gollark: > Thanks for that gollark :/.You're welcome! It would be useful if there was an API for this! Perhaps I could simplify some of my stuff and make a PR!
gollark: Parallel isn't great because you can't add an extra task after it starts.
References
- Brouwer, Andries. "Sims-Gewirtz graph".
- Weisstein, Eric W. "Gewirtz graph". MathWorld.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.