Edge Local Complementation and Equivalence of Binary Linear Codes

Abstract

Orbits of graphs under the operation edge local complementation (ELC) are defined. We show that the ELC orbit of a bipartite graph corresponds to the equivalence class of a binary linear code. The information sets and the minimum distance of a code can be derived from the corresponding ELC orbit. By extending earlier results on local complementation (LC) orbits, we classify the ELC orbits of all graphs on up to 12 vertices. We also give a new method for classifying binary linear codes, with running time comparable to the best known algorithm.

Presented at International Workshop on Coding and Cryptography (WCC 2007), 16-20 Apr. 2007, Versailles, France. (12 pages, 3 figures)

References in corpus (6)

• Multi-party entanglement in graph states
• Graphical description of the action of local Clifford transformations on graph states
• On the Classification of All Self-Dual Additive Codes over GF(4) of Length up to 12
• On Self-Dual Quantum Codes, Graphs, and Boolean Functions
• Edge-local equivalence of graphs
• On Pivot Orbits of Boolean Functions

Cited by in corpus (10)

• Pivoting makes the ZX-calculus complete for real stabilizers
• Quantum stabilizer codes, lattices, and CFTs
• Hard limits on the postselectability of optical graph states
• Error-correcting one-way quantum computation with global entangling gates
• Weight of quadratic forms and graph states
• Iterative Decoding on Multiple Tanner Graphs Using Random Edge Local Complementation
• Pivots, Determinants, and Perfect Matchings of Graphs
• Edge local complementation for logical cluster states
• Interlace Polynomials: Enumeration, Unimodality, and Connections to Codes
• The Foliage Partition: An Easy-to-Compute LC-Invariant for Graph States