Sobre Grafos de Cayley, Permutações e Circuitos Reversíveis

Neste trabalho, apresentamos propriedades importantes de alguns grafos de Cayley associados aos problemas: ciclo hamiltoniano, interconexão de redes, rearranjo de genomas e circuito reversível.
Em particular, mostramos que os grafos Hl,p e H'l,p são grafos de Cayley e têm ciclo hamiltoniano, o que corrobora a conjectura de Lovász. Estabelecemos que o grafo H'l,p tem grau (2l-2) e diâmetro (p/2(l-1)), e o grafo Hl,p tem grau (l(l-1)) e o diâmetro é calculado por um algoritmo com complexidade de tempo de O(l). As propriedades estabelecidas suportam que os grafos Hl,p e H'l,p são bons esquemas para interconexão de redes.
O grafo de rearranjo por transposições pré-fixadas unitárias é formado pelo conjunto de vértices que são as permutações do grupo simétrico Sn, e pelo conjunto de arestas obtido da seguinte forma: dois vértices são adjacentes se existe uma transposição pré-fixada unitária que, aplicada a uma permutação, gera a outra. Apresentamos propriedades deste grafo de Cayley, entre as principais mostramos que o diâmetro é exatamente n - 1 e a existência de ciclo hamiltoniano, que corrobora a conjectura de Lovász sobre os caminhos hamiltonianos nos grafos vértice-transitivos.
Usando grafos de Cayley desenvolvemos uma estrutura para ajudar na análise das contagem de portas e dos custos quânticos resultantes das sínteses de circuitos reversíveis. Apresentamos um algoritmo para a síntese de circuitos reversíveis com  portas Toffoli de controles mistos. Além disso, temos que o limite inferior para o diâmetro do grafo de Cayley.