Propriedades combinatórias e espetrais do grafo das rainhas

Abstract

Nesta dissertação estudam-se as propriedades combinatórias e espetrais do Grafo das Rainhas de ordem n2, Q(n). No caso das propriedades combinatórias, faz-se uma revisão da literatura relativamente aos resultados obtidos sobre vários invariantes combinatórios de Q(n). Detalharam-se algumas provas dos valores obtidos para os números de clique, de independência, de dominância e cromático. Relativamente aos resultados espetrais, apresentam-se vários resultados originais nomeadamente referentes ao menor valor próprio - 4 e ao valor próprio n - 4 que estão presentes no espetro de todos os grafos Q(n) para n ≥ 4. Esta dissertação termina com a anotação de alguns problemas em aberto e a formulação de algumas conjeturas.

In this essay, we study the combinatorial and spectral properties of the Queens Graph of order n2, Q(n). In the combinatorial properties chapter, we review the literature about some combinatorial invariants of Q(n). Some proofs of these known values are presented in this text, for example for clique number, stability number, chromatic number and domination number. In the spectral properties chapter, we present several original results with respect to the smaller eigenvalue - 4 and the eigenvalue n - 4 which are in the spectrum of all Q(n) for n ≥ 4. Finally, we present some open problem about the spectrum of Q(n) and formulate some conjectures.