exponente de la brevedad

---

En la teoría de grafos , el exponente de brevedad es un parámetro numérico de una familia de gráficos que mide qué tan lejos del hamiltoniano pueden estar los gráficos de la familia. Intuitivamente, si es el exponente corto de una familia de gráficos , entonces cada gráfico de vértice en la familia tiene un ciclo de longitud cercana , pero algunos gráficos no tienen ciclos más largos. Más precisamente, para cualquier ordenación de los gráficos en una secuencia , definida como la longitud del ciclo más largo en el gráfico , el exponente de brevedad se define como ^[1]${\ estilo de visualización e}$${\displaystyle {\mathcal {F}}}$${\ estilo de visualización n}$${\ estilo de visualización n ^ {e}}$${\displaystyle {\mathcal {F}}}$${\displaystyle G_{0},G_{1},\puntos}$${\ estilo de visualización h (G)}$${\ estilo de visualización G}$

Este número siempre está en el intervalo de 0 a 1; es 1 para familias de gráficos que siempre contienen un ciclo hamiltoniano o casi hamiltoniano, y 0 para familias de gráficos en los que la longitud de ciclo más larga puede ser menor que cualquier potencia constante del número de vértices.

El exponente de la brevedad de los gráficos poliédricos es . Una construcción basada en cletopos muestra que algunos gráficos poliédricos tienen la longitud de ciclo más larga , ^[2] mientras que también se ha demostrado que cada gráfico poliédrico contiene un ciclo de longitud . ^[3] Los grafos poliédricos son los grafos que son simultáneamente planos y conectados por 3 vértices ; la suposición de conectividad de 3 vértices es necesaria para estos resultados, ya que existen conjuntos de gráficos planos conectados por 2 vértices (como los gráficos bipartitos completos ) con exponente de brevedad 0. Hay muchos resultados adicionales conocidos sobre exponentes de brevedad de restricción subclases de${\ estilo de visualización \ log _ {3} 2 \ aproximadamente 0,631}$${\displaystyle O(n^{\log _{3}2})}$${\displaystyle \Omega (n^{\log _{3}2})}$ ${\displaystyle K_{2,n}}$gráficos planos y poliédricos. ^[1]

Los gráficos cúbicos conectados por 3 vértices (sin la restricción de que sean planos) también tienen un exponente corto que se ha demostrado que se encuentra estrictamente entre 0 y 1. ^{[4] [5]}

---