A short note on graphs with long Thomason chains.

Szczegóły
Opis

Tytuł:: A short note on graphs with long Thomason chains.
Krótka notatka o grafach z długimi łańcuchami Thomasona
Autorzy:: Briański, Marcin
Słowa kluczowe:: Thomason's algorithm, Second Hamiltonian Cycle, Cubic graphs,
Algorytm Thomasona, Drugi cykl Hamiltona, Grafy Kubiczne,
Język:: angielski
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego
: Inne

Przejdź do źródła

Prezentujemy rodzinę 3-spójnych kubicznych planarnych grafów, w których algorytm Thomasona wykonuje wykładniczo wiele kroków. Podstawa wykładnika wynosi ok. 1.1812..., co jest większą wartością niż poprzednio znane przykłady.

We present a family of 3-connected cubic planar Hamiltonian graphs with an exponential numberof steps required by Thomason’s algorithm. The base of the exponent is approximately 1.1812..., whichexceeds previous results in the area.

Informacja

A short note on graphs with long Thomason chains.