Local complementation

Uses your system voice; voice and rate in settings.

Snapshot

≈ 15 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 at a vertex v is an operation that produces a new graph, denoted by G \star v . This operation is defined by replacing the subgraph of G induced by N_G(v) with its complementary subgraph. In other words, two distinct vertices x and y are adjacent in the graph G \star v when exactly one of the following holds: # vertices x and y are adjacent in G ; or # both vertices x and y are neighbours of v in 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 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.…

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 at a vertex v is an operation that produces a new graph, denoted by G \star v . This operation is defined by replacing the subgraph of G induced by N_G(v) with its complementary subgraph. In other words, two distinct vertices x and y are adjacent in the graph G \star v when exactly one of the following holds: vertices x and y are adjacent in G ; or both vertices x and y are neighbours of v in 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 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 , and this collection of graphs can be enumerated efficiently. The local complement operation is self inverse; that is, (G\star v)\star v=G . Local complementations commute only when vertices are non-adjacent; that is, (G\star v)\star w = (G\star w)\star v unless vw \in E(G) . Connected components are preserved by the local complementation operation, so it is common analyse each component of the graph independently. So without loss of generality, all graphs will be assumed to be connected. All locally equivalent graphs can be reached after a sequence of at most \max(n+1, 10n/9) local complementations. Locally equivalent trees are isomorphic (Mulder's conjecture), and there exists a simple expression to count such trees. If a graph is locally equivalent to a tree, it has a subgraph isomorphic to that tree. If a graph is locally equivalent to the cycle graph, it contains a Hamiltonian cycle. If a graph is locally equivalent to its complement, it is self-complementary. The number of essentially different ways of transforming one graph into another via local complementation is 0, 3, 6 or 2^k for some k \ge 0 . 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. Locally equivalent graphs have the same rank-width. Counting the number of locally equivalent graphs is #P-complete. Determining the minimum degree that can be reached by means of local complementation is NP-complete and APX-hard, and can be computed by an \mathcal O^*(1.938^n) algorithm. Determining the minimum total edge weight by means of local complementation is NP-complete. Determining the minimum number of edges by means of pivots is NP-complete. Determining the minimum number of edges by means of local complementation is likely NP-complete. For adjacent vertices x and y , the pivot operation (also historically known as an edge complementation) 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. Alternatively, 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}) then switching the labels x and y . The pivot operation satisfies the identities G \wedge xy \wedge xy = G and G \wedge xy \wedge yz = G \wedge xz . Two graphs are said to be pivot equivalent if one can be obtained from the other through a sequence of pivot operations. Since pivot operations consist of local complementation operations, pivot equivalent graphs are locally equivalent. The converse is true for bipartite graphs, but is not generally true. If G and H are pivot equivalent graphs, there are pairwise disjoint edges e_1, e_2, \dots, e_k such that G \wedge e_1 \wedge e_2 \dots\wedge e_k = H . Fon-Der-Flass proved that if graphs G and H are locally equivalent, they are pivot equivalent to some G' and H' respectively such that G' * v_1 v_2 \dots v_k = H' and \{v_1, v_2, \dots, v_k\} is an independent set in G' and H' . The size of a pivot equivalence class is at most 2^n , and this collection of graphs can be enumerated efficiently. Pivot equivalence has been studied using even binary delta-matroids. For a graph G with vertex set V , the cut-rank function (also historically known as the connectivity function) is denoted \rho_G: \mathcal P(V) \to \mathbb N . 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 when uv is an edge in G . Intuitively, \rho_G(X) is a measure of how complex the connectivity is between vertex set X and the remaining vertices. 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, and so locally equivalent bipartite graphs are also pivot-equivalent. The cut-rank function is submodular since it can be shown that \rho_G(X)+\rho_G(Y) \ge \rho_G(X\cup Y)+\rho_G(X\cap Y) for any vertex set X and Y . However, it is not monotone. Define \mathrm{Odd}_G(X) = \{v \in V(G) \mid |N(v)\cap X| = 1 \bmod 2 \}. A set of vertices S is local in G if S = X \cup \mathrm{Odd}_G(X) for some subset X \subseteq V(G) . Now if S is local in G , it is also local in any graph locally equivalent to G . Local sets can equivalently be defined as the sets of vertices which do not have full cut-rank (i.e. the sets S where \rho_G(S) ). Intuitively, a local set is some linear combination of the closed neighbourhoods of G . Local sets are used to study the degrees of vertices in G . 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, since there are graphs with identical cut-rank functions which are not locally equivalent. Let K_4 be the Klein four-group. A vector \mathbf a \in K_4^n is said to be complete if \mathbf a_i is nonzero for every 1 \le i \le n . Two vectors \mathbf a, \mathbf b \in K_4^n are said to be supplementary if \mathbf a_i and \mathbf b_i are nonzero and distinct for every 1 \le i \le n . For a set S , define \mathbf a[S] as the vector where \mathbf a[S]_i = a_i if i \in S , and \mathbf a[S]_i = 0 otherwise. A subspace L of K_4^n is called a totally isotropic subspace if \dim(L) = \dim(K_4^n)/2 = n , and every two complete vectors in L are not supplementary. A graphic presentation of a totally isotropic subspace L is a triple (G, \mathbf a, \mathbf b) where G is a simple graph on the vertex set V=\{1, \dots, n\} and \mathbf a and \mathbf b are supplementary vectors of K_4^n , such that L is spanned by the set \{\mathbf a[N(v)]+ \mathbf b[\{v\}] \mid v \in V\}. For a fixed L , there is a one-to-one correspondence between every graphic presentation (G, \mathbf a, \mathbf b) and every complete vector \mathbf a where \mathbf a \not\in L , the vectors \mathbf a here are known are Eulerian vectors. Furthermore, if (G, \mathbf a, \mathbf b) is a graphic presentation of L , so is (G\star v, \mathbf a+\mathbf b[\{v\}], \mathbf b+\mathbf a[N(v)]) and (G\wedge vw, \mathbf a[V\setminus\{v,w\}]+\mathbf b[\{v,w\}], \mathbf a[\{v,w\}]+\mathbf b[V\setminus\{v,w\}]). The fundamental graphs of L form a local equivalence class. These facts leads to important results about determining local equivalence and locally equivalent class sizes, which is discussed in the next 2 sections. This structure can be considered as an extension of the local sets structure, since L = \{\mathbf a[\mathrm{Odd}_G(X)]+\mathbf b[X] \mid X \subseteq V\} , and when \mathbf a=\mathbf b , L = \{\mathbf a[S] \mid S \text{ is local in } G\} . Brijder and Traldi introduce the isotropic matroid M[IAS(G)] which is equivalent to the isotropic system introduced by Bouchet above. Let A(G) denote the adjacency matrix of G and let I denote the V(G)\times V(G) identity matrix. The binary matroid represented by the matrix IAS(G)=\begin{pmatrix}I&A(G)&A(G)+I\end{pmatrix} is denoted M[IAS(G)] , and called the isotropic matroid of G . Now graphs G_1 and G_2 are locally equivalent (up to isomorphism) if and only if the binary matroids M[IAS(G_1)] and M[IAS(G_2)] are isomorphic. This classification of local equivalence classes allows a natural study of the minimum degree and independence number of locally equivalent graphs. An equivalent characterisation can be formulated using vertex sets. Let N_1 and N_2 denote the neighbourhood functions of G_1 and G_2 respectively. Then graphs G_1 and G_2 are locally equivalent if and only if there are vertex subsets X, Y, Z, T such that for every pair of vertices v, w , |X\cap N_1(v)\cap N_2(w)|+|Y\cap N_1(v)\cap \{w\}|+|Z\cap N_2(w)\cap\{v\}|+|T\cap\{v,w\}| \equiv 0 \pmod 2, and the symmetric difference of X\cap T with Y\cap Z is the entire vertex set. The global interlace polynomial (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 \wedge uv)-u; x) & uv \in E(G) \\ x^n & G \text{ has no edges and } n \text{ vertices} \end{cases} Now if G and H are locally equivalent, Q(G, x) = Q(H, x) for any x . Additionally, Q(G, 2) is a multiple of the number of graphs locally equivalent to G . In particular, if G is a fundamental graph of a totally isotropic subspace L , this gives the number of Eulerian vectors in L . Q(G; 4)/2^n is the number of induced Eulerian subgraphs in G . (A graph is called Eulerian all degrees are even, even if it is disconnected). A surprising corollary is that locally equivalent graphs have the same number of induced Eulerian subgraphs. \deg Q(G; x) is the largest independent number of the graph locally equivalent to G . The polynomial has closed-form formulas in certain cases: The path graphs P_n have the closed form Q(P_n; x) = \lambda_{1}\left(1+\sqrt{1+x}\right)^{n-1}+\lambda_{2}\left(1-\sqrt{1+x}\right)^{n-1} where \lambda_1=x/2+x/\sqrt{1+x} and \lambda_2=x/2-x/\sqrt{1+x} . More generally, a tree T has the global interlace polynomial Q(T; x) = \sum_{k\ge0} \Phi_k(T) 2^{n-2k}x^k , where \Phi_k(T) is the number of matchings of size k in T . The cycle graphs C_n have the closed form Q(C_n; 2) = (1+\sqrt3)^n+(1-\sqrt3)^n-4(2^{n-1}+(-1)^n)/3 . An equivalent definition of the global interlace polynomial involves a summation over subsets of vertex sets. Let the graph G have the adjacency matrix A over the binary field. For a vertex set S \in V(G) , write A[S] to denote the S\times S sub-matrix 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 when v \in X , and 0 otherwise. 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])}. There are some interesting 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. Isomorphic graphs have the same Tutte polynomial, while locally equivalent or isomorphic graphs have the same global interlace polynomial. A split of a graph G is a partition of its vertex set (X, Y) such that |X|, |Y| \ge 2 and \rho_G(X) = 1 . This happens exactly when the connectivity between X and Y is a complete bipartite graph, and complete bipartite graphs have a simple known structure over local complementation. Since cut-rank is preserved by local complementation, the same is true for splits and any structure built on splits. 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 can be constructed using the following procedure: Start from the set \{G\} consisting of a single graph. Repeatedly pick a graph H from this set that admits a split. 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. The set now contains all induced prime subgraphs of G along with some star graphs and cliques. Lastly, 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 preserves important structural properties over local complementation. The rank-width of G is the maximum rank-width of all prime induced subgraphs.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375546731 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001375546731 · captured 1789730654.0 · version history

Cite this page as: encyclopegia.org, “Local complementation”, snapshot enwiki-001375546731. https://encyclopegia.org/a/local-complementation

Sources cited in this revision

15 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.