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 G {\displaystyle G} at a vertex v {\displaystyle v} is an operation that produces a new graph, denoted by G ⋆ v {\displaystyle G\star v} . This operation is defined by replacing the subgraph of G {\displaystyle G} induced by N G ( v ) {\displaystyle N_{G}(v)} with its complementary subgraph. In other words, two distinct vertices x {\displaystyle x} and y {\displaystyle y} are adjacent in the graph G ⋆ v {\displaystyle G\star v} when exactly one of the following holds:
vertices x {\displaystyle x} and y {\displaystyle y} are adjacent in G {\displaystyle G} ; or both vertices x {\displaystyle x} and y {\displaystyle y} are neighbours of v {\displaystyle v} in G {\displaystyle G} . 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 n {\displaystyle n} 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 3 n {\displaystyle 3^{n}} , 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 | G ⟩ {\displaystyle |G\rangle } , the action of the local Clifford operation is equivalent to the local complementation transformation on the graph G {\displaystyle G} . 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).
… excerpt ends here. Continue reading the full article.
