In graph theory, local complementation (also known as vertex inversion) is an operation on a graph that toggles adjacencies among the neighbours of a chosen vertex, while all other adjacencies remain unchanged. Despite its simple definition, it preserves interesting properties and generates a complex equivalence relation. The operation was introduced by Anton Kotzig and later studied in depth by André Bouchet and Von-Der-Flaass.
Formally, the local complementation of a simple undirected graph at a vertex is an operation that produces a new graph, denoted by . This operation is defined by replacing the subgraph of induced by with its complementary subgraph. In other words, two distinct vertices and are adjacent in the graph when exactly one of the following holds:
vertices and are adjacent in ; or both vertices and are neighbours of in . Two graphs are said to be locally equivalent if one can be obtained from the other through a sequence of local complementations. This defines an equivalence relation on graphs, whose equivalence classes are known as local equivalence classes. For example, the star graph and complete graph on vertices are locally equivalent, and they form a local equivalence class. The local equivalence classes on graphs with up to 12 vertices has been computed. The size of a local equivalence class is at most , and this collection of graphs can be enumerated efficiently.
Applications
Structural graph theory The Robertson–Seymour theorem states that the graph minor relation is a well-quasi ordering. It was proved in a series of twenty papers spanning over 500 pages from 1983 to 2004. The algorithmic consequences are vast - together with an efficient algorithm for graph minor testing, the result provides efficient algorithms for solving a range of computational problems where the optimal value is monotonic in the graph minor relation.
Local complementations are central to the vertex-minor relation, which shares many similarities with the graph minor relation. Better understanding of the local complementation operation could extend the Robertson–Seymour theorem to prove that the vertex-minor relation is also a well-quasi ordering.
Measurement based quantum computing For a given the graph state , the action of the local Clifford operation is equivalent to the local complementation transformation on the graph . The study of graph states that are locally equivalent is relevant to building quantum circuits in measurement based quantum computing (MBQC)
The local unitary operation is related but may produce a different equivalent class. Results suggest that LU-equivalence and LC-equivalence coincide for graph with up to 26 vertices.
Similarly, local complementation is also related to state preparation in photonic quantum computing (PQC).
Properties The local complement operation is self inverse; that is, . Local complementations commute only when vertices are non-adjacent; that is, unless . Connected components are preserved by the local complementation operation, so it is common analyse each component of the graph independently. So without loss of generality, all graphs will be assumed to be connected. All locally equivalent graphs can be reached after a sequence of at most local complementations. Locally equivalent trees are isomorphic (Mulder's conjecture), and there exists a simple expression to count such trees. If a graph is locally equivalent to a tree, it has a subgraph isomorphic to that tree. If a graph is locally equivalent to the cycle graph, it contains a Hamiltonian cycle. If a graph is locally equivalent to its complement, it is self-complementary. The number of essentially different ways of transforming one graph into another via local complementation is or for some . Any class of locally equivalent distance-hereditary graphs is equal to the class of the circle graphs of the Euler tours of some 4-regular graph. Locally equivalent graphs have the same rank-width. Counting the number of locally equivalent graphs is #P-complete. Determining the minimum degree that can be reached by means of local complementation is NP-complete and APX-hard, and can be computed by an algorithm. Determining the minimum total edge weight by means of local complementation is NP-complete. Determining the minimum number of edges by means of pivots is NP-complete. Determining the minimum number of edges by means of local complementation is likely NP-complete.
Pivot operation Local complementations do not commute for adjacent vertices, motivating the following operation that performs complementations at adjacent vertices.
For adjacent vertices and , the pivot operation (also historically known as an edge complementation) is defined asIt can be shown that , and hence the pivot operation is well defined. Alternatively, the graph can be obtained from by toggling adjacencies between every pair of vertices in two different sets among , and then switching the labels and . The pivot operation satisfies the identities and .
Two graphs are said to be pivot equivalent if one can be obtained from the other through a sequence of pivot operations. Since pivot operations consist of local complementation operations, pivot equivalent graphs are locally equivalent. The converse is true for bipartite graphs, but is not generally true. If and are pivot equivalent graphs, there are pairwise disjoint edges such that . Fon-Der-Flass proved that if graphs and are locally equivalent, they are pivot equivalent to some and respectively such that and is an independent set in and .
The size of a pivot equivalence class is at most , and this collection of graphs can be enumerated efficiently.
Pivot equivalence has been studied using even binary delta-matroids.
Invariants
Cut-rank function As a graph undergoes local complementation, its adjacency matrix changes in a well defined way. In particular, the entries that change are exactly some sub-matrix (excluding the main diagonal). Hence, it may be natural to study the local complementation operation using linear algebra.
For a graph with vertex set , the cut-rank function (also historically known as the connectivity function) is denoted . It is defined over the vertex subsets such that is the rank of the bi-adjacency matrix of the partition , defined over the finite field GF(2). That is, the rank of the binary matrix where when is an edge in . Intuitively, is a measure of how complex the connectivity is between vertex set and the remaining vertices.
Since the rank of a matrix is preserved by elementary row and column operations, a straightforward argument shows that locally equivalent graphs have identical cut-rank functions. However, the converse is not true — a counterexample can be constructed using labelled Petersen graphs. It is known that bipartite graphs with identical cut-rank functions are pivot-equivalent, and so locally equivalent bipartite graphs are also pivot-equivalent.
The cut-rank function is submodular since it can be shown that for any vertex set and . However, it is not monotone.
Local sets Since the cut-rank is invariant over local complementation, so are the sets with a particular cut-rank. The sets of rank 1 are studied using canonical split decompositions in a later section. Here, we define a local set as a vertex set which does not have full cut-rank.
Define A set of vertices is local in if for some subset . Now if is local in , it is also local in any graph locally equivalent to . Local sets can equivalently be defined as the sets of vertices which do not have full cut-rank (i.e. the sets where ). Intuitively, a local set is some linear combination of the closed neighbourhoods of . Local sets are used to study the degrees of vertices in .
This invariant may be a helpful tool to quickly show that graphs are not locally equivalent. However, there are graphs with the same local sets which are not locally equivalent, since there are graphs with identical cut-rank functions which are not locally equivalent.
Totally isotropic subspaces The richest description of a class of locally equivalent graphs is an extension of the local sets idea, involving a linear algebra structure over the Klein four-group. Each locally equivalent graph, equipped with two specific vectors, corresponds to some graphic presentations of the same totally isotropic subspace.
Let be the Klein four-group. A vector is said to be complete if is nonzero for every . Two vectors are said to be supplementary if and are nonzero and distinct for every . For a set , define as the vector where if , and otherwise.
A subspace of is called a totally isotropic subspace if , and every two complete vectors in are not supplementary.
A graphic presentation of a totally isotropic subspace is a triple where is a simple graph on the vertex set and and are supplementary vectors of , such that is spanned by the set For a fixed , there is a one-to-one correspondence between every graphic presentation and every complete vector where , the vectors here are known are Eulerian vectors. Furthermore, if is a graphic presentation of , so is and The fundamental graphs of form a local equivalence class. These facts leads to important results about determining local equivalence and locally equivalent class sizes, which is discussed in the next 2 sections.
This structure can be considered as an extension of the local sets structure, since , and when , .
Totally isotropic subspaces (modern interpretation) Brijder and Traldi introduce the isotropic matroid which is equivalent to the isotropic system introduced by Bouchet above. Let denote the adjacency matrix of and let denote the identity matrix. The binary matroid represented by the matrix is denoted , and called the isotropic matroid of . Now graphs and are locally equivalent (up to isomorphism) if and only if the binary matroids and are isomorphic. This classification of local equivalence classes allows a natural study of the minimum degree and independence number of locally equivalent graphs.
Characterisation of local equivalence The following characterisations of locally equivalent graphs are straightforward results using totally isotropic subspaces. This leads to an efficient algorithm to recognise locally equivalent graphs.
Let and be simple graphs and fix supplementary vectors and . he graphs and are locally equivalent if and only if there are supplementary vectors and such that and are graphic presentations of the same totally isotropic subspace. The existence of such vectors and can be determined in by solving a system of linear equations. A modification to this algorithm can, with the same time complexity, recover a sequence of at most local complementations transforming into .
An equivalent characterisation can be formulated using vertex sets. Let and denote the neighbourhood functions of and respectively. Then graphs and are locally equivalent if and only if there are vertex subsets such that for every pair of vertices , and the symmetric difference of with is the entire vertex set.
Global interlace polynomial The global interlace polynomial (also known as the Tutte-Martin polynomial), is a polynomial that corresponds to a simple graph . It is defined recursively asNow if and are locally equivalent, for any . Additionally,
is a multiple of the number of graphs locally equivalent to . In particular, if is a fundamental graph of a totally isotropic subspace , this gives the number of Eulerian vectors in . is the number of induced Eulerian subgraphs in . (A graph is called Eulerian all degrees are even, even if it is disconnected). A surprising corollary is that locally equivalent graphs have the same number of induced Eulerian subgraphs. is the largest independent number of the graph locally equivalent to .
The polynomial has closed-form formulas in certain cases:
The path graphs have the closed form where and .