Índice de brevedad

El índice de brevedad es un parámetro numérico de una familia de gráficos que indica qué tan lejos de ser hamiltonianos pueden estar los gráficos de la familia. Intuitivamente, si es una medida de la brevedad de un gráfico de la familia , entonces cualquier gráfico con vértices tiene un ciclo de longitud cercano a , pero algunos gráficos no tienen ciclos más largos. Más precisamente, para cualquier ordenación de gráficos en la secuencia y una función definida como la duración del ciclo más largo en el gráfico , el índice de brevedad se define como [1] $mi$ ${\mathcal {F}}$ $norte$ ${\ Displaystyle n^{e}}$ ${\mathcal {F}}$ $G_{0},G_{1},\puntos$ $h(G)$ $GRAMO$

\liminf_{i\to \infty}}{\frac {\log h(G_{i})}{\log |V(G_{i})|}}.

Este número siempre está en el rango de 0 a 1. El exponente es 1 si las gráficas de la familia siempre contienen hamiltonianos o un ciclo cercano al hamiltoniano, y 0 si la mayor longitud de ciclos en las gráficas de la familia puede ser menor que cualquier potencia constante del número de vértices.

El índice de brevedad de los gráficos poliédricos es . Una construcción basada en poliedros de Klee muestra que algunos gráficos poliédricos tienen el ciclo de longitud más grande [2] y también se ha demostrado que cualquier gráfico poliédrico contiene un ciclo de longitud [3] . Los gráficos poliédricos son gráficos que son a la vez planos y conectados por 3 vértices . El hecho de que la conexión del vértice 3 sea importante aquí se debe a que hay muchos gráficos planos conectados al vértice 2 (como los gráficos bipartitos completos ) con un exponente corto de 0. Hay muchos resultados adicionales con respecto al exponente corto de las subclases acotadas de planos y poliédricos. gráficos [1] . ${\ estilo de visualización \ log _ {3} 2 \ aproximadamente 0,631}$ $O(n^{\log _{3}2})$ $\Omega (n^{\log _{3}2})$ ${\ Displaystyle K_ {2, n}}$

Los gráficos cúbicos conectados a 3 vértices (sin el requisito de planaridad) también tienen un exponente corto, que (como se ha mostrado) se encuentra estrictamente entre 0 y 1 [4] [5] .

Notas

↑ 1 2 Grünbaum, Walther, 1973 , p. 364–385.
↑ Luna, Moser, 1963 , p. 629–631.
↑ Chen, Yu, 2002 , pág. 80–99.
↑ Bondy, Simonovits, 1980 , p. 987–992.
↑ Jackson, 1986 , pág. 17–26.

Literatura

Branko Grünbaum , Hansjoachim Walther. Exponentes breves de familias de grafos // Journal of Combinatorial Theory . - 1973. - T. 14 . — S. 364–385 . - doi : 10.1016/0097-3165(73)90012-5 .
JW Luna, L. Moser. Caminos simples en poliedros // Pacific Journal of Mathematics . - 1963. - T. 13 . — S. 629–631 .
Guantao Chen, Xingxing Yu. Ciclos largos en gráficos de 3 conexiones // Journal of Combinatorial Theory . - 2002. - T. 86 , núm. 1 . — S. 80–99 . -doi : 10.1006/ jctb.2002.2113 .
J. A. Bondy, M. Simonovits. Ciclos más largos en gráficos regulares de 3 conectados en 3 // Canadian Journal of Mathematics . - 1980. - T. 32 , núm. 4 . — S. 987–992 . -doi : 10.4153 / CJM-1980-076-2 .
Bill Jackson. Ciclos más largos en gráficos cúbicos de 3 conexiones // Journal of Combinatorial Theory . - 1986. - T. 41 , núm. 1 . — P. 17–26 . - doi : 10.1016/0095-8956(86)90024-9 .