En el campo matemático de la teoría de grafos , el grafo de Ljubljana es un grafo bipartito no dirigido con 112 vértices y 168 aristas . [1]
Gráfico de Liubliana | |
---|---|
Vértices | 112 |
Bordes | 168 |
Radio | 7 |
Diámetro | 8 |
Circunferencia | 10 |
Automorfismos | 168 |
Número cromático | 2 |
Índice cromático | 3 |
Propiedades | Hamiltoniano cúbico semi-simétrico |
Tabla de gráficos y parámetros |
Es una gráfica cúbica de diámetro 8, radio 7, número cromático 2 e índice cromático 3. Su circunferencia es 10 y hay exactamente 168 ciclos de longitud 10 en ella. También hay 168 ciclos de 12. [2]
Construcción
El gráfico de Ljubljana es hamiltoniano y se puede construir a partir de la notación 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 .
El gráfico de Ljubljana es el gráfico de Levi de la configuración de Ljubljana, una configuración sin cuadrángulos con 56 líneas y 56 puntos. [2] En esta configuración, cada línea contiene exactamente 3 puntos, cada punto pertenece exactamente a 3 líneas y dos líneas cualesquiera se cruzan como máximo en un punto.
Propiedades algebraicas
El grupo de automorfismos del grafo de Ljubljana es un grupo de orden 168. Actúa de forma transitiva en los bordes del grafo pero no en sus vértices: hay simetrías que llevan cada borde a cualquier otro borde, pero no llevan cada vértice a ningún otro vértice. Por lo tanto, el gráfico de Ljubljana es un gráfico semi-simétrico , el tercer gráfico semi-simétrico cúbico más pequeño posible después del gráfico de Gray en 54 vértices y el gráfico de Iofinova-Ivanov en 110 vértices . [3]
El polinomio característico del gráfico de Ljubljana es
Historia
El gráfico de Ljubljana fue publicado por primera vez en 1993 por Brouwer , Dejter y Thomassen [4] como un subgráfico autocomplementario del gráfico de Dejter . [5]
En 1972, Bouwer ya hablaba de un grafo cúbico transitivo de 112 vértices pero no vértice transitivo encontrado por RM Foster , sin embargo inédito. [6] Conder , Malnič, Marušič , Pisanski y Potočnik redescubrieron este gráfico de 112 vértices en 2002 y lo llamaron el gráfico de Ljubljana en honor a la capital de Eslovenia . [2] Demostraron que era el único gráfico cúbico transitivo de vértices de 112 vértices, pero no el gráfico cúbico transitivo de vértice y, por tanto, ese era el gráfico encontrado por Foster.
Galería
El gráfico de Ljubljana es hamiltoniano y bipartito
El índice cromático del gráfico de Ljubljana es 3.
Dibujo alternativo del gráfico de Ljubljana.
Referencias
- ^ Weisstein, Eric W. "Gráfico de Ljubljana" . MathWorld .
- ↑ a b c Conder, M .; Malnič, A .; Marušič, D .; Pisanski, T .; y Potočnik, P. "The Ljubljana Graph". 2002. [1] .
- ^ Marston Conder , Aleksander Malnič, Dragan Marušič y Primož Potočnik. "Un censo de gráficos cúbicos semisimétricos de hasta 768 vértices". Revista de combinatoria algebraica: una revista internacional. Volumen 23, Número 3, páginas 255-294, 2006.
- ^ Brouwer, AE; Dejter, IJ; y Thomassen, C. "Subgrafos altamente simétricos de hipercubos". J. Algebraic Combinat. 2, 25-29, 1993.
- ^ Klin M .; Lauri J .; Ziv-Av M. "Vínculos entre dos gráficos semisimétricos en 112 vértices a través de la lente de los esquemas de asociación", Jour. Computación simbólica., 47–10, 2012, 1175–1191.
- ^ Bouwer, IA "Gráficos regulares transitivos en el borde pero no en el vértice". J. Combin. Th. Ser. B 12, 32-40, 1972.