Two-graph

In mathematics, a two-graph is a set of unordered triples chosen from a finite vertex set X, such that every unordered quadruple from X contains an even number of triples of the two-graph.

For any element x of X, define a graph with vertex set X having vertices y and z adjacent if and only if {x, y, z} is in Γ.

This two-graph is called the extension of G by x in design theoretic language.

[4] To a graph G there corresponds a signed complete graph Σ on the same vertex set, whose edges are signed negative if in G and positive if not in G. Conversely, G is the subgraph of Σ that consists of all vertices and all negative edges.

Two signed complete graphs yield the same two-graph if and only if they are equivalent under switching.

[5] A two-graph on a set V is regular if and only if its adjacency matrix has just two distinct eigenvalues ρ1 > 0 > ρ2 say, where ρ1ρ2 = 1 - |V|.

[6] Every two-graph is equivalent to a set of lines in some dimensional euclidean space each pair of which meet in the same angle.

[7] With the notation as above, the maximum cardinality n satisfies n ≤ d(ρ2 - 1)/(ρ2 - d) and the bound is achieved if and only if the two-graph is regular.

For non-trivial two-graphs on the set X, the two-graph is regular if and only if for some x in X the graph Γx is a strongly regular graph with k = 2μ (the degree of any vertex is twice the number of vertices adjacent to both of any non-adjacent pair of vertices).