The minimum number of minimal codewords in an [n, k]-code and in graphic codes

摘要

We survey some lower bounds on the function in the title based on matroid theory and address the following problem by Dosa et al. (2004): Determine the smallest number of circuits in a loopless matroid with no parallel elements and with a given size and rank. In the graphic 3-connected case we provide a lower bound which is a product of a linear function of the number of vertices and an exponential function of the average degree. We also prove that, for p >= 38, every 3-connected graph with p vertices has at least as many cycles as the wheel with p vertices. (C) 2014 Elsevier B.V. All rights reserved.