Draft:Local complementation

Local Complementation (graph theory)

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 ${\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 $G$ is locally equivalent to a tree $T$, then $G$ has a subgraph isomorphic to $T$.

Relation to quantum computing

If $|G\rangle$ 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).

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\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 $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} _{\geq 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

TODO

the 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{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 $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 {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.

Local Sets

Define $Odd_{G}(D)=\{v\in V(G)\mid |N(v)\cap D|=1{\bmod {2}}\}$. We say that a set of vertices $L$ is local if $L=X\cup Odd_{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$. Any local set does not have full cut-rank.

Canonical (tree) Decomposition

TODO

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 ${\mathcal {O}}(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.

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.