Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/99215
Title: The maximum number of minimal codewords in long codes
Authors: Alahmadi, A.
Aldred, R. E. L.
de la Cruz, R.
Solé, P.
Thomassen, C.
Issue Date: 2013
Source: Alahmadi, A., Aldred, R., dela Cruz, R., Solé, P., & Thomassen, C. (2013). The maximum number of minimal codewords in long codes. Discrete Applied Mathematics, 161(3), 424-429.
Series/Report no.: Discrete applied mathematics
Abstract: 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 Entringer and Slater who asked if a connected graph with p vertices and q edges can have only slightly more than 2q−p cycles. The bounds in this note answer this in the affirmative for all graphs except possibly some that have fewer than 2p+3log2(3p) edges. We also conclude that an Eulerian (even and connected) graph has at most 2q−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 2q−p+p cycles.
URI: https://hdl.handle.net/10356/99215
http://hdl.handle.net/10220/17374
ISSN: 0166-218X
DOI: http://dx.doi.org/10.1016/j.dam.2012.09.009
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Journal Articles

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.