Circuitos hamiltonianos em grafos de Cayley

Resumo:

Se $\Gamma$ é um grupo e $S$ é um conjunto de geradores para ele, o grafo de Cayley de $(\Gamma,S)$ tem $\Gamma$ como conjunto de vértices, e arestas dirigidas $g\rightarrow gs$ para cada $g \in \Gamma$, $s \in S$.

A construção de circuitos hamiltonianos em certos grafos de Cayley tem várias aplicações na geração eficiente de objetos combinatórios; algumas dessas construções são conhecidas como códigos de Gray. Juntando a isso a extraordinária simetria inerente aos grafos de Cayley, é natural perguntar se todo grafo de Cayley finito é hamiltoniano.

Essa questão foi formulada por Lovasz há mais de 30 anos e permanece em aberto. Será apresentado um pequeno panorama geral da área, descrevendo algumas classes de grafos de Cayley para os quais a resposta é afirmativa (para deixar a pergunta em aberto, evitarei apresentar casos com resposta negativa), incluindo resultados recentes.