On graphs and codes preserved by edge local complementation

DOI10.1007/S10623-013-9876-6MaRDI QIDQ2260792zbMATH OpenOpenAlexFDO

Authors Lars Eirik Danielsen, Matthew G. Parker, Constanza Riera, Joakim Grahl Knudsen

Publication date 12 March 2015

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.5802

zbMATH Keywords

graphsisomorphismbinary linear codespivotedge local complementation

Mathematics Subject Classification ID

Information theory (general) (94A15) Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75) Linear codes (general theory) (94B05)

Abstract: Orbits of graphs under local complementation (LC) and edge local complementation (ELC) have been studied in several different contexts. For instance, there are connections between orbits of graphs and error-correcting codes. We define a new graph class, ELC-preserved graphs, comprising all graphs that have an ELC orbit of size one. Through an exhaustive search, we find all ELC-preserved graphs of order up to 12 and all ELC-preserved bipartite graphs of order up to 16. We provide general recursive constructions for infinite families of ELC-preserved graphs, and show that all known ELC-preserved graphs arise from these constructions or can be obtained from Hamming codes. We also prove that certain pairs of ELC-preserved graphs are LC equivalent. We define ELC-preserved codes as binary linear codes corresponding to bipartite ELC-preserved graphs, and study the parameters of such codes.

Recommendations

• Edge local complementation and equivalence of binary linear codes
• scientific article; zbMATH DE number 4202305
• Locally recoverable codes from planar graphs
• Locally testable codes and Cayley graphs
• Codes based on complete graphs
• Codes on graphs: Recent progress
• scientific article; zbMATH DE number 4070305
• On graphs and codes
• scientific article; zbMATH DE number 808801
• Codes on Graphs: Fundamentals

Cites work

• scientific article; zbMATH DE number 4202305 (Why is no real title available?)
• scientific article; zbMATH DE number 1243360 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1972849 (Why is no real title available?)
• scientific article; zbMATH DE number 5175633 (Why is no real title available?)
• scientific article; zbMATH DE number 3257167 (Why is no real title available?)
• Adaptive Soft-Decision Iterative Decoding Using Edge Local Complementation
• An enumeration of binary self-dual codes of length 32
• Circle graph obstructions
• Circle graph obstructions under pivoting
• Distance Hereditary Graphs and the Interlace Polynomial
• Edge local complementation and equivalence of binary linear codes
• Euler circuits and DNA sequencing by hybridization
• Generalized Bent Criteria for Boolean Functions (I)
• Graphic presentations of isotropic systems
• Interlace polynomials
• Interlace polynomials: enumeration, unimodality and connections to codes
• Local complementation and interlacement graphs
• Multiparty entanglement in graph states
• On graphs and codes
• On the classification of all self-dual additive codes over \(\text{GF}(4)\) of length up to 12
• Quantum error correction via codes over GF(4)
• The interlace polynomial of a graph

Cited in

(1)

• Edge local complementation and equivalence of binary linear codes

This page was built for publication: On graphs and codes preserved by edge local complementation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2260792)