| Title: | Paint cost spectrum of perfect k-ary trees |
|---|
| Authors: | ID Mafunda, Sonwabile (Author)
ID Merzel, Jonathan L. (Author)
ID Perry, Katherine E. (Author)
ID Varvak, Anna (Author) |
|---|
| Files: |  ADAM_Mafunda,_Merzel,_Perry,_Varvak_2026.pdf (441,47 KB)
MD5: 5FB550B3DD42B36BAB2994584F675E34
|
|---|
| Language: | English |
|---|
| Work type: | Article |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | ZUP - University of Primorska Press
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | distinguishing coloring, fixing set, symmetry, cost of distinguishing |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 28.01.2026 |
|---|
| Publisher: | Založba Univerze na Primorskem |
|---|
| Year of publishing: | 2026 |
|---|
| Number of pages: | 17 str. |
|---|
| Numbering: | Vol. 9, no. 2, [article no.] P2.01 |
|---|
| PID: | 20.500.12556/RUP-22837  |
|---|
| UDC: | 51 |
|---|
| eISSN: | 2590-9770 |
|---|
| DOI: | 10.26493/2590-9770.1847.2ad |
|---|
| Publication date in RUP: | 23.03.2026 |
|---|
| Views: | 216 |
|---|
| Downloads: | 5 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
