Riassunto analitico
La mia tesi è incentrata sullo studio dei grafi di Cayley. Un grafo di Cayley è un grafo il cui insieme dei vertici è un gruppo G e due vertici u e v sono adiacenti se e solo se uv^(-1) è un elemento di un dato sottoinsieme S di G. Dopo aver descritto le proprietà generali dei grafi di Cayley, come il suo gruppo di automorfismi e la struttura del grafo quando G è un gruppo libero o quando G è un gruppo finito, ho studiato tre temi principali legati al concetto di grafo di Cayley .
Il primo è una classe speciale di questi grafi: grafi di Cayley che ammettono una rotazione completa; ovvero grafi di Cayley aventi un particolare automorfismo ω tale che, per un certo ordinamento di S={s_i :0≤ i≤d-1},ω(xs_i)=ω(x)s_(i+1) per ogni x ∊G e ogni i∊Zd. In particolare, ho studiato i grafi di Cayley definiti da trasposizioni, tra cui un teorema che caratterizza completamente i grafi di questo tipo aventi una rotazione completa. Il teorema afferma che i grafi di Cayley generati dalle trasposizioni sono essenzialmente di due tipi : modified bubble-sort graphs e prodotti cartesiani di isomorphic modified bubble-sort graphs, e generalized star graphs GST(t+q,q) con t e q relativamente primi e prodotti cartesiani di isomorphic generalized star graphs GST(t+q,q) con t e q relativamente primi.
Il secondo argomento concerne il problema di trovare una clique massimale in un dato grafo, dove una clique è un sottoinsieme dell'insieme di vertici tale che il sottografo indotto è completo. Nel mio caso il grafo è un grafo di Paley con q2 vertici, dove q è potenza di un numero primo dispari e ho analizzato alcuni risultati che costruiscono una clique massimale nel grafo. Inoltre ho studiato alcune stime per la dimensione massima della clique nel grafo, la cardinalità della più grande coclique nel grafo, e il numero cromatico (il numero minimo di colori necessari per ottenere una colorazione propria del grafo) ottenuti con gli autovalori del grafo (cioè gli autovalori della matrice di adiacenza del grafo).
Questo è il motivo per cui ho studiato, come ultimo argomento principale, lo spettro dei grafi di Cayley. Per ottenere informazioni relative allo spettro di un grafo di Cayley dobbiamo indagare la struttura del gruppo G; in particolare le sue rappresentazioni. Infatti esiste un teorema fondamentale che descrive lo spettro del grafo di Cayley, più in generale di un grafo colorato di Cayley, usando i distinti caratteri irriducibili di G.
|
Abstract
My thesis is focused on the study of Cayley graphs. A Cayley graph is a graph whose vertex set is a group G and two vertices u and v are adjacent if and only if uv^(-1) is an element of a given subset S of G. After describing general properties of Cayley graphs, such as its automorphism group and the structure of the graph when G is a free group or when G is a finite group, I have studied three main topics related to the concept of Cayley graph.
The first one is a special class of these graphs: complete rotational Cayley graphs; which are Cayley graphs admitting a particular automorphism ω such that, for some ordering of S={s_i :0≤ i≤d-1},ω(xs_i)=ω(x)s_(i+1) for any x∊ G and an i∊Zd. In particular, I have investigated the Cayley graphs defined by transpositions, including a theorem that completely characterizes the graphs of this type with a complete rotation. The theorem states that Cayley graphs generated by transpositions are essentially of two kinds: modified bubble-sort graphs and Cartesian products of isomorphic modified bubble-sort graph; and generalized star graphs GST(t+q,q) with t and q relatively prime and Cartesian products of isomorphic generalized star graphs GST(t+q,q) with t and q relatively prime.
The second topic deals with the problem of finding a maximal clique in a given graph; where a clique is a subset of the vertex set such that the induced subgraph is complete. In my case the graph is a Paley graph of square order and I have analyzed some results which construct a maximal clique in the graph. Moreover, I have studied some bounds for the clique number (the size of the maximum clique in the graph), the independent number (the cardinality of the largest coclique in the graph) and the chromatic number (the minimum number of colors required to obtain a proper colouring of the graph) obtained with the eigenvalues of the graph (i.e. the eigenvalues of the adjacency matrix of the graph).
This is the reason why I have studied, as the last main topic, the spectrum of Cayley graphs. In order to obtain information about the spectrum of a Cayley graph, we have to investigate the structure of the group G; in particular its representations. In fact there is a fundamental theorem which describes the spectrum of the Cayley graph, more generally a Cayley color graph, using the distinct irreducible characters of G.
|