This paper investigates the properties of permutation Ham- ming graphs, a class of graphs in which the vertices are the permutations of n symbols and the edges connect pairs of vertices at a Hamming dis- tance greater than or equal to a value d. Despite a remarkable regularity, permutation Hamming graphs elude general formulas for relevant indica- tors like the clique number. The clique number plays a crucial role in the Maximum Permutation Code Problem (MPCP), a well-known optimiza- tion problem. This work focuses on the relationship between permutation Hamming graphs and a particular type of Tura ́n graphs. The main re- sult is a theorem asserting that permutation Hamming graphs are the intersection of a set of Tur ́an graphs. This equivalence has implications on the MPCP. In fact it enables a reformulation as a hitting set problem, which in turn can be translated into a binary integer program.

Permutation Codes, Hamming Graphs and Turan Graphs / Barta, Janos; Montemanni, Roberto. - 574:(2019), pp. 111-118. (Intervento presentato al convegno 3rd International Conference on: Applied Physics, System Science and Computers tenutosi a Dubrovnik, Croatia nel September 2018) [10.1007/978-3-030-21507-1_17].

### Permutation Codes, Hamming Graphs and Turan Graphs

#### Abstract

This paper investigates the properties of permutation Ham- ming graphs, a class of graphs in which the vertices are the permutations of n symbols and the edges connect pairs of vertices at a Hamming dis- tance greater than or equal to a value d. Despite a remarkable regularity, permutation Hamming graphs elude general formulas for relevant indica- tors like the clique number. The clique number plays a crucial role in the Maximum Permutation Code Problem (MPCP), a well-known optimiza- tion problem. This work focuses on the relationship between permutation Hamming graphs and a particular type of Tura ́n graphs. The main re- sult is a theorem asserting that permutation Hamming graphs are the intersection of a set of Tur ́an graphs. This equivalence has implications on the MPCP. In fact it enables a reformulation as a hitting set problem, which in turn can be translated into a binary integer program.
##### Scheda breve Scheda completa Scheda completa (DC)
2019
3rd International Conference on: Applied Physics, System Science and Computers
Dubrovnik, Croatia
September 2018
574
111
118
Barta, Janos; Montemanni, Roberto
Permutation Codes, Hamming Graphs and Turan Graphs / Barta, Janos; Montemanni, Roberto. - 574:(2019), pp. 111-118. (Intervento presentato al convegno 3rd International Conference on: Applied Physics, System Science and Computers tenutosi a Dubrovnik, Croatia nel September 2018) [10.1007/978-3-030-21507-1_17].
File in questo prodotto:
Non ci sono file associati a questo prodotto.
##### Pubblicazioni consigliate

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/1177001`
• ND
• 1
• ND