A two-graph is a finite set provided with a collection of triples, called coherent, such that each 4-set contains an even number of coherent triples. The two-graph is called regular when each pair of points is contained in the same number of coherent triples. Trivial two-graphs are obtained by taking no triples, or all triples.
Given a graph Γ on a set V of vertices, one obtains a two-graph by taking all triples that contain an odd number of edges of Γ. Every two-graph arises in this way. (One can for example stipulate that a given vertex p must be isolated, and then qr must be an edge precisely when pqr is a coherent triple.) A graph and its complement give rise to two-graphs with complementary sets of coherent triples.
Two graphs Γ, Δ with the same vertex set V are called switching equivalent when V is the disjoint union of subsets A and B, and Γ and Δ induce the same subgraph on A and on B, but vertices a ∈ A and b ∈ B are joined in Γ iff they are not joined in Δ. Being switching equivalent is an equivalence relation, and two graphs are switching equivalent precisely when they give rise to the same two-graph.
The Seidel adjacency matrix of a graph Γ is the matrix S = J−I−2A that has zero diagonal, −1 for adjacency, and 1 for nonadjacency. If Γ and Δ are switching equivalent, their Seidel adjacency matrices have the same spectrum. This common spectrum is called the Seidel spectrum of the two-graph. The Seidel spectrum of the complementary two-graph equals minus the Seidel spectrum of a given two-graph.
|Clebsch graph||(16,10,6,6)||101 25 (−2)10||(−5)6 310|
|Shrikhande graph, |
Hamming graph H(2,4)
|(16,6,2,2)||61 26 (−2)9||(−5)6 310|
|K1+T(6)||81 25 01 (−2)9||(−5)6 310|
|complement of Clebsch graph||(16,5,0,2)||51 110 (−3)5||56 (−3)10|
|complement of Shrikhande,
complement of H(2,4)
|(16,9,4,6)||91 19 (−3)6||56 (−3)10|
|cone over GQ(2,2)||(3 ± 2√6)1 19 (−3)5||56 (−3)10|
The automorphism group of the regular two-graph here is 24:Sym(6) of order 11520. The automorphism groups of the graphs in its switching class are subgroups.