Up

Two-graphs

Regular two-graphs were introduced by G. Higman in order to study permutation representations of doubly transitive groups, and, in particular, the action of Co.3 on 276 points. The concept of switching class is due to J. J. Seidel, who studied equiangular systems of lines in a Euclidean space.

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.

Example: the regular two-graph on 16 points

There is a unique complementary pair of nontrivial regular two-graphs on 16 points. They have Seidel spectrum (−5)6 310 and 56 (−3)10. The switching class of the former contains the strongly regular graphs with parameters (16,10,6,6) and (16,6,2,2), that is, the Clebsch graph, and the Shrikhande graph and the lattice graph H(2,4). It also contains the graph K1+T(6), the disjoint union of the triangular graph T(6) and an isolated point. The switching class of the latter contains the complements of these graphs. These six graphs have the following spectra.

graph parameters spectrum Seidel spectrum
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.