Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Short covering codes arising from matchings in weighted graphs


Authors: Anderson N. Martinhão and Emerson L. Monte Carmelo
Journal: Math. Comp. 82 (2013), 605-616
MSC (2010): Primary 11B75, 05C70, 94B75; Secondary 05B40, 11T71, 94B25
Published electronically: May 1, 2012
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The concept of embedded matching in a weighted graph is introduced, and the maximum cardinality of an embedded matching is computed. On the other hand, consider the following problem induced by a short covering. Given a prime power $ q$, the number $ c(q)$ denotes the minimum cardinality of a subset $ \mathcal {H}$ of $ \mathbb{F}_q^3$ which satisfies the following property: every element in this space differs in at most $ 1$ coordinate from a scalar multiple of a vector in $ \mathcal {H}$. As another goal, a connection between embedded matching and short covering code is established. Moreover, this link is applied to improve the upper bound on $ c(q)$ for every odd prime power $ q$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11B75, 05C70, 94B75, 05B40, 11T71, 94B25

Retrieve articles in all journals with MSC (2010): 11B75, 05C70, 94B75, 05B40, 11T71, 94B25


Additional Information

Anderson N. Martinhão
Affiliation: Departamento de Matemática, Universidade Estadual de Maringá, Brazil
Email: and{\textunderscore}nm@hotmail.com

Emerson L. Monte Carmelo
Affiliation: Departamento de Matemática, Universidade Estadual de Maringá, Brazil
Email: elmcarmelo@uem.br

DOI: http://dx.doi.org/10.1090/S0025-5718-2012-02613-5
PII: S 0025-5718(2012)02613-5
Keywords: Matching, weighted graph, square number, finite field, independent vectors, covering codes.
Received by editor(s): April 12, 2011
Received by editor(s) in revised form: August 24, 2011
Published electronically: May 1, 2012
Additional Notes: The first author was supported by Capes.
The second author is supported by Fundação Araucária and CNPq.
Dedicated: This work is dedicated to Professor Adilson Gonçalves
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.