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.
Allan Gewirtz
''Graphs with Maximal Even Girth'', Ph.D. Dissertation in Mathematics, City University of New York, 1967.
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
In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The chara ...
of the Gewirtz graph is
:
Therefore, it is an integral graph In the mathematical field of graph theory, an integral graph is a graph whose adjacency matrix's spectrum consists entirely of integers. In other words, a graph is an integral graph if all of the roots of the characteristic polynomial of its adjace ...
. The Gewirtz graph is also determined by its spectrum.
The independence number
Independence is a condition of a person, nation, country, or Sovereign state, state in which residents and population, or some portion thereof, exercise self-government, and usually sovereignty, over its territory. The opposite of independ ...
is 16.
Notes
References
*
* {{MathWorld, title=Gewirtz graph, urlname=GewirtzGraph
Individual graphs
Regular graphs
Strongly regular graphs