Um Algoritmo para Gerar Grafos Threshold Simplesmente Estruturados
DOI:
https://doi.org/10.5540/03.2026.012.01.0343Keywords:
Grafo Threshold, Matriz Laplaciana, Autovetores, Autobase Simplesmente EstruturadaAbstract
Seja G um grafo threshold conexo com n vértices. Neste trabalho, caracterizamos todos os grafos G que tem uma autobase simplesmente estruturada para a matriz laplaciana, isto é, uma base de Rn composta de autovetores com entradas somente em {−1, 0, 1}. Nosso método consiste em provar que os autoespaços de um grafo threshold devem possuir um número mínimo de vetores, além de desenvolver um algoritmo para gerar todos os grafos threshold que satisfazem essa propriedade.
Downloads
References
M. Adm, K. Almuhtaseb, S. Fallat, K. Meagher, S. Nasserasr, M. N. Shirazi e A. S. Razafimahatratra. “Weakly Hadamard diagonalizable graphs”. Em: Linear Algebra and its Applications 610 (2021), pp. 86–119. doi: 10.1016/j.laa.2020.09.038.
C. O. Aguilar, M. Ficarra, N. Schurman e B. Sullivan. “The role of the anti-regular graph in the spectral analysis of threshold graphs”. Em: Linear Algebra and its Applications 588 (2020), pp. 210–223. doi: 10.1016/j.laa.2019.12.005.
N. Johnston e S. Plosker. “Laplacian {−1, 0, 1}- and {−1, 1}-diagonalizable graphs”. Em: Linear Algebra and its Applications 704 (2025), pp. 309–339. doi: 10.1016/j.laa.2024. 10.016.
R. R. Macharete, R. R. Del-Vecchio, H. Teixeira e L. de Lima. “A Laplacian eigenbasis for threshold graphs”. Em: Special Matrices 12.1 (2024), p. 20240029. doi: 10.1515/spma 2024-0029.
“Threshold Graphs and Related Topics”. Em: Threshold Graphs and Related Topics. Ed. por N.V.R. Mahadev e U.N. Peled. Vol. 56. Annals of Discrete Mathematics. Elsevier, 1995, p. iii. doi: 10.1016/S0167-5060(13)71063-X.
D. McLaren, H. Monterde e S. Plosker. “Weakly Hadamard diagonalizable graphs and Quantum State Transfer”. Em: (jul. de 2023). arXiv: 2307.01859 [math.CO].
T. Sander e J. Sander. “On simply structured kernel bases of unicyclic graphs”. Em: AKCE International Journal of Graphs and Combinatorics 4 (jan. de 2007), pp. 61–82.
