On graphs with simply structured eigenspaces

Abstract

Resumo: Um grafo G possui um autoespa¸co simplesmente estruturado se o autoespa¸co associado a umautovalor da matriz laplaciana admite uma base cujas entradas pertencem ao conjunto {-1,0,1}. Dizemos que G 'e simplesmente estruturado se todos os seus autoespa¸cos forem simplesmente estruturados. Neste trabalho, determinamos o n' umero m' inimo de vetores em uma base de um autoespa¸ co da matriz laplaciana de um grafo threshold conexo, de modo que essa base seja simplesmente estruturada. Al' em disso, caracterizamos todos os grafos threshold conexos com n v'ertices que s˜ao simplesmente estruturados e cuja base de autovetores da matriz laplaciana admite uma ordena¸ c˜ao tal que vetores n˜ao consecutivos sejam ortogonais, os quais chamamos de grafos threshold fracamente Hadamard diagonaliz' avel (WHD). Isso oferece uma resposta parcial ao problema proposto em [2] sobre a determina¸ c˜ao de quais cografos s˜ ao WHD. Tamb'em identificamos uma subfam' ilia infinita de grafos em cadeia na qual todos os autovalores inteiros da matriz laplaciana possuem autoespa¸ cos simplesmente estruturados, e mostramos que n˜ ao faz sentido estender as defini¸c˜oes de grafos WHD para a matriz laplaciana sem sinal

Abstract: A graphG has a simply structured eigenspace if the eigenspace associated with an eigenvalue of the Laplacian matrix admits a basis with all entries in the set {-1,0,1}. We say that G is simply structured if all its eigenspaces are simply structured. In this work, we determine the minimum number of vectors in a basis of an eigenspace of the Laplacian matrix of a connected threshold graph, such that this basis is simply structured. Additionally, we characterize all connected threshold graphs with n vertices that are simply structured and whose Laplacian eigenvector bases admit an ordering in which non-consecutive vectors are orthogonal, which we call threshold weakly Hadamard diagonalizable (WHD) graph. This provides a partial answer to the problem posed in [2] with regard to determining which cographs are WHD. We also identify an infinite subfamily of chain graphs in which all integer eigenvalues of the Laplacian matrix have simply structured eigenspaces, and we show that extending the definition of WHD graphs to the signless Laplacian matrix is not appropriate