Korthetsindex

Korthetsindexet är en numerisk parameter för en familj av grafer som indikerar hur långt från att vara Hamiltonskt familjens grafer kan vara. Intuitivt, om är ett mått på kortheten av en graf av familjen , då har varje graf med hörn en cykel med längd nära , men vissa grafer har inte längre cykler. Närmare bestämt, för varje ordning av grafer i sekvensen och en funktion definierad som längden på den längsta cykeln i grafen , definieras korthetsindexet som [1] $e$ ${\mathcal {F}}$ $n$ ${\displaystyle 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})|}}.

Detta tal ligger alltid i intervallet från 0 till 1. Exponenten är 1 om familjens grafer alltid innehåller Hamiltonianer eller en cykel nära Hamiltonian, och 0 om den största längden av cykler i familjens grafer kan vara mindre än någon konstant potens av antalet hörn.

Korthetsindexet för polyedriska grafer är . En konstruktion baserad på Klee polyhedra visar att vissa polyedriska grafer har den största längdcykeln [2] , och det har också bevisats att alla polyedriska grafer innehåller en längdcykel [3] . Polyedriska grafer är grafer som är både plana och 3-vertex-anslutna . Det faktum att vertex 3-anslutningen är viktig här beror på att det finns många vertex-2-anslutna plana grafer (såsom kompletta tvådelade grafer ) med korthetsexponent 0. Det finns många ytterligare resultat angående korthetsexponenten för avgränsade underklasser av plana och polyedriska grafer [1] . $\log _{3}2\approx 0,631$ $O(n^{\log _{3}2})$ $\Omega (n^{\log _{3}2})$ ${\displaystyle K_{2,n))$

Vertex-3-kopplade kubikgrafer (utan planaritetskravet) har också en korthetsexponent, som (som visats) ligger strikt mellan 0 och 1 [4] [5] .

Anteckningar

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

Litteratur

Branko Grünbaum , Hansjoachim Walther. Korthetsexponenter för graffamiljer // Journal of Combinatorial Theory . - 1973. - T. 14 . — S. 364–385 . - doi : 10.1016/0097-3165(73)90012-5 .
JW Moon, L. Moser. Enkla vägar på polyedrar // Pacific Journal of Mathematics . - 1963. - T. 13 . — S. 629–631 .
Guantao Chen, Xingxing Yu. Långa cykler i 3-kopplade grafer // Journal of Combinatorial Theory . - 2002. - T. 86 , nr. 1 . — S. 80–99 . - doi : 10.1006/jctb.2002.2113 .
J. A. Bondy, M. Simonovits. Längsta cykler i 3-kopplade 3-regelbundna grafer // Canadian Journal of Mathematics . - 1980. - T. 32 , nr. 4 . — S. 987–992 . - doi : 10.4153/CJM-1980-076-2 .
Bill Jackson. Längsta cykler i 3-kopplade kubikgrafer // Journal of Combinatorial Theory . - 1986. - T. 41 , nr. 1 . — S. 17–26 . - doi : 10.1016/0095-8956(86)90024-9 .