454 KB71 KB200820252022Ollis, M. A.Pasotti, AnitaPellegrini, Marco AntonioSchmitt, John R.letnik:22številka:4str. 567-594DOI:10.26493/1855-3974.2659.be1COBISSID_HOST:141370627ISSN:1855-3966URN:URN:NBN:SI:doc-OJAABSC1enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneacomplete graphdolžina povezaveedge-lengthgrowable realizationHamiltonian pathHamiltonova potpolni grafrastoča realizacijaGrowable realizations: a powerful approach to the Buratti-Horak-Rosa Conjecture|Label the vertices of the complete graph ?$K_v$? with the integers ?$\{0, 1, \dots, v-1\}$? and define the length of the edge between the vertices ?$x$? and ?$y$? to be ?$\min (|x-y|,v-|x-y|)$?. Let ?$L$? be a multiset of size ?$v-1$? with underlying set contained in ?$\{1, \dots, \lfloor v/2 \rfloor \}$?. The Buratti-Horak-Rosa Conjecture is that there is a Hamiltonian path in ?$K_v$? whose edge lengths are exactly ?$L$? if and only if for any divisor ?$d$? of ?$v$? the number of multiples of ?$d$? appearing in ?$L$? is at most ?$v-d$?. We introduce "growable realizations", which enable us to prove many new instances of the conjecture and to reprove known results in a simpler way. As examples of the new method, we give a complete solution when the underlying set is contained in ?$\{1, 4, 5\}$? or in ?$\{1, 2, 3, 4\}$? and a partial result when the underlying set has the form ?$\{1, x, 2x\}$?. We believe that for any set ?$U$? of positive integers there is a finite set of growable realizations that implies the truth of the Buratti-Horak-Rosa Conjecture for all but finitely many multisets with underlying set ?$U$?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žicTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije