Local complementation

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

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

Equivalently, the local complementation at $v$ replaces the subgraph of $G$ induced by $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.

Local equivalence

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 $n$, the star graph and complete graph on $n$ vertices forms a trivial local equivalence class. The local equivalence classes on graphs up to 12 vertices is known....

Using ideas from isotropic subsystems, Bouchet introduced a $𝒪(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 $\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 $G$ is locally equivalent to a tree $T$, then $G$ has a subgraph isomorphic to $T$

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

Relation to quantum computing

If $|G⟩$ represents a graph state in quantum computing, the action of the local Clifford operation on the graph state is roughly equivalent. 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)

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

Properties

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

1. Local complementations do not, in general, commute; that is, $(G\star v)\star w\ne (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 $G$ independently. Without loss of generality, we assume that $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 $4$-regular graph.
4. Dahlberg, Helsen, and Wehner 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.

Relation to circle graphs

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

Invariants

Cut-rank function

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

Totally isotropic subsystems

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.

Global interlace polynomial

The global interlace polynomial $Q(G,x)$, also known as the Tutte-Martin polynomial, is a polynomial that corresponds to a simple graph $G$. It is defined recursively as $Q(G,x)=\{\begin{array}{cc}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{array}$

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

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

$Q(G,x)=\sum _{R\subseteq S\subseteq V(G)}(x-2{)}^{\mathrm{n}\mathrm{u}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{y}((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.

Local sets

Define $Od{d}_G(D)=\{v\in V(G)\mid |N(v)\cap D|=1mod2\}$. We say that a set of vertices $L$ is local if $L=X\cup Od{d}_G(X)$ for some subset $X\subseteq L$. Now if $L$ is local in $G$, it is local in any graph locally equivalent to $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.

Canonical split decomposition

A split of a graph $G$ is a partition $(X,Y)$ of the vertex set of $G$ such that $|X|,|Y|\ge 2$ and ${\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 $G_1$ and $G_2$ with marker vertices $v_1\in V(G_1)$ and $v_2\in V(G_2)$ is defined to be the graph obtained from the disjoint union of $G_1-v_1$ and $G_2-v_2$ by adding an edge between every neighbour of $v_1$ in $G_1$ and every neighbour of $v_2$ in $G_2$.

The canonical split decomposition is constructed as follows: Start from a set $\{G\}$ consisting of a single graph. Repeatedly pick a graph $H$ that admits a split. We then replace $H$ with $2$ smaller graphs whose 1-join reconstructs $H$. This process is applied only when $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.

Vertex-minor relation

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

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.. However, for each fixed circle graph $H$, there is an $𝒪(n^3)$-time algorithm to decide whether an input $n$-vertex graph $G$ contains a vertex-minor isomorphic to $H$. Every prime graph with at least 6 vertices has a prime vertex-minor with one less vertex

Distance-hereditary graphs are exactly the graphs with no vertex-minor isomorphic to $C_5$, and exactly the graphs which are the vertex-minor of a tree

Pivot operation

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

$G\wedge xy=G\star x\star y\star x$

It can be shown that $G\star x\star y\star x=G\star y\star x\star y$, and hence the pivot operation is well defined. The graph $G\wedge xy$ can be obtained from $G$ by toggling adjacencies between every pair of vertices in two different sets among $N_G(x)-(N_G(y)\cup y)$, $N_G(x)\cap N_G(y)$, and $N_G(y)-(N_G(x)\cup x)$ and then switching labels of $x$ and $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 $G$ and $H$ are locally equivalent, they are pivot equivalent to some $G^{\prime }$ and $H^{\prime }$ respectively such that $G^{\prime }*v_1{v}_2\dots v_k=H^{\prime }$ and $\{v_1,v_2,\dots ,v_k\}$ is an independent set in $G^{\prime }$.

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

Pivot-minor relation

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.