Interlace polynomials: enumeration, unimodality and connections to codes

DOI10.1016/J.DAM.2009.11.011zbMATH Open1225.05156arXiv0804.2576OpenAlexW2018745606WikidataQ60692133 ScholiaQ60692133MaRDI QIDQ968188FDOQ968188

Authors: Lars Eirik Danielsen, Matthew G. Parker 

Publication date: 5 May 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: The interlace polynomial q was introduced by Arratia, Bollobas, and Sorkin. It encodes many properties of the orbit of a graph under edge local complementation (ELC). The interlace polynomial Q, introduced by Aigner and van der Holst, similarly contains information about the orbit of a graph under local complementation (LC). We have previously classified LC and ELC orbits, and now give an enumeration of the corresponding interlace polynomials of all graphs of order up to 12. An enumeration of all circle graphs of order up to 12 is also given. We show that there exist graphs of all orders greater than 9 with interlace polynomials q whose coefficient sequences are non-unimodal, thereby disproving a conjecture by Arratia et al. We have verified that for graphs of order up to 12, all polynomials Q have unimodal coefficients. It has been shown that LC and ELC orbits of graphs correspond to equivalence classes of certain error-correcting codes and quantum states. We show that the properties of these codes and quantum states are related to properties of the associated interlace polynomials.

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

Recommendations

• Interlace polynomials
• The interlace polynomial and the Tutte–Martin polynomial
• The interlace polynomial of a graph
• Coding and Cryptography
• Interlace polynomials of ladder graphs

zbMATH Keywords

unimodalityquantum codeslocal complementationcircle graphsinterlace polynomialsquantum graph states

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Cites Work

• Title not available (Why is that?)
• Quantum error correction via codes over GF(4)
• Circle graph obstructions
• Recognition of Circle Graphs
• Multiparty entanglement in graph states
• Graphic presentations of isotropic systems
• Local complementation and interlacement graphs
• The interlace polynomial of graphs at \(-1\)
• Interlace polynomials
• Euler circuits and DNA sequencing by hybridization
• The interlace polynomial of a graph
• Graph-based classification of self-dual additive codes over finite fields
• Generalized Bent Criteria for Boolean Functions (I)
• On additive GF(4) codes
• On the classification of all self-dual additive codes over \(\text{GF}(4)\) of length up to 12
• Coding and Cryptography
• The coefficients of the Tutte polynomial are not unimodal
• Edge local complementation and equivalence of binary linear codes
• Some new results for additive self-dual codes over \(\mathrm{GF}(4)\)
• Spectral Orbits and Peak-to-Average Power Ratio of Boolean Functions with Respect to the {I,H,N} n Transform
• Aperiodic propagation criteria for Boolean functions
• Title not available (Why is that?)
• Univariate and Multivariate Merit Factors

Cited In (4)

• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• Signed permutohedra, delta‐matroids, and beyond
• Coding and Cryptography
• On graphs and codes preserved by edge local complementation

Uses Software

• OEIS

This page was built for publication: Interlace polynomials: enumeration, unimodality and connections to codes

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