A permutation code can be represented as a graph, in which the nodes correspond to the permutation codewords and the weights on the edges are the Hamming distances between the codewords. Graphs belonging to this class are called permutation Hamming graphs. This paper explores the Maximum Permutation Code Problem (MPCP), a well-known optimization problem in coding theory, by means of a graph theoretical approach. Permutation Hamming graphs turn out to satisfy strong regularity properties, such as vertex transitivity and r-partiteness. In addition, exact formulas for the degree of the vertices and for the number of the edges are presented. Furthermore, a remarkable similarity between permutation Hamming graphs and Turán graphs is enlightened. The new link with Turán graphs might help to improve current results on the MPCP.

Hamming Graphs and Permutation Codes / Barta, Janos; Montemanni, Roberto. - 2018-:(2017), pp. 154-158. (Intervento presentato al convegno 4th International Conference on Mathematics and Computers in Sciences and in Industry, MCSI 2017 tenutosi a Corfu Greece nel 2017) [10.1109/MCSI.2017.35].

Hamming Graphs and Permutation Codes

Montemanni Roberto
2017

Abstract

A permutation code can be represented as a graph, in which the nodes correspond to the permutation codewords and the weights on the edges are the Hamming distances between the codewords. Graphs belonging to this class are called permutation Hamming graphs. This paper explores the Maximum Permutation Code Problem (MPCP), a well-known optimization problem in coding theory, by means of a graph theoretical approach. Permutation Hamming graphs turn out to satisfy strong regularity properties, such as vertex transitivity and r-partiteness. In addition, exact formulas for the degree of the vertices and for the number of the edges are presented. Furthermore, a remarkable similarity between permutation Hamming graphs and Turán graphs is enlightened. The new link with Turán graphs might help to improve current results on the MPCP.
2017
2017
4th International Conference on Mathematics and Computers in Sciences and in Industry, MCSI 2017
Corfu Greece
2017
2018-
154
158
Barta, Janos; Montemanni, Roberto
Hamming Graphs and Permutation Codes / Barta, Janos; Montemanni, Roberto. - 2018-:(2017), pp. 154-158. (Intervento presentato al convegno 4th International Conference on Mathematics and Computers in Sciences and in Industry, MCSI 2017 tenutosi a Corfu Greece nel 2017) [10.1109/MCSI.2017.35].
File in questo prodotto:
File Dimensione Formato  
08326833.pdf

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 151.78 kB
Formato Adobe PDF
151.78 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1177022
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 0
social impact