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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
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
08326833.pdf

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 151.78 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11380/1177022`