Grafo de Ljubljana

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Grafo de Ljubljana
Ljubljana graph hamiltonian.svg

O grafo de Ljubljana
vértices 112
arestas 168
Raio 7
Diâmetro 8
Cintura 10
Automorfismos 168
Número cromático 2
Índice cromático 3
Propriedades Cúbico
Hamiltoniano
Semi-simétrico

No campo da matemática da teoria dos grafos o grafo de Ljubljana é um grafo não direcionado bipartido com 112 vértices e 168 arestas.

É um grafo cúbico com diâmetro 8, raio 7, número cromático 2 e índice cromático 3. Sua cintura é 10 e há exatamente 168 ciclos de comprimento 10 nele. Há também 168 ciclos de comprimento 12.[1]

Construção[editar | editar código-fonte]

O grafo de Ljubljana é Hamiltoniano e pode ser construído a partir da notação LCF : [47, -23, -31, 39, 25, -21, -31, -41, 25, 15, 29, -41, -19, 15, -49, 33, 39, -35, -21, 17, -33, 49, 41, 31, -15, -29, 41, 31, -15, -25, 21, 31, -51, -25, 23, 9, -17, 51, 35, -29, 21, -51, -39, 33, -9, -51, 51, -47, -33, 19, 51, -21, 29, 21, -31, -39]2.

O grafo de Ljubljana é o grafo de Levi da configuração de Ljubljana, uma configuração quadrangular livre com 56 linhas e 56 pontos.[1] Nesta configuração, cada linha contém exatamente três pontos, cada ponto pertence a exatamente 3 linhas e quaisquer duas linhas se cruzam em no máximo um ponto.

Propriedades algébricas[editar | editar código-fonte]

O grupo de automorfismo do grafo de Ljubljana é um grupo de ordem 168. Ele age transitivamente em suas arestas, mas não em seus vértices: existem simetrias levando cada aresta para qualquer outra aresta, mas não levando cada vértice para qualquer outro vértice. Portanto, o grafo de Ljubljana é um grafo semi-simétrico, o terceiro menor grafo cúbico semi-simétrico possível após o grafo de Levi em 54 vértices e o grafo de Iofinova-Ivanov em 110 vértices.[2]

O polinômio característico do grafo de Ljubljana é

(x-3)x^{14}(x+3)(x^2-x-4)^7(x^2-2)^6(x^2+x-4)^7(x^4-6x^2+4)^{14}.\

História[editar | editar código-fonte]

O grafo de Ljubljana foi publicado pela primeira vez em 1993 por Brouwer, Dejter e Thomassen.[3]

Em 1972, Bouwer já estava falando de uma de um grafo cúbico de 112 vértices aresta- mas não vértice-transitivo encontrado por R. M. Foster, mas não publicado ainda.[4] Conder, Malnic, Marusic, Pisanski e Potočnik redescobriram este grafo de 112 vértices em 2002 e nomearam-no grafo de Ljubljana capital da Eslovénia. Eles provaram que ele era o único grafo cúbico de 112 vértices aresta- mas não vértice-transitivo cúbicos e, portanto, que o grafo era aquele encontrado por Foster.

Galeria[editar | editar código-fonte]

Referências

  1. a b Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; and Potočnik, P. "The Ljubljana Graph." 2002. [1].
  2. Marston Conder, Aleksander Malnič, Dragan Marušič and Primž Potočnik. "A census of semisymmetric cubic graphs on up to 768 vertices." Journal of Algebraic Combinatorics: An International Journal. Volume 23, Issue 3, pages 255-294, 2006.
  3. Brouwer, A. E.; Dejter, I. J.; and Thomassen, C. "Highly Symmetric Subgraphs of Hypercubes." J. Algebraic Combinat. 2, 25-29, 1993.
  4. Bouwer, I. A. "On Edge But Not Vertex Transitive Regular Graphs." J. Combin. Th. Ser. B 12, 32-40, 1972.