The Group Structure of Pivot and Loop Complementation on Graphs and Set Systems
arXiv:0909.4004 · doi:10.1016/j.ejc.2011.03.002
Abstract
We study the interplay between principal pivot transform (pivot) and loop complementation for graphs. This is done by generalizing loop complementation (in addition to pivot) to set systems. We show that the operations together, when restricted to single vertices, form the permutation group S_3. This leads, e.g., to a normal form for sequences of pivots and loop complementation on graphs. The results have consequences for the operations of local complementation and edge complementation on simple graphs: an alternative proof of a classic result involving local and edge complementation is obtained, and the effect of sequences of local complementations on simple graphs is characterized.
21 pages, 7 figures, significant additions w.r.t. v3 are Thm 7 and Remark 25
References in corpus (2)
Cited by in corpus (21)
- Interlace Polynomials for Multimatroids and Delta-Matroids
- On the interplay between embedded graphs and delta-matroids
- Matroids, Delta-matroids and Embedded Graphs
- Nullity and Loop Complementation for Delta-Matroids
- Binary matroids and local complementation
- Pivots, Determinants, and Perfect Matchings of Graphs
- Quaternary Bicycle Matroids and the Penrose Polynomial for Delta-Matroids
- Partial-twuality polynomials of delta-matroids
- Hopf algebras and Tutte polynomials
- Inductive tools for connected ribbon graphs, delta-matroids and multimatroids
- Measurement-based quantum computation--a quantum-mechanical toy model for spacetime?
- The adjacency matroid of a graph
- Quaternary matroids are vf-safe
- Isotropic matroids II: Circle graphs
- The Sortability of Graphs and Matrices under Context Directed Swaps
- Orienting Transversals and Transition Polynomials of Multimatroids
- The Nullity Theorem for Principal Pivot Transform
- On the linear algebra of local complementation
- The excluded 3-minors for vf-safe delta-matroids
- Eulerian and bipartite binary delta-matroids
- Sorting by Reversals and the Theory of 4-Regular Graphs