The maximum number of minimal codewords in long codes

DOI10.1016/J.DAM.2012.09.009MaRDI QIDQ1932464zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Patrick Solé, Carsten Thomassen, Adel Alahmadi, R. E. L. Aldred, R. de la Cruz

Publication date 18 January 2013

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

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

zbMATH Keywords

cycle code of graphsintersecting codesminimal codewords

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial aspects of matroids and geometric lattices (05B35) Paths and cycles (05C38) Linear codes (general theory) (94B05)

Abstract: Upper bounds on the maximum number of minimal codewords in a binary code follow from the theory of matroids. Random coding provide lower bounds. In this paper we compare these bounds with analogous bounds for the cycle code of graphs. This problem (in the graphic case) was considered in 1981 by Entringer and Slater who asked if a connected graph with $p$ vertices and $q$ edges can have only slightly more that $2^{q-p}$ cycles. The bounds in this note answer this in the affirmative for all graphs except possibly some that have fewer than $2p+3lo{g}_2(3p)$ edges. We also conclude that an Eulerian (even) graph has at most $2^{q-p}$ cycles unless the graph is a subdivision of a 4-regular graph that is the edge-disjoint union of two Hamiltonian cycles, in which case it may have as many as $2^{q-p}+p$ cycles.

Recommendations

• The maximum number of minimal codewords in an \([n,k]\)-code
• The minimum number of minimal codewords in an \([n, k]\)-code and in graphic codes
• Maximality of the cycle code of a graph
• An application of coding theory to a problem in graphical enumeration
• On the maximum number of minimal codewords

Cited in

(10)

• An application of coding theory to a problem in graphical enumeration
• scientific article; zbMATH DE number 4074967 (Why is no real title available?)
• On the minimum number of minimal codewords
• Number of minimal-weight words in block codes
• Counting Hamiltonian cycles in planar triangulations
• Cycles in 5-connected triangulations
• On the maximum number of minimal codewords
• The minimum number of minimal codewords in an \([n, k]\)-code and in graphic codes
• On the number of minimal codewords in codes generated by the adjacency matrix of a graph
• The maximum number of minimal codewords in an \([n,k]\)-code

This page was built for publication: The maximum number of minimal codewords in long codes

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