Rövidségi kitevő

A matematika, azon belül a gráfelmélet területén a rövidségi kitevő vagy rövidségkitevő (shortness exponent) gráfcsaládok olyan numerikus paramétere, ami azt jellemzi, hogy a család gráfjai milyen messze lehetnek attól, hogy Hamilton-körük legyen. Intuitívan, ha az $ℱ$ gráfcsalád rövidségi kitevője $e$, akkor a család minden $n$-csúcsú gráfjában van közel $n^e$ hosszúságú kör, de néhány gráfban nincs ennél hosszabb kör. Precízebben, az $ℱ$ gráfjainak bármelyik $G_0,G_1,\dots$, sorozatba rendezésére, ahol $h(G)$ a $G$ leghosszabb körének hosszát jelöli, a rövidségkitevő meghatározása a következő:

$\underset{i\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{\log h(G_i)}{\log |V(G_i)|}.$

Ez a szám mindig 0 és 1 közé esik; az 1 értéket olyan gráfcsaládokon veszi fel, melyek mindig tartalmaznak Hamilton-kört vagy majdnem Hamilton-kört, a 0 értéket pedig olyan gráfcsaládokon, melyek leghosszabb köre kisebb lehet a csúcsok számának bármely konstans hatványánál.

A poliédergráfok rövidségkitevője ${\log }_{3}2\approx 0,631$. Egy kleetóp-alapú konstrukció segítségével megmutatható, hogy egyes poliédergráfok leghosszabb körének hossza $O(n^{{\log }_{3}2})$, miközben az is ismert, hogy minden poliédergráf tartalmaz $\mathrm{\Omega }(n^{{\log }_{3}2})$ hosszú kört. A poliédergráfok azok a gráfok, melyek egyszerre síkba rajzolhatók és 3-szorosan csúcsösszefüggők; a 3-összefüggőség ezeknek az eredményeknek szükséges feltétele, hiszen léteznek olyan, 2-összefüggő síkbarajzolható gráfok (például a $K_{2,n}$ teljes páros gráfok), melyek rövidségkitevője 0. Számos további eredmény ismert poliédergráfok és síkbarajzolható gráfok korlátozott alosztályainak rövidségkitevőjével kapcsolatban.

A 3-összefüggő 3-reguláris gráfok (a síkbarajzolhatóság követelménye nélkül) rövidségkitevője szintén szigorúan 0 és 1 közé esik.

Fordítás

• Sablon:Fordítás