On graphs and codes preserved by edge local complementation

DOI10.1007/S10623-013-9876-6zbMATH Open1342.94112arXiv1006.5802OpenAlexW2137967397MaRDI QIDQ2260792FDOQ2260792

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)

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.

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

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

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)

Cites Work

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

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)