20.500.12556/RUP-22837 Paint cost spectrum of perfect k-ary trees Spekter stroškov barvanja popolnih k-arnih dreves We determine the paint cost spectrum for perfect k-ary trees. A coloring of the vertices of a graph G with d colors is said to be d-distinguishing if only the trivial automorphism preserves the color classes. The smallest such d is the distinguishing number of G and is denoted Dist(G). The paint cost of d-distinguishing G, denoted ρd(G), is the minimum size of the complement of a color class over all d-distinguishing colorings. A subset S of the vertices of G is said to be a fixing set for G if the only automorphsim that fixes the vertices in S pointwise is the trivial automorphism. The cardinality of a smallest fixing set is denoted Fix(G). In this paper, we explore the breaking of symmetry in perfect k-ary trees by investigating what we define as the paint cost spectrum of a graph G: (Dist(G); ρDist(G)(G), ρDist(G)+1(G), . . . , ρFix(G)+1(G)) and the paint cost ratio of G, which is defined to be the fraction of paint costs in the paint cost spectrum equal to Fix(G). We determine both the paint cost spectrum and the paint cost ratio completely for perfect k-ary trees. We also prove a lemma that is of interest in its own right: given an n-tuple, n ≥ 2 of distinct elements of an ordered abelian group and 1 ≤ k ≤ n! − 1, there exists a k × n row permuted matrix with distinct column sums. Določimo spekter stroškov barvanja za popolna k-arna drevesa. Barvanje vozlišč grafa G z d barvami imenujemo d-razlikovalno, če razrede barv ohranjale trivialni avtomorfizem. Najmanjše takšno številodje razlikovalno število grafa G in ga označimo z Dist(G).Strošek barvanja za d-razlikovanje grafa G, označen z ρd(G), je najmanjša velikost komplementa barvnega razreda med vsemi d-razlikovalnimi barvanji. Pod množico S vozlišč grafa G imenujemo fiksirna množica za G, če je edini avtomorfizem, ki točkovno fiksira vsa vozlišča v S, trivialni avtomorfizem. Kardinalnost najmanjše fiksirne množice označimo s Fix(G). V tem članku raziskujemo razbijanje simetrije v popolnih k-arnih drevesih tako, da preučujemo tisto, kar definiramo kot spekter stroškov barvanja grafa G: (Dist(G); ρDist(G)(G), ρDist(G)+1(G), . . . , ρFix(G)+1(G)) in razmerje stroška barvanja grafa G, ki ga definiramo kot delež stroškov barvanja v spektru stroškov barvanja, ki so enaki Fix(G). Za popolna k-arna drevesa v celoti določimo tako spekter stroškov barvanja kot tudi razmerje stroška barvanja. Dokažemo tudi lemo, ki je zanimiva sama po sebi: za dan n-terec, n≥2, različnih elementov urejene abelove grupe in za 1≤k≤n!−1 obstaja k × n matrika, dobljena spermutacijami vrstic, z različnimi vsotami stolpcev. distinguishing coloring fixing set symmetry cost of distinguishing razlikovalno barvanje fiksirna množica simetrija strošek razločevanja true false true Založba Univerze na Primorskem Angleški jezik Slovenski jezik Članek v reviji 2026-03-23 10:09:11 2026-03-23 10:09:11 2026-03-24 03:06:12 0000-00-00 00:00:00 2026 0 0 17 str. no. 2, [article no.] P2.01 Vol. 9 2026 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2026-01-28 51 2590-9770 10.26493/2590-9770.1847.2ad ADAM_Mafunda,_Merzel,_Perry,_Varvak_2026.pdf ADAM_Mafunda,_Merzel,_Perry,_Varvak_2026.pdf 1 5FB550B3DD42B36BAB2994584F675E34 0ea6e9739684d41c1bdb56d0382a93c9fe3fdbc3770907b634934df355a23986 41b9ed8f-2699-11f1-9e8d-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=33315 Založba Univerze na Primorskem 0 0 0