×

zbMATH — the first resource for mathematics

The minimum number of minimal codewords in an \([n, k]\)-code and in graphic codes. (English) Zbl 1311.05027
Summary: We survey some lower bounds on the function in the title based on matroid theory and address the following problem by G. Dosa et al. [PU.M.A., Pure Math. Appl. 15, No. 4, 383–392 (2004; Zbl 1112.05021)]: 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 \geq 38\), every 3-connected graph with \(p\) vertices has at least as many cycles as the wheel with \(p\) vertices.

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
94B25 Combinatorial codes
Software:
Magma; nauty; Traces
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agrell, E., On the Voronoi neighbor ratio for binary linear codes, IEEE Trans. Inform. Theory, 3064-3072, (1998) · Zbl 0936.94020
[2] Alahmadi, A.; Aldred, R. E.L.; de la Cruz, R.; Solé, P.; Thomassen, C., The maximum number of minimal codewords in long codes, Discrete Appl. Math., 161, 424-429, (2013) · Zbl 1254.05084
[3] Aldred, R. E.L.; Thomassen, C., On the number of cycles in 3-connected cubic graphs, J. Combin. Theory Ser. B, 71, 79-84, (1997) · Zbl 0918.05068
[4] Ashikhmin, A.; Barg, A., Minimal vectors in linear codes, IEEE Trans. Inform. Theory, 2010-2017, (1998) · Zbl 0932.94032
[5] Barnette, D.; Grünbaum, B., On steinitz’s theorem concerning convex 3-polytopes and on some properties of planar graphs, (The Many Facets of Graph Theory, Lecture Notes in Math, vol. 110, (1969), Springer-Verlag Berlin), 27-40 · Zbl 0194.25003
[6] Bosma, W.; Cannon, J.; Playoust, C., The magma algebra system. I. the user language, J. Symbolic Comput., 24, 235-265, (1997) · Zbl 0898.68039
[7] Dosa, Gy.; Szalkai, I.; Laflamme, C., The maximum and minimum number of circuits and bases of matroids, Pure Math. Appl. (PU.M.A.), 15, 383-392, (2004) · Zbl 1112.05021
[8] Greene, C., A rank inequality for finite geometric lattices, J. Comb. Theory, 9, 357-364, (1970) · Zbl 0254.05016
[9] Jianji, S., The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B, 75, 74-87, (1999) · Zbl 0931.05044
[10] N. Kashyap, On the convex geometry of binary linear codes, preprint. http://www.ece.iisc.ernet.in/ nkashyap/Papers/code_geometry.pdf.
[11] Kostochka, A. V., A lower number for the hadwiger number of graphs by their average degree, Combinatorica, 4, 307-316, (1984) · Zbl 0555.05030
[12] Lovász, L., Combinatorial problems and exercises, (1979), North Holland · Zbl 0439.05001
[13] McKay, B. D.; Piperno, A., Practical graph isomorphism, II, J. Symbolic Comput., 60, 94-112, (2013) · Zbl 1394.05079
[14] S. Ok, (Ph.D. thesis), Technical University of Denmark, 2015, preprint.
[15] Stiebitz, M., Decomposing graphs under degree constraints, J. Graph Theory, 23, 321-324, (1996) · Zbl 0865.05058
[16] Thomason, A., An extremal number for contractions of graphs, Math. Proc. Cambridge Philos. Soc., 95, 261-265, (1984) · Zbl 0551.05047
[17] Thomason, A., The extremal function for complete minors, J. Combin. Theory Ser. B, 81, 318-338, (2001) · Zbl 1024.05083
[18] Thomassen, C., Kuratowski’s theorem, J. Graph Theory, 5, 225-241, (1981) · Zbl 0481.05023
[19] Thomassen, C., Graph decomposition with constraints on the connectivity and minimum degree, J. Graph Theory, 7, 165-167, (1983) · Zbl 0515.05045
[20] Titov, V. K., A constructive description of some classes of graphs, (1975), Moscow
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.