In graph theory, the local complementation (also known as a vertex inversion) of a simple undirected graph ${\displaystyle G}${\displaystyle G} at a vertex ${\displaystyle v}${\displaystyle v} is an operation that produces a new graph, denoted by ${\displaystyle G\star v}${\displaystyle G\star v}. This operation is defined by toggling the adjacencies between all pairs of neighbors of ${\displaystyle v}${\displaystyle v} in ${\displaystyle G}${\displaystyle G}. Formally, two distinct vertices ${\displaystyle x}${\displaystyle x} and ${\displaystyle y}${\displaystyle y} are adjacent in ${\displaystyle G\star v}${\displaystyle G\star v} if and only if exactly one of the following holds:

1. ${\displaystyle x}${\displaystyle x} and ${\displaystyle y}${\displaystyle y} are adjacent in G; or
2. both ${\displaystyle x}${\displaystyle x} and ${\displaystyle y}${\displaystyle y} are neighbours of ${\displaystyle v}${\displaystyle v} in ${\displaystyle G}${\displaystyle G}.

Equivalently, the local complementation at ${\displaystyle v}${\displaystyle v} replaces the subgraph of ${\displaystyle G}${\displaystyle G} induced by ${\displaystyle N_{G}(v)}${\displaystyle N_{G}(v)} with its complementary subgraph.

The concept was introduced by Anton Kotzig and later studied in depth by André Bouchet and Von-Der-Flaass.

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 a positive integer ${\displaystyle n}${\displaystyle n}, the star graph and complete graph on ${\displaystyle n}${\displaystyle n} vertices forms a trivial local equivalence class. The local equivalence classes on graphs up to 12 vertices is known^{[1] [2]} .

Using ideas from isotropic subsystems, Bouchet^[3] introduced a ${\displaystyle {\mathcal {O}}(n^{3})}${\displaystyle {\mathcal {O}}(n^{3})} algorithm to determine whether two graphs are locally equivalent.

Bouchet proved a conjecture that locally equivalent trees are isomorphic, and gives a simple closed form expression for number of such trees. Furthermore, if a graph ${\displaystyle G}${\displaystyle G} is locally equivalent to a tree ${\displaystyle T}${\displaystyle T}, then ${\displaystyle G}${\displaystyle G} has a subgraph isomorphic to ${\displaystyle T}${\displaystyle T}^[4] .

If ${\displaystyle |G\rangle }${\displaystyle |G\rangle } represents a graph state in quantum computing, the action of the local Clifford operation on the graph state is roughly equivalent^[5] to the local complementation transformation on the graph. The study of graph states that are locally Clifford equivalent graphs is relevant to building quantum circuits in measurement based quantum computing (MBQC) ^[1] .

1. The local complement operation is self inverse ${\displaystyle (G\star v)\star v=G}${\displaystyle (G\star v)\star v=G}.

1. Local complementations do not, in general, commute; that is, ${\displaystyle (G\star v)\star w\neq (G\star w)\star v}${\displaystyle (G\star v)\star w\neq (G\star w)\star v} in general.
2. Connected components are preserved by the local complementation operation, so it is common analyse each component of ${\displaystyle G}${\displaystyle G} independently. Without loss of generality, we assume that ${\displaystyle G}${\displaystyle G} is connected.
3. Any class of locally equivalent distance-hereditary graphs is equal to the class of the circle graphs of the Euler tours of some ${\displaystyle 4}${\displaystyle 4}-regular graph.
4. Dahlberg, Helsen, and Wehner^[6] proved that counting locally equivalent graphs is #P-complete by reducing this problem on circle graphs to the problem of counting Eulerian circuits in a 4-regular graph.

If ${\displaystyle G}${\displaystyle G} is a circle graph, then performing a local complementation at ${\displaystyle v}${\displaystyle v} corresponds to flipping one side of the circle divided by the chord representing ${\displaystyle v}${\displaystyle v} on the chord diagram^{[3] [7]} . The class of circle graphs are hence closed under local complementation, and they are also closed under taking vertex-minors.

For a graph ${\displaystyle G}${\displaystyle G} with vertex set ${\displaystyle V}${\displaystyle V}, the cut-rank function (also historically known as the connectivity function) is denoted ${\displaystyle \rho _{G}:2^{V}\to \mathbb {Z} _{\geq 0}}${\displaystyle \rho _{G}:2^{V}\to \mathbb {Z} _{\geq 0}}. It is defined over the vertex subsets ${\displaystyle X\subseteq V}${\displaystyle X\subseteq V} such that ${\displaystyle \rho _{G}(X)}${\displaystyle \rho _{G}(X)} is the rank of the bi-adjacency matrix of the partition ${\displaystyle (X,V-X)}${\displaystyle (X,V-X)}, defined over the finite field GF(2). That is, the rank of the ${\displaystyle X\times (V-X)}${\displaystyle X\times (V-X)} binary matrix ${\displaystyle M}${\displaystyle M} where ${\displaystyle M_{uv}=1}${\displaystyle M_{uv}=1} if and only if ${\displaystyle uv}${\displaystyle uv} is an edge in ${\displaystyle G}${\displaystyle G}.

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^[8] .

TODO

The global interlace polynomial ${\displaystyle Q(G,x)}${\displaystyle Q(G,x)}, also known as the Tutte-Martin polynomial, is a polynomial that corresponds to a simple graph ${\displaystyle G}${\displaystyle G}. It is defined recursively as ${\displaystyle Q(G,x)={\begin{cases}Q(G-u,x)+Q((G*u)-u,x)+Q((G*uvu)-u,x)&uv\in E(G)\\x^{n}&G{\text{ has no edges}}\end{cases}}}${\displaystyle Q(G,x)={\begin{cases}Q(G-u,x)+Q((G*u)-u,x)+Q((G*uvu)-u,x)&uv\in E(G)\\x^{n}&G{\text{ has no edges}}\end{cases}}}

Now if ${\displaystyle G}${\displaystyle G} and ${\displaystyle H}${\displaystyle H} are locally equivalent, ${\displaystyle Q(G,x)=Q(H,x)}${\displaystyle Q(G,x)=Q(H,x)} for any ${\displaystyle x}${\displaystyle x}. Additionally, ${\displaystyle Q(G,2)}${\displaystyle Q(G,2)} is related to the number of graphs locally equivalent to ${\displaystyle G}${\displaystyle G}.

Let ${\displaystyle A}${\displaystyle A} be the adjacency matrix of a graph ${\displaystyle G}${\displaystyle G} over the binary field. For a subset ${\displaystyle S}${\displaystyle S} of ${\displaystyle V(G)}${\displaystyle V(G)}, we write ${\displaystyle A[S]}${\displaystyle A[S]} to denote the ${\displaystyle S\times S}${\displaystyle S\times S} submatrix of ${\displaystyle A}${\displaystyle A}. Let ${\displaystyle I_{X}}${\displaystyle I_{X}} be the ${\displaystyle V(G)\times V(G)}${\displaystyle V(G)\times V(G)} diagonal matrix over the binary field such that the ${\displaystyle (v,v)}${\displaystyle (v,v)}-entry is 1 if and only if ${\displaystyle v\in X}${\displaystyle v\in X}. The global interlace polynomial can equivalently be defined as

${\displaystyle Q(G,x)=\sum _{R\subseteq S\subseteq V(G)}(x-2)^{\mathrm {nullity} ((A+I_{R})[S])}}${\displaystyle Q(G,x)=\sum _{R\subseteq S\subseteq V(G)}(x-2)^{\mathrm {nullity} ((A+I_{R})[S])}}

This polynomial has a nice formula in certain cases, such as when G is locally equivalent to a cycle or a tree.

It is interesting to note a couple of similarities to the canonical Tutte polynomial. In particular, the recurrence looks similar to the deletion-contraction formula, and both polynomials can be formulated as a sum of terms raised to the power of a matrix rank.

Define ${\displaystyle Odd_{G}(D)=\{v\in V(G)\mid |N(v)\cap D|=1{\bmod {2}}\}}${\displaystyle Odd_{G}(D)=\{v\in V(G)\mid |N(v)\cap D|=1{\bmod {2}}\}}. We say that a set of vertices ${\displaystyle L}${\displaystyle L} is local if ${\displaystyle L=X\cup Odd_{G}(X)}${\displaystyle L=X\cup Odd_{G}(X)} for some subset ${\displaystyle X\subseteq L}${\displaystyle X\subseteq L}. Now if ${\displaystyle L}${\displaystyle L} is local in ${\displaystyle G}${\displaystyle G}, it is local in any graph locally equivalent to ${\displaystyle G}${\displaystyle G}. Any local set does not have full cut-rank.

TODO

A graph ${\displaystyle H}${\displaystyle H} is a vertex-minor of a graph ${\displaystyle G}${\displaystyle G} if ${\displaystyle H}${\displaystyle H} is an induced subgraph of a graph locally equivalent to ${\displaystyle G}${\displaystyle G}. The name ‘vertex-minor’ was coined by Oum but it appeared previously under various names such as l-reduction and i-minor^[9] .

Deciding whether H is a vertex-minor of G for two input graphs G and H with is NP-complete, even if H is a complete graph and G is a circle graph ^[10] . However, for each fixed circle graph ${\displaystyle H}${\displaystyle H}, there is an ${\displaystyle {\mathcal {O}}(n^{3})}${\displaystyle {\mathcal {O}}(n^{3})}-time algorithm to decide whether an input ${\displaystyle n}${\displaystyle n}-vertex graph ${\displaystyle G}${\displaystyle G} contains a vertex-minor isomorphic to ${\displaystyle H}${\displaystyle H}^[11] . Every prime graph with at least 6 vertices has a prime vertex-minor with one less vertex ^[9] .

Distance-hereditary graphs are exactly the graphs with no vertex-minor isomorphic to ${\displaystyle C_{5}}${\displaystyle C_{5}}^[12] , and exactly the graphs which are the vertex-minor of a tree^[13] .

For two adjacent vertices x and y, the pivot operation is defined as

${\displaystyle G\wedge xy=G\star x\star y\star x}${\displaystyle G\wedge xy=G\star x\star y\star x}

It can be shown that ${\displaystyle G\star x\star y\star x=G\star y\star x\star y}${\displaystyle G\star x\star y\star x=G\star y\star x\star y}, and hence the pivot operation is well defined. The graph ${\displaystyle G\wedge xy}${\displaystyle G\wedge xy} can be obtained from ${\displaystyle G}${\displaystyle G} by toggling adjacencies between every pair of vertices in two different sets among ${\displaystyle N_{G}(x)-(N_{G}(y)\cup {y})}${\displaystyle N_{G}(x)-(N_{G}(y)\cup {y})}, ${\displaystyle N_{G}(x)\cap N_{G}(y)}${\displaystyle N_{G}(x)\cap N_{G}(y)}, and ${\displaystyle N_{G}(y)-(N_{G}(x)\cup {x})}${\displaystyle N_{G}(y)-(N_{G}(x)\cup {x})} and then switching labels of ${\displaystyle x}${\displaystyle x} and ${\displaystyle y}${\displaystyle y}.

Two graphs are said to be pivot equivalent if one can be obtained from the other through a sequence of pivot operations. Pivot equivalent graphs are locally equivalent, but the converse is not true.

A graph H is a pivot-minor of a graph G if H is an induced subgraph of a graph pivot-equivalent to G. Note that bipartite graphs with the pivot-minor relation are essentially equivalent to binary matroids with the matroid minor relation.

• Draft articles on STEM
• AfC submissions on other topics
• Pending AfC submissions
• AfC pending submissions by age/10 days ago
• AfC submissions by date/04 November 2025