The maximum number of minimal codewords in long codes. (English) Zbl 1254.05084

Alahmadi, A.; Aldred, R. E. L.; dela Cruz, R.; Solé, P.; Thomassen, C.

Discrete Appl. Math. 161, No. 3, 424-429 (2013).

Summary: Upper bounds on the maximum number of minimal codewords in a binary code follow from the theory of matroids. Random coding provides 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 R. C. Entringer and P. J. Slater [Ars. Comb. 11, 289–294 (1981; Zbl 0469.05043)] who asked if a connected graph with \(p\) vertices and \(q\) edges can have only slightly more than \(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+3\log_{2}(3p)\) edges. We also conclude that an Eulerian (even and connected) 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.

MSC:

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

Keywords:

minimal codewords; intersecting codes; cycle code of graphs