Indicator de scurtare

Indicele de scurtare este un parametru numeric al unei familii de grafice care indică cât de departe de a fi hamiltoniene pot fi graficele familiei. În mod intuitiv, dacă este o măsură a scurtității unui grafic al familiei , atunci orice grafic cu vârfuri are un ciclu de lungime apropiat de , dar unele grafice nu au cicluri mai lungi. Mai precis, pentru orice ordonare a graficelor din secvența și o funcție definită ca lungimea celui mai lung ciclu din grafic , indicele de scurtare este definit ca [1] $e$ ${\mathcal {F}}$ $n$ $n^{e}$ ${\mathcal {F}}$ $G_{0},G_{1},\dots$ $h(G)$ $G$

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

Acest număr este întotdeauna în intervalul de la 0 la 1. Exponentul este 1 dacă graficele familiei conțin întotdeauna hamiltonieni sau un ciclu apropiat de hamiltonian și 0 dacă cea mai mare lungime a ciclurilor din graficele familiei poate fi mai mică decât orice putere constantă a numărului de vârfuri.

Indicele de scurtare al graficelor poliedrice este . O construcție bazată pe poliedre Klee arată că unele grafuri poliedrice au cel mai mare ciclu de lungime [2] , și s-a dovedit, de asemenea, că orice graf poliedric conține un ciclu de lungime [3] . Graficele poliedrice sunt grafice care sunt atât plane , cât și conectate cu 3 vârfuri . Faptul că conexiunea cu vârful 3 este importantă aici se datorează faptului că există multe grafice plane conectate cu vârfuri 2 (cum ar fi grafice bipartite complete ) cu exponent de scurtare 0. Există multe rezultate suplimentare cu privire la exponentul de scurtitate al subclaselor mărginite de planare și poliedrice. grafice [1] . $\log _{3}2\aproximativ 0,631$ $O(n^{\log _{3}2})$ $\Omega (n^{\log _{3}2})$ $K_{2,n)$

Graficele cubice legate de vârfuri-3 (fără cerința de planaritate) au și un exponent de scurtare, care (după cum s-a arătat) se află strict între 0 și 1 [4] [5] .

Note

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

Literatură

Branko Grünbaum , Hansjoachim Walther. Exponenții de scurtare ai familiilor de grafuri // Journal of Combinatorial Theory . - 1973. - T. 14 . — S. 364–385 . - doi : 10.1016/0097-3165(73)90012-5 .
JW Moon, L. Moser. Căi simple pe poliedre // Pacific Journal of Mathematics . - 1963. - T. 13 . — S. 629–631 .
Guantao Chen, Xingxing Yu. Cicluri lungi în grafice cu 3 conexiuni // Journal of Combinatorial Theory . - 2002. - T. 86 , nr. 1 . — S. 80–99 . - doi : 10.1006/jctb.2002.2113 .
J. A. Bondy, M. Simonovits. Cele mai lungi cicluri în 3-conectate 3-grafice regulate // Canadian Journal of Mathematics . - 1980. - T. 32 , nr. 4 . — S. 987–992 . - doi : 10.4153/CJM-1980-076-2 .
Bill Jackson. Cele mai lungi cicluri în grafice cubice cu 3 conexiuni // Journal of Combinatorial Theory . - 1986. - T. 41 , nr. 1 . — S. 17–26 . - doi : 10.1016/0095-8956(86)90024-9 .