Growable realizations: a powerful approach to the Buratti-Horak-Rosa Conjecture

angleški

2022

letnik 22, številka 4

dolžina povezave   Hamiltonova pot   polni graf   rastoča realizacija

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Označimo vozlišča polnega grafa ?$K_v$? s celimi števili ?$\{0, 1, \dots, v-1\}$? in definirajmo dolžino povezave med vozliščema ?$x$? in ?$y$? kot ?$\min (|x-y|,v-|x-y|)$?. Naj bo ?$L$? multimnožica velikosti ?$v-1$? z osnovno množico, vsebovano v množici ?$\{1, \dots, \lfloor v/2 \rfloor \}$?. Buratti-Horak-Roseova domneva pravi, da obstaja Hamiltonova pot v polnem grafu ?$K_v$?, za katero velja, da dolžine njenih povezav tvorijo natanko multimnožico ?$L$?, če in samo če je za poljuben delitelj ?$d$? števila ?$v$? število večkratnikov števila ?$d$?, ki nastopajo v množici ?$L$?, največ ?$v-d$?. Vpeljemo t.i. rastoče realizacije, ki nam omogočajo dokazati mnoge nove primere te domneve in na novo dokazati znane rezultate enostavneje. Predstavimo dva primera uporabe te nove metode: popolno rešitev, če je osnovna množica vsebovana v ?$\{1, 4, 5\}$? ali v ?$\{1, 2, 3, 4\}$?, in delni rezultat, če ima osnovna množica obliko ?$\{1, x, 2x\}$?. Verjamemo, da za vsako množico ?$U$? pozitivnih celih števil obstaja končna množica rastočih realizacij, ki implicira resničnost Buratti-Horak-Roseove domneve za vse multimnožice z osnovno množico ?$U$?, z izjemo končno mnogo takšnih multimnožic.

02.10.2023