Exponente de brevedad

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

${\displaystyle \liminf _{i\to \infty }{\frac {\log h(G_{i})}{\log |V(G_{i})|}}.}$

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 del ciclo más largo puede ser menor que cualquier potencia constante del número de vértices.

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

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

Referencias

1. Grünbaum, Branko ; Walther, Hansjoachim (1973), "Exponentes de corto plazo de familias de grafos", Journal of Combinatorial Theory , Serie A, 14 : 364–385, doi :10.1016/0097-3165(73)90012-5, hdl : 10338.dmlcz/101257 , MR  0314691.
2. Moon, JW; Moser, L. (1963), "Caminos simples en poliedros", Pacific Journal of Mathematics , 13 : 629–631, doi : 10.2140/pjm.1963.13.629 , MR  0154276.
3. Chen, Guantao; Yu, Xingxing (2002), "Ciclos largos en grafos 3-conectados", Journal of Combinatorial Theory , Serie B, 86 (1): 80–99, doi : 10.1006/jctb.2002.2113 , MR  1930124.
4. Bondy, JA ; Simonovits, M. (1980), "Ciclos más largos en grafos 3-regulares conexos", Revista canadiense de matemáticas , 32 (4): 987–992, doi : 10.4153/CJM-1980-076-2 , MR  0590661.
5. Jackson, Bill (1986), "Ciclos más largos en grafos cúbicos 3-conectados", Journal of Combinatorial Theory , Serie B, 41 (1): 17–26, doi :10.1016/0095-8956(86)90024-9, MR  0854600.