509 KB71 KB142 KB4 KB200820262026Agirseven, OnurOllis, M. A.letnik:26številka:4, article p4.07str. 1-27DOI:10.26493/1855-3974.3348.c69ISSN:1855-3974COBISSID_HOST:294225923URN:URN:NBN:SI:doc-1GSMAYPUenUniverza na PrimorskemArs mathematica contemporaneacomplete graphdolžina povezaveedge-lengthgrid-based graphHamiltonian pathHamiltonova potmrežasti grafpolni grafrealizacijarealizationGrid-based graphs, linear realizations, and the Buratti-Horak-Rosa conjecture|Label the vertices of the complete graph K_v with the integers {0, 1, …, v - 1} and define the length l of the edge between distinct vertices labeled x and y by l(x, y) = min (|y - x|,v - |y - x|). A realization of a multiset L of size v - 1 is a Hamiltonian path through K_v whose edge labels are L. The Buratti-Horak-Rosa (BHR) Conjecture is that there is a realization for a multiset L if and only if for any divisor d of v the number of multiples of d in L is at most v - d. We introduce “grid-based graphs" as a useful tool for constructing particular types of realizations, called “linear realizations,"especially when the multiset in question has a support of size 3. This lets us prove many new instances of the BHR Conjecture, including those for multisets of the form {1^a, x^b, y^c} when a ? x + y - ?, where ? is the number of even elements in {x, y}, and those for all multisets of the following forms for sufficiently large v with gcd (v,y) = 1 for all y ? L: •{1^a, 2^b, x^c}, except possibly when a ? {1, 2} and x is odd, •{1^a, x^b, (x + 1)^c}. This establishes that there are infinitely many sets U of size 3 for which there are infinitely many values of v where the BHR Conjecture holds for each multiset with support U. We also show that the BHR Conjecture holds for {1^a, x^b, (x + 1)^c} when x ? {7, 9, 10} and gcd (v, x) = gcd (v, x + 1) = 1Označimo vozlišča polnega grafa K_v s celimi števili iz množice {0, 1, …, v - 1} in definirajmo dolžino l povezave med različnima vozliščema, označenima z x in y, kot l(x, y) = min(|y - x|, v - |y - x|). Realizacija multimnožice L velikosti v - 1 je Hamiltonova pot v grafu K_v, katere oznake povezav tvorijo množico L. Buratti–Horak–Rosova (BHR) domneva pravi, da realizacija multimnožice L obstaja natanko tedaj, ko za vsak delitelj d števila v število veˇckratnikov števila d v L ni večje od v - d. Vpeljemo “mrežaste grafe” kot uporabno orodje za konstrukcijo posebnih vrst realizacij, imenovanih “linearne realizacije”, zlasti kadar ima obravnavana multimnožica nosilec velikosti 3. S tem dokažemo številne nove primere BHR-domneve, med drugim za multimnožice oblike {1^a, x^b, y^c}, kadar velja a ? x + y - ?, kjer je ? število sodih elementov v množici {x, y}, ter za vse multimnožice naslednjih oblik pri dovolj velikem v, če velja gcd(v, y) = 1 za vsak y ? L: • {1^a, 2^b, x^c}, razen morda kadar je a ? {1, 2} in je x liho število, • {1^a, x^b, (x + 1)^c}. S tem pokažemo, da obstaja neskončno mnogo množic U velikosti 3, za katere obstaja neskončno mnogo vrednosti v, pri katerih BHR-domneva velja za vsako multimnožico z nosilcem U . Poleg tega pokažemo, da BHR-domneva velja za {1^a, x^b, (x + 1)^c}, kadar je x ? {7, 9, 10} in gcd(v, x) = gcd(v, x + 1) = 1TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije