Two-graph
Encyclopedia
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. A regular two-graph has the property that every pair of vertices lies in the same number of triples of the two-graph. Two-graphs have been studied because of their connection with equiangular lines
and, for regular two-graphs, strongly regular graph
s, and also finite group
s because many regular two-graphs have interesting automorphism groups.
A two-graph should not be confused with other objects called 2-graphs in graph theory
, such as 2-regular graphs
.
Switching a set of vertices in a (simple) graph means reversing the adjacencies of each pair of vertices, one in the set and the other not in the set: thus the edge set is changed so that an adjacent pair becomes nonadjacent and a nonadjacent pair becomes adjacent. The edges whose endpoints are both in the set, or both not in the set, are not changed. Graphs are switching equivalent if one can be obtained from the other by switching. An equivalence class of graphs under switching is called a switching class. Switching was introduced by van Lint and Seidel (1966) and developed by Seidel; it has been called graph switching or Seidel switching, partly to distinguish it from switching of signed graphs.
Given a graph G, there is a corresponding two-graph on the same vertex set whose triples consist of the sets of three vertices that contain an odd number of edges of G. Two graphs yield the same two-graph if and only if they are equivalent under switching.
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. The two-graph of G can also be defined as the set of triples of vertices that support a negative triangle in Σ. Two signed complete graphs yield the same two-graph if and only if they are equivalent under switching.
Switching of G and of Σ are related: switching the same vertices in both yields a graph H and its corresponding signed complete graph.
If graphs G and H are in a same switching class, the multiset of eigenvalues of two Seidel adjacency matrices
of G and H coincide.
of G. The Seidel matrix is a fundamental tool in the study of two-graphs, especially regular two-graphs.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, 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. A regular two-graph has the property that every pair of vertices lies in the same number of triples of the two-graph. Two-graphs have been studied because of their connection with equiangular lines
Equiangular lines
In geometry, a set of lines in Euclidean space is called equiangular if every pair of lines makes the same angle.Equiangular lines are related to two-graphs....
and, for regular two-graphs, strongly regular graph
Strongly regular graph
In graph theory, a discipline within mathematics, a strongly regular graph is defined as follows. Let G = be a regular graph with v vertices and degree k...
s, and also finite group
Finite group
In mathematics and abstract algebra, a finite group is a group whose underlying set G has finitely many elements. During the twentieth century, mathematicians investigated certain aspects of the theory of finite groups in great depth, especially the local theory of finite groups, and the theory of...
s because many regular two-graphs have interesting automorphism groups.
A two-graph should not be confused with other objects called 2-graphs in graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, such as 2-regular graphs
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
.
Switching and graphs
A two-graph is equivalent to a switching class of graphs and also to a (signed) switching class of signed complete graphs.Switching a set of vertices in a (simple) graph means reversing the adjacencies of each pair of vertices, one in the set and the other not in the set: thus the edge set is changed so that an adjacent pair becomes nonadjacent and a nonadjacent pair becomes adjacent. The edges whose endpoints are both in the set, or both not in the set, are not changed. Graphs are switching equivalent if one can be obtained from the other by switching. An equivalence class of graphs under switching is called a switching class. Switching was introduced by van Lint and Seidel (1966) and developed by Seidel; it has been called graph switching or Seidel switching, partly to distinguish it from switching of signed graphs.
Given a graph G, there is a corresponding two-graph on the same vertex set whose triples consist of the sets of three vertices that contain an odd number of edges of G. Two graphs yield the same two-graph if and only if they are equivalent under switching.
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. The two-graph of G can also be defined as the set of triples of vertices that support a negative triangle in Σ. Two signed complete graphs yield the same two-graph if and only if they are equivalent under switching.
Switching of G and of Σ are related: switching the same vertices in both yields a graph H and its corresponding signed complete graph.
If graphs G and H are in a same switching class, the multiset of eigenvalues of two Seidel adjacency matrices
Seidel adjacency matrix
In mathematics, in graph theory, the Seidel adjacency matrix of a simple graph G is the symmetric matrix with a row and column for each vertex, having 0 on the diagonal and, in the positions corresponding to vertices vi and vj, −1 if the vertices are adjacent...
of G and H coincide.
Adjacency matrix
The adjacency matrix of a two-graph is the adjacency matrix of any corresponding signed complete graph; thus it is symmetric, is zero on the diagonal, and has entries ±1 off the diagonal. If G is the graph corresponding to Σ, this matrix is called the (0, −1, 1)-adjacency matrix or Seidel adjacency matrixSeidel adjacency matrix
In mathematics, in graph theory, the Seidel adjacency matrix of a simple graph G is the symmetric matrix with a row and column for each vertex, having 0 on the diagonal and, in the positions corresponding to vertices vi and vj, −1 if the vertices are adjacent...
of G. The Seidel matrix is a fundamental tool in the study of two-graphs, especially regular two-graphs.