Local complementation

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]

Using ideas from isotropic subsystems, Bouchet^[2] introduced a ${\displaystyle {\mathcal {O}}(n^{3})}${\displaystyle {\mathcal {O}}(n^{3})} algorithm to determine whether two graphs are locally equivalent. Additionally, Fon-Der-Flass shows that all locally equivalent graphs can be reached after a sequence of at most ${\displaystyle \max(n+1,10n/9)}${\displaystyle \max(n+1,10n/9)} local complementations (see page 55 of "Local complementations of simple and directed graphs").

Bouchet and Fon-Der-Flass independently proved Mulder's conjecture that locally equivalent trees are isomorphic. Furthermore, Bouchet gives a simple closed form expression for number of such trees (only leaves and their neighbours can be swapped), and Fon-Der-Flass proves a stronger statement that 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}^[3]

Fon-Der-Flass proved that graphs locally equivalent to the cycle graph contain a Hamiltonian cycle.

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

Similarly, local complementation is also related to state preparation in photonic quantum computing (PQC).

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^[5] 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^{[2] [6]} . 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^[7]

Bouchet develops a structure using the Klein four-group to represent a class of locally equivalent graphs. Each locally equivalent graph corresponds to some graphical representations of the same totally isotropic system. This leads to results about determining local equivalence and enumerating locally equivalent graphs.

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}. Local sets can equivalently be defined as the sets which do not have full cut-rank.

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.

A split of a graph ${\displaystyle G}${\displaystyle G} is a partition ${\displaystyle (X,Y)}${\displaystyle (X,Y)} of the vertex set of ${\displaystyle G}${\displaystyle G} such that ${\displaystyle |X|,|Y|\geq 2}${\displaystyle |X|,|Y|\geq 2} and ${\displaystyle \rho _{G}(X)=1}${\displaystyle \rho _{G}(X)=1}.

If a graph admits a split, it can be built by the 1-join of two graphs. The 1-join of two graphs ${\displaystyle G_{1}}${\displaystyle G_{1}} and ${\displaystyle G_{2}}${\displaystyle G_{2}} with marker vertices ${\displaystyle v_{1}\in V(G_{1})}${\displaystyle v_{1}\in V(G_{1})} and ${\displaystyle v_{2}\in V(G_{2})}${\displaystyle v_{2}\in V(G_{2})} is defined to be the graph obtained from the disjoint union of ${\displaystyle G_{1}-v_{1}}${\displaystyle G_{1}-v_{1}} and ${\displaystyle G_{2}-v_{2}}${\displaystyle G_{2}-v_{2}} by adding an edge between every neighbour of ${\displaystyle v_{1}}${\displaystyle v_{1}} in ${\displaystyle G_{1}}${\displaystyle G_{1}} and every neighbour of ${\displaystyle v_{2}}${\displaystyle v_{2}} in ${\displaystyle G_{2}}${\displaystyle G_{2}}.

The canonical split decomposition is constructed as follows: Start from a set ${\displaystyle \{G\}}${\displaystyle \{G\}} consisting of a single graph. Repeatedly pick a graph ${\displaystyle H}${\displaystyle H} that admits a split. We then replace ${\displaystyle H}${\displaystyle H} with ${\displaystyle 2}${\displaystyle 2} smaller graphs whose 1-join reconstructs ${\displaystyle H}${\displaystyle H}. This process is applied only when ${\displaystyle H}${\displaystyle H} is neither a complete graph nor a star. We can associate a tree by having one node for each graph in the resulting set and adding edges between corresponding marker vertices.

The canonical split decomposition is unique and has nice properties regarding local complementation.

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

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.^[9] . 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}^[10] . Every prime graph with at least 6 vertices has a prime vertex-minor with one less vertex ^[8]

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

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. However, Fon-Der-Flass proved that if graphs ${\displaystyle G}${\displaystyle G} and ${\displaystyle H}${\displaystyle H} are locally equivalent, they are pivot equivalent to some ${\displaystyle G'}${\displaystyle G'} and ${\displaystyle H'}${\displaystyle H'} respectively such that ${\displaystyle G'*v_{1}v_{2}\dots v_{k}=H'}${\displaystyle G'*v_{1}v_{2}\dots v_{k}=H'} and ${\displaystyle \{v_{1},v_{2},\dots ,v_{k}\}}${\displaystyle \{v_{1},v_{2},\dots ,v_{k}\}} is an independent set in ${\displaystyle G'}${\displaystyle G'}.

Pivot equivalence has been studied using even binary delta-matroids.

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.

• Graph operations

• Articles with short description
• Short description matches Wikidata