Grafo de Ljubljana
| Grafo de Ljubljana | |
|---|---|
 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 é
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]
-
O número cromático do grafo de Ljubljana é 2. -
O índice cromático do grafo de Ljubljana é 3. -
Desenho alternativo do grafo de Ljubljana. -
O grafo de Ljubljana é o grafo de Levi desta configuração.
Referências
- ↑ a b Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; and Potočnik, P. "The Ljubljana Graph." 2002. [1].
- ↑ 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.
- ↑ Brouwer, A. E.; Dejter, I. J.; and Thomassen, C. "Highly Symmetric Subgraphs of Hypercubes." J. Algebraic Combinat. 2, 25-29, 1993.
- ↑ Bouwer, I. A. "On Edge But Not Vertex Transitive Regular Graphs." J. Combin. Th. Ser. B 12, 32-40, 1972.