Eigenvalue bounds for the distance-$t$ chromatic number of a graph and their application to Lee codes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916219586609152 |
|---|---|
| author | Abiad, Aida Neri, Alessandro Reijnders, Luuk |
| author_facet | Abiad, Aida Neri, Alessandro Reijnders, Luuk |
| contents | We derive eigenvalue bounds for the $t$-distance chromatic number of a graph, which is a generalization of the classical chromatic number. We apply such bounds to hypercube graphs, providing alternative spectral proofs for results by Ngo, Du and Graham [Inf. Process. Lett., 2002], and improving their bound for several instances. We also apply the eigenvalue bounds to Lee graphs, extending results by Kim and Kim [Discrete Appl. Math., 2011]. Finally, we provide a complete characterization for the existence of perfect Lee codes of minimum distance $3$. In order to prove our results, we use a mix of spectral and number theory tools. Our results, which provide the first application of spectral methods to Lee codes, illustrate that such methods succeed to capture the nature of the Lee metric. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_14839 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Eigenvalue bounds for the distance-$t$ chromatic number of a graph and their application to Lee codes Abiad, Aida Neri, Alessandro Reijnders, Luuk Combinatorics Information Theory We derive eigenvalue bounds for the $t$-distance chromatic number of a graph, which is a generalization of the classical chromatic number. We apply such bounds to hypercube graphs, providing alternative spectral proofs for results by Ngo, Du and Graham [Inf. Process. Lett., 2002], and improving their bound for several instances. We also apply the eigenvalue bounds to Lee graphs, extending results by Kim and Kim [Discrete Appl. Math., 2011]. Finally, we provide a complete characterization for the existence of perfect Lee codes of minimum distance $3$. In order to prove our results, we use a mix of spectral and number theory tools. Our results, which provide the first application of spectral methods to Lee codes, illustrate that such methods succeed to capture the nature of the Lee metric. |
| title | Eigenvalue bounds for the distance-$t$ chromatic number of a graph and their application to Lee codes |
| topic | Combinatorics Information Theory |
| url | https://arxiv.org/abs/2404.14839 |