Two-graph

Last updated

In mathematics, a two-graph is a set of unordered triples chosen from a finite vertex setX, 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 graphs, and also finite groups because many regular two-graphs have interesting automorphism groups.

Contents

A two-graph is not a graph and should not be confused with other objects called 2-graphs in graph theory, such as 2-regular graphs.

Examples

On the set of vertices {1,...,6} the following collection of unordered triples is a two-graph:

123  124  135  146  156  236  245  256  345  346

This two-graph is a regular two-graph since each pair of distinct vertices appears together in exactly two triples.

Given a simple graph G = (V,E), the set of triples of the vertex set V whose induced subgraph has an odd number of edges forms a two-graph on the set V. Every two-graph can be represented in this way. [1] This example is referred to as the standard construction of a two-graph from a simple graph.

As a more complex example, let T be a tree with edge set E. The set of all triples of E that are not contained in a path of T form a two-graph on the set E. [2]

Switching and graphs

Switching {X,Y} in a graph Xyswitch.svg
Switching {X,Y} in a graph

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 & Seidel (1966) and developed by Seidel; it has been called graph switching or Seidel switching, partly to distinguish it from switching of signed graphs.

In the standard construction of a two-graph from a simple graph given above, two graphs will yield the same two-graph if and only if they are equivalent under switching, that is, they are in the same switching class.

Let Γ be a two-graph on the set X. 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 Γ. In this graph, x will be an isolated vertex. This construction is reversible; given a simple graph G, adjoin a new element x to the set of vertices of G, retaining the same edge set, and apply the standard construction above. This two-graph is called the extension of G by x in design theoretic language. [3] In a given switching class of graphs of a regular two-graph, let Γx be the unique graph having x as an isolated vertex (this always exists, just take any graph in the class and switch the open neighborhood of x) without the vertex x. That is, the two-graph is the extension of Γx by x. In the first example above of a regular two-graph, Γx is a 5-cycle for any choice of x. [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. The two-graph of G can also be defined as the set of triples of vertices that support a negative triangle (a triangle with an odd number of negative edges) 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.

Adjacency matrix

The adjacency matrix of a two-graph is the adjacency matrix of the 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 the signed complete graph Σ, this matrix is called the (0, −1, 1)-adjacency matrix or Seidel adjacency matrix of G. The Seidel matrix has zero entries on the main diagonal, -1 entries for adjacent vertices and +1 entries for non-adjacent vertices.

If graphs G and H are in a same switching class, the multisets of eigenvalues of the two Seidel adjacency matrices of G and H coincide, since the matrices are similar. [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]

Equiangular lines

Every two-graph is equivalent to a set of lines in some dimensional euclidean space each pair of which meet in the same angle. The set of lines constructed from a two graph on n vertices is obtained as follows. Let -ρ be the smallest eigenvalue of the Seidel adjacency matrix, A, of the two-graph, and suppose that it has multiplicity n - d. Then the matrix ρI + A is positive semi-definite of rank d and thus can be represented as the Gram matrix of the inner products of n vectors in euclidean d-space. As these vectors have the same norm (namely, ) and mutual inner products ±1, any pair of the n lines spanned by them meet in the same angle φ where cos φ = 1/ρ. Conversely, any set of non-orthogonal equiangular lines in a euclidean space can give rise to a two-graph (see equiangular lines for the construction). [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.

Strongly regular graphs

The two-graphs on X consisting of all possible triples of X and no triples of X are regular two-graphs and are considered to be trivial two-graphs.

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). If this condition holds for one x in X, it holds for all the elements of X. [8]

It follows that a non-trivial regular two-graph has an even number of points.

If G is a regular graph whose two-graph extension is Γ having n points, then Γ is a regular two-graph if and only if G is a strongly regular graph with eigenvalues k, r and s satisfying n = 2(k - r) or n = 2(k - s). [9]

Notes

  1. ↑ Colbourn & Dinitz 2007 , p. 876, Remark 13.2
  2. ↑ Cameron, P.J. (1994), "Two-graphs and trees", Discrete Mathematics, 127: 63–74, doi:10.1016/0012-365x(92)00468-7 cited in Colbourn & Dinitz 2007 , p. 876, Construction 13.12
  3. ↑ Cameron & van Lint 1991 , pp. 58-59
  4. ↑ Cameron & van Lint 1991 , p. 62
  5. ↑ Cameron & van Lint 1991 , p. 61
  6. ↑ Colbourn & Dinitz 2007 , p. 878 #13.24
  7. ↑ van Lint & Seidel 1966
  8. ↑ Cameron & van Lint 1991 , p. 62 Theorem 4.11
  9. ↑ Cameron & van Lint 1991 , p. 62 Theorem 4.12

Related Research Articles

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

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 internal vertex are equal to each other. A regular graph with vertices of degree k is called a k‑regular graph or regular graph of degree k.

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Graph (discrete mathematics)</span> Vertices connected in pairs by edges

In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix.

<span class="mw-page-title-main">Graph (abstract data type)</span> Abstract data type in computer science

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics.

<span class="mw-page-title-main">Strongly regular graph</span> Concept in graph theory

In graph theory, a strongly regular graph (SRG) is a regular graph G = (V, E) with v vertices and degree k such that for some given integers

<span class="mw-page-title-main">Centrality</span> Degree of connectedness within a graph

In graph theory and network analysis, indicators of centrality assign numbers or rankings to nodes within a graph corresponding to their network position. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, super-spreaders of disease, and brain networks. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin.

In geometry, a set of lines is called equiangular if all the lines intersect at a single point, and every pair of lines makes the same angle.

Combinatorial design theory is the part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of balance and/or symmetry. These concepts are not made precise so that a wide range of objects can be thought of as being under the same umbrella. At times this might involve the numerical sizes of set intersections as in block designs, while at other times it could involve the spatial arrangement of entries in an array as in sudoku grids.

<span class="mw-page-title-main">Coxeter graph</span> Cubic graph with 28 vertices and 42 edges

In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter.

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graphQn is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Qn has 2n vertices, 2n – 1n edges, and is a regular graph with n edges touching each vertex.

In mathematics, in graph theory, the Seidel adjacency matrix of a simple undirected graph G is a symmetric matrix with a row and column for each vertex, having 0 on the diagonal, −1 for positions whose rows and columns correspond to adjacent vertices, and +1 for positions corresponding to non-adjacent vertices. It is also called the Seidel matrix or—its original name—the (−1,1,0)-adjacency matrix. It can be interpreted as the result of subtracting the adjacency matrix of G from the adjacency matrix of the complement of G.

<span class="mw-page-title-main">Clebsch graph</span> One of two different regular graphs with 16 vertices

In the mathematical field of graph theory, the Clebsch graph is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge graph is the dimension-5 halved cube graph; it was called the Clebsch graph name by Seidel (1968) because of its relation to the configuration of 16 lines on the quartic surface discovered in 1868 by the German mathematician Alfred Clebsch. The 40-edge variant is the dimension-5 folded cube graph; it is also known as the Greenwood–Gleason graph after the work of Robert E. Greenwood and Andrew M. Gleason, who used it to evaluate the Ramsey number R(3,3,3) = 17.

<span class="mw-page-title-main">Schläfli graph</span>

In the mathematical field of graph theory, the Schläfli graph, named after Ludwig Schläfli, is a 16-regular undirected graph with 27 vertices and 216 edges. It is a strongly regular graph with parameters srg(27, 16, 10, 8).

<span class="mw-page-title-main">Locally linear graph</span> Graph where every edge is in one triangle

In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be paired up into an induced matching. Locally linear graphs have also been called locally matched graphs. Their triangles form the hyperedges of triangle-free 3-uniform linear hypergraphs and the blocks of certain partial Steiner triple systems, and the locally linear graphs are exactly the Gaifman graphs of these hypergraphs or partial Steiner systems.

<span class="mw-page-title-main">Conway's 99-graph problem</span> On existence of a strongly regular graph

In graph theory, Conway's 99-graph problem is an unsolved problem asking whether there exists an undirected graph with 99 vertices, in which each two adjacent vertices have exactly one common neighbor, and in which each two non-adjacent vertices have exactly two common neighbors. Equivalently, every edge should be part of a unique triangle and every non-adjacent pair should be one of the two diagonals of a unique 4-cycle. John Horton Conway offered a $1000 prize for its solution.

<span class="mw-page-title-main">Berlekamp–Van Lint–Seidel graph</span>

In graph theory, the Berlekamp–Van Lint–Seidel graph is a locally linear strongly regular graph with parameters . This means that it has 243 vertices, 22 edges per vertex, exactly one shared neighbor per pair of adjacent vertices, and exactly two shared neighbors per pair of non-adjacent vertices. It was constructed by Elwyn Berlekamp, J. H. van Lint, and Johan Jacob Seidel as the coset graph of the ternary Golay code.

In graph theory, the Games graph is the largest known locally linear strongly regular graph. Its parameters as a strongly regular graph are (729,112,1,20). This means that it has 729 vertices, and 40824 edges. Each edge is in a unique triangle and each non-adjacent pair of vertices have exactly 20 shared neighbors. It is named after Richard A. Games, who suggested its construction in an unpublished communication and wrote about related constructions.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.