{{Short description|Operation in graph theory}} 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 <math>G</math> at a vertex <math>v</math> is an operation that produces a new graph, denoted by <math>G \star v</math>. This operation is defined by replacing the subgraph of <math>G</math> induced by <math>N_G(v)</math> with its complementary subgraph. In other words, two distinct vertices <math>x</math> and <math>y</math> are adjacent in the graph <math>G \star v</math> when exactly one of the following holds:
# vertices <math>x</math> and <math>y</math> are adjacent in <math>G</math>; or # both vertices <math>x</math> and <math>y</math> are neighbours of <math>v</math> in <math>G</math>. 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 <math>n</math> 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.<ref name=":1">{{Cite journal |last1=Cabello |first1=Adan |title=Optimal preparation of graph states |date=2011-04-16 |last2=Danielsen |first2=Lars Eirik |last3=Lopez-Tarrida |first3=Antonio J. |last4=Portillo |first4=Jose R. |journal=Physical Review A |volume=83 |issue=4 |article-number=042314 |doi=10.1103/PhysRevA.83.042314 |arxiv=1011.5464 |bibcode=2011PhRvA..83d2314C }}</ref> The size of a local equivalence class is at most <math>3^n</math>, and this collection of graphs can be enumerated efficiently.
== Applications ==
=== Structural graph theory === The Robertson–Seymour theorem states that the graph minor relation is a well-quasi ordering. It was proved in a series of twenty papers spanning over 500 pages from 1983 to 2004. The algorithmic consequences are vast - together with an efficient algorithm for graph minor testing, the result provides efficient algorithms for solving a range of computational problems where the optimal value is monotonic in the graph minor relation.
Local complementations are central to the vertex-minor relation, which shares many similarities with the graph minor relation. Better understanding of the local complementation operation could extend the Robertson–Seymour theorem to prove that the vertex-minor relation is also a well-quasi ordering.
=== Measurement based quantum computing === For a given the graph state <math>|G\rang</math>, the action of the local Clifford operation is equivalent to the local complementation transformation on the graph <math>G</math>. The study of graph states that are locally equivalent is relevant to building quantum circuits in measurement based quantum computing (MBQC)<ref name=":1" />
The local unitary operation is related but may produce a different equivalent class.<ref>{{Cite journal |last1=Ji |first1=Z.-F. |last2=Chen |first2=J.-X. |last3=Wei |first3=Z.-H. |last4=Ying |first4=M.-S. |date=January 2010 |title=The LU-LC conjecture is false |url=http://www.rintonpress.com/journals/doi/QIC10.1-2-8.html |journal=Quantum Information and Computation |volume=10 |issue=1&2 |pages=97–108 |doi=10.26421/QIC10.1-2-8|url-access=subscription }}</ref> Results suggest that LU-equivalence and LC-equivalence coincide for graph with up to 26 vertices.<ref>{{Cite web |last=Cabello |first=Adan |last2=Danielsen |first2=Lars Eirik |last3=Lopez-Tarrida |first3=Antonio J. |last4=Portillo |first4=Jose R. |date=2010-11-24 |title=Optimal preparation of graph states |url=https://arxiv.org/abs/1011.5464v2 |access-date=2026-04-08 |website=arXiv.org |language=en}}</ref>
Similarly, local complementation is also related to state preparation in photonic quantum computing (PQC).
== Properties == # The local complement operation is self inverse; that is, <math>(G\star v)\star v=G</math>. # Local complementations commute only when vertices are non-adjacent; that is, <math>(G\star v)\star w = (G\star w)\star v</math> unless <math>vw \in E(G)</math>. # 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 <math>\max(n+1, 10n/9)</math> local complementations.<ref name=":3">{{Cite book |last=Koršunov |first=Aleksej D. |title=Discrete Analysis and Operations Research |date=1996 |publisher=Springer Netherlands |isbn=978-94-010-7217-5 |series=Mathematics and Its Applications |location=Dordrecht}}</ref> # Locally equivalent trees are isomorphic (Mulder's conjecture), and there exists a simple expression to count such trees.<ref name=":5">{{Cite journal |last=Bouchet |first=André |date=1988 |title=Transforming trees by successive local complementations |url=https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.3190120210 |journal=Journal of Graph Theory |language=en |volume=12 |issue=2 |pages=195–207 |doi=10.1002/jgt.3190120210 |issn=1097-0118|url-access=subscription }}</ref> # If a graph is locally equivalent to a tree, it has a subgraph isomorphic to that tree.<ref name=":6">{{Cite web |last=Fon-Der-Flaas |first=D. G. |date=1988 |title=On local complementations of graphs |url=https://zbmath.org/0728.05048 |access-date=2026-02-26 |website=zbmath.org}}</ref> # If a graph is locally equivalent to the cycle graph, it contains a Hamiltonian cycle.<ref name=":6" /> # If a graph is locally equivalent to its complement, it is self-complementary.<ref name=":6" /> # The number of essentially different ways of transforming one graph into another via local complementation is <math>0, 3, 6</math> or <math>2^k</math> for some <math>k \ge 0</math>.<ref name=":6" /> # 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.<ref>{{Cite journal |last1=Dahlberg |first1=Axel |title=Counting single-qubit Clifford equivalent graph states is #P-complete |date=2019-07-18 |arxiv=1907.08024 |last2=Helsen |first2=Jonas |last3=Wehner |first3=Stephanie |journal=Journal of Mathematical Physics |volume=61 |issue=2 |article-number=022202 |doi=10.1063/1.5120591 }}</ref> # 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 <math>\mathcal O^*(1.938^n)</math> algorithm.<ref>{{cite book |last1=Javelle |first1=Jérôme |title=Graph-Theoretic Concepts in Computer Science |date=2012-04-20 |last2=Mhalla |first2=Mehdi |last3=Perdrix |first3=Simon |chapter=On the Minimum Degree up to Local Complementation: Bounds and Complexity |series=Lecture Notes in Computer Science |volume=7551 |pages=138–147 |doi=10.1007/978-3-642-34611-8_16 |arxiv=1204.4564 |isbn=978-3-642-34610-1 }}</ref><ref>{{cite book |last1=Cattanéo |first1=David |title=Algorithms and Computation |date=2016-08-17 |arxiv=1503.04702 |last2=Perdrix |first2=Simon |chapter=Minimum Degree up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms |series=Lecture Notes in Computer Science |volume=9472 |pages=259–270 |doi=10.1007/978-3-662-48971-0_23 |isbn=978-3-662-48970-3 }}</ref> # Determining the minimum total edge weight by means of local complementation is NP-complete.<ref>{{Cite journal |last1=Sharma |first1=Hemant |title=Minimising the number of edges in LC-equivalent graph states |date=2026-01-27 |arxiv=2506.00292 |last2=Goodenough |first2=Kenneth |last3=Borregaard |first3=Johannes |last4=Rozpędek |first4=Filip |last5=Helsen |first5=Jonas |journal=Quantum |volume=10 |article-number=2001 |doi=10.22331/q-2026-02-09-2001 }}</ref> # 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.
== Pivot operation == Local complementations do not commute for adjacent vertices, motivating the following operation that performs complementations at adjacent vertices.
For adjacent vertices <math>x</math> and <math>y</math>, the '''pivot operation''' (also historically known as an edge complementation) is defined as<math display="block">G\wedge xy = G\star x\star y\star x.</math>It can be shown that <math>G\star x\star y\star x = G\star y\star x\star y</math>, and hence the pivot operation is well defined. Alternatively, the graph <math>G\wedge xy</math> can be obtained from <math>G</math> by toggling adjacencies between every pair of vertices in two different sets among <math>N_G(x) - (N_G(y) \cup {y})</math>, <math>N_G(x) \cap N_G(y)</math> and <math>N_G(y) - (N_G(x) \cup {x})</math> then switching the labels <math>x</math> and <math>y</math>. The pivot operation satisfies the identities <math>G \wedge xy \wedge xy = G</math> and <math>G \wedge xy \wedge yz = G \wedge xz</math>.<ref>{{Cite journal |last=Oum |first=Sang-il |date=2005-09-01 |title=Rank-width and vertex-minors |url=https://www.sciencedirect.com/science/article/pii/S0095895605000389 |journal=Journal of Combinatorial Theory, Series B |volume=95 |issue=1 |pages=79–100 |doi=10.1016/j.jctb.2005.03.003 |issn=0095-8956|url-access=subscription }}</ref>
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,<ref name=":3" /> but is not generally true. If <math>G</math> and <math>H</math> are pivot equivalent graphs, there are pairwise disjoint edges <math>e_1, e_2, \dots, e_k</math> such that <math>G \wedge e_1 \wedge e_2 \dots\wedge e_k = H</math>. Fon-Der-Flass proved that if graphs <math>G</math> and <math>H</math> are locally equivalent, they are pivot equivalent to some <math>G'</math> and <math>H'</math> respectively such that <math>G' * v_1 v_2 \dots v_k = H'</math> and <math>\{v_1, v_2, \dots, v_k\}</math> is an independent set in <math>G'</math> and <math>H'</math>.<ref>{{Cite journal |last=D. G. |first=Fon-Der-Flaass |date=1989 |title=Distance between locally equivalent graphs |journal=Metody Diskret. Analiz |volume=48 |pages=85–94 |via=Novosibirsk: Institute of Mathematics of the USSR Academy of Sciences}}</ref>
The size of a pivot equivalence class is at most <math>2^n</math>, and this collection of graphs can be enumerated efficiently.
Pivot equivalence has been studied using even binary delta-matroids.<ref>{{Cite journal |last1=Bouchet |first1=A. |last2=Duchamp |first2=A. |date=1991-02-15 |title=Representability of △-matroids over GF(2) |url=https://dx.doi.org/10.1016/0024-3795%2891%2990020-W |journal=Linear Algebra and Its Applications |volume=146 |pages=67–78 |doi=10.1016/0024-3795(91)90020-W |issn=0024-3795|url-access=subscription }}</ref>
== Invariants ==
=== Cut-rank function === As a graph undergoes local complementation, its adjacency matrix changes in a well defined way. In particular, the entries that change are exactly some sub-matrix (excluding the main diagonal). Hence, it may be natural to study the local complementation operation using linear algebra.
For a graph <math>G</math> with vertex set <math>V</math>, the cut-rank function (also historically known as the connectivity function) is denoted <math display="inline">\rho_G: \mathcal P(V) \to \mathbb N</math>. It is defined over the vertex subsets <math>X \subseteq V</math> such that <math>\rho_G(X)</math> is the rank of the bi-adjacency matrix of the partition <math>(X, V-X)</math>, defined over the finite field GF(2). That is, the rank of the <math>X\times(V-X)</math> binary matrix <math>M</math> where <math>M_{uv} = 1</math> when <math>uv</math> is an edge in <math>G</math>. Intuitively, <math>\rho_G(X)</math> is a measure of how complex the connectivity is between <math>X</math> 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,<ref>{{Cite journal |last=Seymour |first=P. D |date=1988-08-01 |title=On the connectivity function of a matroid |url=https://dx.doi.org/10.1016/0095-8956%2888%2990052-4 |journal=Journal of Combinatorial Theory, Series B |volume=45 |issue=1 |pages=25–30 |doi=10.1016/0095-8956(88)90052-4 |issn=0095-8956|url-access=subscription }}</ref> and so locally equivalent bipartite graphs are also pivot-equivalent.
The cut-rank function is submodular since it can be shown that <math>\rho_G(X)+\rho_G(Y) \ge \rho_G(X\cup Y)+\rho_G(X\cap Y)</math> for any vertex set <math>X</math> and <math>Y</math>. However, it is not monotone.
=== Local sets === The cut-rank can be considered 'most interesting' when it is either rank 1 or full rank. Since the cut-rank is invariant over local complementation, so are the sets with a particular cut-rank. The sets of rank 1 are studied using canonical split decompositions in a later section. Here, we define a local set as a vertex set which does not have full cut-rank.
Define <math display="block">\mathrm{Odd}_G(X) = \{v \in V(G) \mid |N(v)\cap X| = 1 \bmod 2 \}.</math>A set of vertices <math>S</math> is '''local''' in <math>G</math> if <math>S = X \cup \mathrm{Odd}_G(X)</math> for some subset <math>X \subseteq V(G)</math>. Now if <math>S</math> is local in <math>G</math>, it is also local in any graph locally equivalent to <math>G</math>. Local sets can equivalently be defined as the sets of vertices which do not have full cut-rank (i.e. the sets <math>S</math> where <math>\rho_G(S) < |S|</math>). Intuitively, a local set is some linear combination of the closed neighbourhoods of <math>G</math>. Local sets are used to study the degrees of vertices in <math>G</math>.<ref>{{Cite journal |last=Høyer |first=Peter |last2=Mhalla |first2=Mehdi |last3=Perdrix |first3=Simon |date=2006 |editor-last=Asano |editor-first=Tetsuo |title=Resources Required for Preparing Graph States |url=https://link.springer.com/chapter/10.1007/11940128_64?error=cookies_not_supported&code=bcd69664-6723-4241-80fa-838f1fd751cd |journal=Algorithms and Computation |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=638–649 |doi=10.1007/11940128_64 |isbn=978-3-540-49696-0}}</ref>
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.<ref name=":4">{{Cite journal |last=Bouchet |first=André |date=1993-04-28 |title=Recognizing locally equivalent graphs |url=https://dx.doi.org/10.1016/0012-365X%2893%2990357-Y |journal=Discrete Mathematics |volume=114 |issue=1 |pages=75–86 |doi=10.1016/0012-365X(93)90357-Y |issn=0012-365X|url-access=subscription }}</ref>
=== Totally isotropic subspaces === The richest description of a class of locally equivalent graphs is an extension of the local sets idea, involving a linear algebra structure over the Klein four-group. Each locally equivalent graph, equipped with two specific vectors, corresponds to some graphic presentations of the same totally isotropic subspace.
Let <math>K_4</math> be the Klein four-group. A vector <math>\mathbf a \in K_4^n</math> is said to be '''complete''' if <math>\mathbf a_i</math> is nonzero for every <math>1 \le i \le n</math>. Two vectors <math>\mathbf a, \mathbf b \in K_4^n</math> are said to be '''supplementary''' if <math>\mathbf a_i</math> and <math>\mathbf b_i</math> are nonzero and distinct for every <math>1 \le i \le n</math>. For a set <math>S</math>, define <math>\mathbf a[S]</math> as the vector where <math>\mathbf a[S]_i = a_i</math> if <math>i \in S</math>, and <math>\mathbf a[S]_i = 0</math> otherwise.
A subspace <math>L</math> of <math>K_4^n</math> is called a '''totally isotropic subspace''' if <math>\dim(L) = \dim(K_4^n)/2 = n</math>, and every two complete vectors in <math>L</math> are not supplementary.
A '''graphic presentation''' of a totally isotropic subspace <math>L</math> is a triple <math>(G, \mathbf a, \mathbf b)</math> where <math>G</math> is a simple graph on the vertex set <math>V=\{1, \dots, n\}</math> and <math>\mathbf a</math> and <math>\mathbf b</math> are supplementary vectors of <math>K_4^n</math>, such that <math>L</math> is spanned by the set <math display="block">\{\mathbf a[N(v)]+ \mathbf b[\{v\}] \mid v \in V\}.</math>For a fixed <math>L</math>, there is a one-to-one correspondence between every graphic presentation <math>(G, \mathbf a, \mathbf b)</math> and every complete vector <math>\mathbf a</math> where <math>\mathbf a \not\in L</math>, the vectors <math>\mathbf a</math> here are known are '''Eulerian vectors'''. Furthermore, if <math>(G, \mathbf a, \mathbf b)</math> is a graphic presentation of <math>L</math>, so is <math display="block">(G\star v, \mathbf a+\mathbf b[\{v\}], \mathbf b+\mathbf a[N(v)])</math> and <math display="block">(G\wedge vw, \mathbf a[V\setminus\{v,w\}]+\mathbf b[\{v,w\}], \mathbf a[\{v,w\}]+\mathbf b[V\setminus\{v,w\}]).</math>The '''fundamental graphs''' of <math>L</math> 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 <math>L = \{\mathbf a[\mathrm{Odd}_G(X)]+\mathbf b[X] \mid X \subseteq V\}</math>, and when <math>\mathbf a=\mathbf b</math>, <math>L = \{\mathbf a[S] \mid S \text{ is local in } G\}</math>.<ref>{{Cite journal |last=Bouchet |first=André |date=1988-08-01 |title=Graphic presentations of isotropic systems |url=https://www.sciencedirect.com/science/article/pii/009589568890055X |journal=Journal of Combinatorial Theory, Series B |volume=45 |issue=1 |pages=58–76 |doi=10.1016/0095-8956(88)90055-X |issn=0095-8956|url-access=subscription }}</ref>
=== Totally isotropic subspaces (modern interpretation) === Brijder and Traldi introduce the isotropic matroid <math>M[IAS(G)]</math> which is equivalent to the isotropic system introduced by Bouchet above. Let <math>A(G)</math> denote the adjacency matrix of <math>G</math> and let <math>I</math> denote the <math>V(G)\times V(G)</math> identity matrix. The binary matroid represented by the matrix <math display="block">IAS(G)=\begin{pmatrix}I&A(G)&A(G)+I\end{pmatrix}</math>is denoted <math>M[IAS(G)]</math>, and called the isotropic matroid of <math>G</math>. Now graphs <math>G_1</math> and <math>G_2</math> are locally equivalent (up to isomorphism) if and only if the binary matroids <math>M[IAS(G_1)]</math> and <math>M[IAS(G_2)]</math> are isomorphic. This classification of local equivalence classes allows a natural study of the minimum degree and independence number of locally equivalent graphs.<ref>{{Citation |last=Traldi |first=Lorenzo |title=Binary matroids and local complementation |date=2014-11-08 |url=http://arxiv.org/abs/1301.4946 |access-date=2026-04-03 |publisher=arXiv |doi=10.48550/arXiv.1301.4946 |id=arXiv:1301.4946}}</ref><ref>{{Citation |last=Brijder |first=Robert |title=Isotropic matroids I: Multimatroids and neighborhoods |date=2016-10-19 |url=http://arxiv.org/abs/1503.04406 |access-date=2026-04-03 |publisher=arXiv |doi=10.48550/arXiv.1503.04406 |id=arXiv:1503.04406 |last2=Traldi |first2=Lorenzo}}</ref><ref>{{Citation |last=Brijder |first=Robert |title=Isotropic matroids II: Circle graphs |date=2016-10-19 |url=http://arxiv.org/abs/1504.04299 |access-date=2026-04-03 |publisher=arXiv |doi=10.48550/arXiv.1504.04299 |id=arXiv:1504.04299 |last2=Traldi |first2=Lorenzo}}</ref><ref>{{Citation |last=Traldi |first=Lorenzo |title=Isotropic matroids III: Connectivity |date=2017-06-30 |url=http://arxiv.org/abs/1602.03899 |access-date=2026-04-03 |publisher=arXiv |doi=10.48550/arXiv.1602.03899 |id=arXiv:1602.03899 |last2=Brijder |first2=Robert}}</ref>
=== Characterisation of local equivalence === The following characterisations of locally equivalent graphs are straightforward results using totally isotropic subspaces. This leads to a efficient algorithm to recognise locally equivalent graphs.
Let <math>G_1</math> and <math>G_2</math> be simple graphs and fix supplementary vectors <math>\mathbf a_1</math> and <math>\mathbf b_1</math>. he graphs <math>G_1</math> and <math>G_2</math> are locally equivalent if and only if there are supplementary vectors <math>\mathbf a_2</math> and <math>\mathbf b_2</math> such that <math>(G_1, \mathbf a_1, \mathbf b_1)</math> and <math>(G_2, \mathbf a_2, \mathbf b_2)</math> are graphic presentations of the same totally isotropic subspace. The existence of such vectors <math>\mathbf a_2</math> and <math>\mathbf b_2</math> can be determined in <math>\mathcal O(n^3)</math> by solving a system of linear equations.<ref name=":0">{{Cite journal |last=Bouchet |first=André |date=1991-12-01 |title=An efficient algorithm to recognize locally equivalent graphs |url=https://doi.org/10.1007/BF01275668 |journal=Combinatorica |language=en |volume=11 |issue=4 |pages=315–329 |doi=10.1007/BF01275668 |issn=1439-6912|url-access=subscription }}</ref> A modification to this algorithm can, with the same time complexity, recover a sequence of at most <math>3n/2</math> local complementations transforming <math>G_1</math> into <math>G_2</math>.<ref>{{Citation |last=Fon-Der-Flaass |first=D. G. |title=Local Complementations of Simple and Directed Graphs |date=1996 |work=Discrete Analysis and Operations Research |pages=15–34 |editor-last=Korshunov |editor-first=Alekseǐ D. |url=https://doi.org/10.1007/978-94-009-1606-7_3 |access-date=2026-02-26 |place=Dordrecht |publisher=Springer Netherlands |language=en |doi=10.1007/978-94-009-1606-7_3 |isbn=978-94-009-1606-7|url-access=subscription }}</ref>
An equivalent characterisation can be formulated using vertex sets. Let <math>N_1</math> and <math>N_2</math> denote the neighbourhood functions of <math>G_1</math> and <math>G_2</math> respectively. Then graphs <math>G_1</math> and <math>G_2</math> are locally equivalent if and only if there are vertex subsets <math>X, Y, Z, T</math> such that for every pair of vertices <math>v, w</math>, <math display="block">|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,</math>and the symmetric difference of <math>X\cap T</math> with <math>Y\cap Z</math> is the entire vertex set.<ref name=":0" />
=== Global interlace polynomial === The '''global interlace polynomial''' (also known as the Tutte-Martin polynomial), is a polynomial that corresponds to a simple graph <math>G</math>. It is defined recursively as<math display="block">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}</math>Now if <math>G</math> and <math>H</math> are locally equivalent, <math>Q(G, x) = Q(H, x)</math> for any <math>x</math>.<ref name=":4" /> Additionally,
* <math>Q(G, 2)</math> is a multiple of the number of graphs locally equivalent to <math>G</math>. In particular, if <math>G</math> is a fundamental graph of a totally isotropic subspace <math>L</math>, this gives the number of Eulerian vectors in <math>L</math>. * <math>Q(G; 4)/2^n</math> is the number of induced Eulerian subgraphs in <math>G</math>. (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.<ref name=":7">{{Cite journal |last=Aigner |first=Martin |last2=van der Holst |first2=Hein |date=2004-01-15 |title=Interlace polynomials |url=https://www.sciencedirect.com/science/article/pii/S0024379503006761 |journal=Linear Algebra and its Applications |volume=377 |pages=11–30 |doi=10.1016/j.laa.2003.06.010 |issn=0024-3795}}</ref> * <math>\deg Q(G; x)</math> is the largest independent number of the graph locally equivalent to <math>G</math>.<ref name=":7" />
The polynomial has closed-form formulas in certain cases:
* The path graphs <math>P_n</math> have the closed form <math>Q(P_n; x) = \lambda_{1}\left(1+\sqrt{1+x}\right)^{n-1}+\lambda_{2}\left(1-\sqrt{1+x}\right)^{n-1}</math> where <math>\lambda_1=x/2+x/\sqrt{1+x}</math> and <math>\lambda_2=x/2-x/\sqrt{1+x}</math>. * More generally, a tree <math>T</math> has the global interlace polynomial <math display="inline">Q(T; x) = \sum_{k\ge0} \Phi_k(T) 2^{n-2k}x^k</math>, where <math>\Phi_k(T)</math> is the number of matchings of size <math>k</math> in <math>T</math>. * The cycle graphs <math>C_n</math> have the closed form <math>Q(C_n; 2) = (1+\sqrt3)^n+(1-\sqrt3)^n-4(2^{n-1}+(-1)^n)/3</math>.<ref name=":4" />
An equivalent definition of the global interlace polynomial involves a summation over subsets of vertex sets. Let the graph <math>G</math> have the adjacency matrix <math>A</math> over the binary field. For a vertex set <math>S \in V(G)</math>, write <math>A[S]</math> to denote the <math>S\times S</math> sub-matrix of <math>A</math>. Let <math>I_X</math> be the <math>V(G)\times V(G)</math> diagonal matrix over the binary field such that the <math>(v,v)</math>-entry is 1 when <math>v \in X</math>, and 0 otherwise. The global interlace polynomial can equivalently be defined as<math display="block">Q(G; x) = \sum_{R \subseteq S \subseteq V(G)} (x-2)^{\mathrm{nullity}((A+I_R)[S])}.</math>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.
=== Canonical split decomposition === {{Main|Split (graph theory)}}
A '''split''' of a graph <math>G</math> is a partition of its vertex set <math>(X, Y)</math> such that <math>|X|, |Y| \ge 2</math> and <math>\rho_G(X) = 1</math>. This happens exactly when the connectivity between <math>X</math> and <math>Y</math> is a complete bipartite graph, and complete bipartite graphs have a simple known structure over local complementation.
If a graph admits a split, it can be built by the '''1-join''' of two graphs. The 1-join of two graphs <math>G_1</math> and <math>G_2</math> with marker vertices <math>v_1 \in V(G_1)</math> and <math>v_2 \in V(G_2)</math> is defined to be the graph obtained from the disjoint union of <math>G_1-v_1</math> and <math>G_2-v_2</math> by adding an edge between every neighbour of <math>v_1</math> in <math>G_1</math> and every neighbour of <math>v_2</math> in <math>G_2</math>.
The '''canonical split decomposition''' can be constructed using the following procedure: Start from the set <math>\{G\}</math> consisting of a single graph. Repeatedly pick a graph <math>H</math> from this set that admits a split. Then replace <math>H</math> with <math>2</math> smaller graphs whose 1-join reconstructs <math>H</math>. This process is applied only when <math>H</math> is neither a complete graph nor a star. The set now contains all induced prime subgraphs of <math>G</math> 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.<ref name=":5" />
The canonical split decomposition is unique and has preserves important structural properties over local complementation.
The rank-width of <math>G</math> is the maximum rank-width of all prime induced subgraphs. == Vertex-minor relation == Local complementation gives rise to several derived operations that play a central role in graph minor theory. A graph <math>H</math> is a '''vertex-minor''' (also historically known as l-reduction or i-minor) of a graph <math>G</math> if <math>H</math> is an induced subgraph of a graph locally equivalent to <math>G</math>.<ref name=":2">{{Cite journal |last=Bouchet |first=André |date=1987-08-01 |title=Unimodularity and circle graphs |url=https://dx.doi.org/10.1016/0012-365X%2887%2990132-4 |journal=Discrete Mathematics |volume=66 |issue=1 |pages=203–208 |doi=10.1016/0012-365X(87)90132-4 |issn=0012-365X|url-access=subscription }}</ref>
Deciding whether <math>H</math> is a vertex-minor of <math>G</math> for two input graphs <math>G</math> and <math>H</math> is NP-complete, even if <math>H</math> is a complete graph and <math>G</math> is a circle graph.<ref>{{Cite arXiv|last1=Dahlberg |first1=Axel |title=The complexity of the vertex-minor problem |date=2019-06-12 |eprint=1906.05689 |last2=Helsen |first2=Jonas |last3=Wehner |first3=Stephanie |class=math.CO }}</ref> However, for each fixed circle graph <math>H</math>, there is an <math>\mathcal O(n^3)</math>-time algorithm to decide whether an input <math>n</math>-vertex graph <math>G</math> contains a vertex-minor isomorphic to <math>H</math>.<ref>{{Cite journal |last1=Courcelle |first1=Bruno |last2=Oum |first2=Sang-il |date=2007-01-01 |title=Vertex-minors, monadic second-order logic, and a conjecture by Seese |url=https://www.sciencedirect.com/science/article/pii/S0095895606000463 |journal=Journal of Combinatorial Theory, Series B |volume=97 |issue=1 |pages=91–126 |doi=10.1016/j.jctb.2006.04.003 |issn=0095-8956|url-access=subscription }}</ref> Every prime graph with at least 6 vertices has a prime vertex-minor with one less vertex.<ref name=":2" />
Distance-hereditary graphs are exactly the graphs with no vertex-minor isomorphic to <math>C_5</math>,<ref>{{cite journal |last1=Kwon |first1=O.-Joung |title=Unavoidable vertex-minors in large prime graphs |date=2014-03-24 |last2=Oum |first2=Sang-il |journal=European Journal of Combinatorics |volume=41 |pages=100–127 |doi=10.1016/j.ejc.2014.03.013 |arxiv=1306.3066 }}</ref> and exactly the graphs which are the vertex-minor of a tree.<ref>{{Cite journal |last=Bouchet |first=André |date=1987-09-01 |title=Reducing prime graphs and recognizing circle graphs |url=https://doi.org/10.1007/BF02579301 |journal=Combinatorica |language=en |volume=7 |issue=3 |pages=243–254 |doi=10.1007/BF02579301 |issn=1439-6912|url-access=subscription }}</ref>
== Pivot-minor relation == A graph <math>H</math> is a pivot-minor of a graph <math>G</math> if <math>H</math> is an induced subgraph of a graph pivot-equivalent to <math>G</math>. Bipartite graphs with the pivot-minor relation are essentially equivalent to binary matroids with the matroid minor relation.
== Relation to circle graphs == For a circle graph <math>G</math>, performing a local complementation at <math>v</math> corresponds to an graphical transformation of its chord diagram. In particular, the chord diagram of <math>G\star v</math> is obtains from the chord diagram of <math>G</math> by cutting the circumference by chord representing <math>v</math>, then reversing one arc.<ref name=":0" /><ref name=":4" /> The class of circle graphs are hence closed under local complementation, and they are also closed under taking vertex-minors.
== References == {{reflist}}
Category:Graph operations