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 ${\mathcal {F}}$ 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 ${\mathcal {F}}$ 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ő:

$\liminf _{i\to \infty }{\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 $\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

• Ez a szócikk részben vagy egészben a Shortness exponent című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.