Balaban de 11 jaulas

Gráfico 3-regular

En el campo matemático de la teoría de grafos , la jaula de 11 de Balaban o jaula de Balaban (3,11) es un grafo regular de 3 elementos con 112 vértices y 168 aristas que lleva el nombre de Alexandru T. Balaban . ^[1]

La jaula 11 de Balaban es la única jaula (3,11) . Fue descubierta por Balaban en 1973. ^[2] La singularidad fue demostrada por Brendan McKay y Wendy Myrvold en 2003. ^[3]

La jaula 11 de Balaban es un gráfico hamiltoniano y se puede construir por escisión de la jaula 12 de Tutte eliminando un pequeño subárbol y suprimiendo los vértices resultantes de grado dos. ^[4]

Tiene número de independencia 52, ^[5] número cromático 3, índice cromático 3, radio 6, diámetro 8 y circunferencia 11. También es un grafo conexo por 3 vértices y un grafo conexo por 3 aristas .

El polinomio característico de la jaula 11 de Balaban es:

${\displaystyle (x-3)x^{12}(x^{2}-6)^{5}(x^{2}-2)^{12}(x^{3}-x^{2}-4x+2)^{2}\cdot }$

${\displaystyle \cdot (x^{3}+x^{2}-6x-2)(x^{4}-x^{3}-6x^{2}+4x+4)^{4}\cdot }$

${\displaystyle \cdot (x^{5}+x^{4}-8x^{3}-6x^{2}+12x+4)^{8}}$.

El grupo de automorfismos de la jaula 11 de Balaban es de orden 64. ^[4]

Galería

• 
  El número cromático de la jaula 11 de Balaban es 3.
• 
  El índice cromático del Balaban de 11 jaulas es 3.
• 
  Dibujo alternativo del Balaban de 11 jaulas. ^[6]

Referencias

1. Weisstein, Eric W. "Balaban 11-Cage". MundoMatemático .
2. Balaban, Alexandru T. , Gráficos trivalentes de circunferencias nueve y once, y relaciones entre jaulas , Revue Roumaine de Mathématiques Pures et Appliquées 18 (1973), 1033-1043. Señor 0327574
3. Weisstein, Eric W. "Gráfico de jaula". MundoMatemático .
4. Geoffrey Exoo y Robert Jajcay, Estudio dinámico de jaulas, Electr. J. Combin. 15 (2008)
5. Sanar (2016)
6. P. Eades , J. Marks, P. Mutzel , S. North. "Informe del concurso de dibujo gráfico", TR98-16, diciembre de 1998, Mitsubishi Electric Research Laboratories.

Referencias

• Heal, Maher (2016), "Una formulación de programación cuadrática para encontrar el conjunto independiente máximo de cualquier gráfico", Conferencia internacional de 2016 sobre ciencia computacional e inteligencia computacional , Las Vegas: IEEE Computer Society