The Gewirtz graph is a

strongly regular graph In graph theory, a strongly regular graph (SRG) is defined as follows. Let be a regular graph with vertices and degree . is said to be strongly regular if there are also integers and such that: * Every two adjacent vertices have comm ...

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 250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line. In combinatorial mathematics, a Steiner system (named after Jakob Steine ...

, 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 In mathematical graph theory, the Higman–Sims graph is a 22-regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph srg(100,22,0,6), where no neighboring pair of vertices share a common neighbor and e ...

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

of the Gewirtz graph is :

(x-10)(x-2)^(x+4)^. \,

Therefore, it is an integral graph. 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