Exponent krátkosti - Shortness exponent

v teorie grafů, exponent krátkosti je číselný parametr rodiny grafů, který měří, jak daleko od Hamiltonian grafy v rodině mohou být. Intuitivně, pokud ${ displaystyle e}$ je exponent krátkosti rodiny grafů ${ displaystyle { mathcal {F}}}$, pak každý ${ displaystyle n}$-vrcholový graf v rodině má cyklus délky blízký ${ displaystyle n ^ {e}}$ ale některé grafy nemají delší cykly. Přesněji, pro jakékoli uspořádání grafů v ${ displaystyle { mathcal {F}}}$ do sekvence ${ displaystyle G_ {0}, G_ {1}, tečky}$, s ${ displaystyle h (G)}$ definována jako délka nejdelšího cyklu v grafu ${ displaystyle G}$, exponent krátkosti je definován jako^[1]

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

Toto číslo je vždy v intervalu od 0 do 1; je to 1 pro rodiny grafů, které vždy obsahují Hamiltonianův nebo téměř Hamiltonovský cyklus, a 0 pro rodiny grafů, ve kterých může být nejdelší délka cyklu menší než jakákoli konstantní síla počtu vrcholů.

Exponent krátkosti polyedrické grafy je ${ displaystyle log _ {3} 2 přibližně 0,631}$. Konstrukce založená na kleetopy ukazuje, že některé polyedrické grafy mají nejdelší délku cyklu ${ displaystyle O (n ^ { log _ {3} 2})}$,^[2] zatímco bylo také prokázáno, že každý polyedrický graf obsahuje cyklus délky ${ displaystyle Omega (n ^ { log _ {3} 2})}$.^[3] Polyedrické grafy jsou grafy, které jsou současně rovinný a 3-vrchol připojený; pro tyto výsledky je nezbytný předpoklad konektivity 3 vrcholů, protože existují sady rovinných grafů spojených 2 vrcholy (například kompletní bipartitní grafy ${ displaystyle K_ {2, n}}$) s exponentem krátkosti 0. Existuje mnoho dalších známých výsledků na exponentech krátkosti omezených podtříd třídy rovinný a mnohostěnné grafy.^[1]

3-vrchol připojen kubické grafy (bez omezení, že jsou rovinné) mají také exponent krátkosti, u kterého bylo prokázáno, že leží striktně mezi 0 a 1.^[4][5]

Reference