Clique-Number of Timbral Graphs
Resumo
We study the clique-number of the timbral graphs Tn,k,ℓ. The vertex set of Tn,k,ℓ is the set of all words of length k built on an alphabet of n symbols and two vertices are adjacent when they agree in exactly ℓ coordinates. We provide lower and upper bounds for the general case and determine ω(Tn,k,1) when k−1 ≤ n is a prime power, showing the correspondence between a clique with n2 vertices in Tn,n+1,1 and an affine plane of order n.
Referências
Akhmedov, A. and Winter, M. (2014). Chordal and timbral morphologies using hamiltonian cycles. Journal of Mathematics and Music: Mathematical and Computational Approaches to Music Theory, Analysis, Composition and Performance, 8:1–24.
Harney, I. (2017). Colorings of Hamming-Distance Graphs. PhD thesis, University of Kentucky.
Imrich, W. and Klavzar, S. (1996). On the complexity of recognizing hamming graphs and related classes of graphs. European Journal of Combinatorics, 17:209–221.
Lint, J. H. V. (1995). Codes. In Graham, R., Groetschel, M., and Lovász, L., editors, Handbook of Combinatorics, pages 773–807. Elsevier.
Rouayheb, S. E. and Georghiades, C. (2011). Graph theoretic methods in coding theory. In Cohen, L., Poor, H. V., and Scully, M. O., editors, Classical, Semi-Classical and Quantum Noise, pages 53–62. Springer.
Sharifiyazdi, E. (2007). The Clique Number of Generalized Hamming Graphs. PhD thesis, Clausthal University of Technology.
Shult, E. (2010). Points and lines: characterizing the classical geometries. Springer.
Sloane, N. J. A. (1989). Unsolved problems in graph theory arising from the study of codes. Graph Theory Notes of New York, 18:11–20.
Harney, I. (2017). Colorings of Hamming-Distance Graphs. PhD thesis, University of Kentucky.
Imrich, W. and Klavzar, S. (1996). On the complexity of recognizing hamming graphs and related classes of graphs. European Journal of Combinatorics, 17:209–221.
Lint, J. H. V. (1995). Codes. In Graham, R., Groetschel, M., and Lovász, L., editors, Handbook of Combinatorics, pages 773–807. Elsevier.
Rouayheb, S. E. and Georghiades, C. (2011). Graph theoretic methods in coding theory. In Cohen, L., Poor, H. V., and Scully, M. O., editors, Classical, Semi-Classical and Quantum Noise, pages 53–62. Springer.
Sharifiyazdi, E. (2007). The Clique Number of Generalized Hamming Graphs. PhD thesis, Clausthal University of Technology.
Shult, E. (2010). Points and lines: characterizing the classical geometries. Springer.
Sloane, N. J. A. (1989). Unsolved problems in graph theory arising from the study of codes. Graph Theory Notes of New York, 18:11–20.
Publicado
21/07/2024
Como Citar
CERIOLI, Márcia R.; CARDOSO, Luan Simões; VIANA, Petrucio.
Clique-Number of Timbral Graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 9. , 2024, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 58-62.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2024.2497.
