| Naslov: | Paint cost spectrum of perfect k-ary trees |
|---|
| Avtorji: | ID Mafunda, Sonwabile (Avtor)
ID Merzel, Jonathan L. (Avtor)
ID Perry, Katherine E. (Avtor)
ID Varvak, Anna (Avtor) |
|---|
| Datoteke: |  ADAM_Mafunda,_Merzel,_Perry,_Varvak_2026.pdf (441,47 KB)
MD5: 5FB550B3DD42B36BAB2994584F675E34
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | ZUP - Založba Univerze na Primorskem
|
|---|
| Opis: | 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. |
|---|
| Ključne besede: | distinguishing coloring, fixing set, symmetry, cost of distinguishing |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 28.01.2026 |
|---|
| Založnik: | Založba Univerze na Primorskem |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | 17 str. |
|---|
| Številčenje: | Vol. 9, no. 2, [article no.] P2.01 |
|---|
| PID: | 20.500.12556/RUP-22837  |
|---|
| UDK: | 51 |
|---|
| eISSN: | 2590-9770 |
|---|
| DOI: | 10.26493/2590-9770.1847.2ad |
|---|
| Datum objave v RUP: | 23.03.2026 |
|---|
| Število ogledov: | 215 |
|---|
| Število prenosov: | 5 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
