Distinguishing tournaments with small label classes
A d-distinguishing vertex (arc) labeling of a digraph is a vertex (arc) labeling using d labels that is not preserved by any nontrivial automorphism. Let ρ(T) (ρ′(T)) be the minimum size of a label class in a 2-distinguishing vertex (arc) labeling of a tournament T. Gluck's Theorem implies that ρ(T)...
| Author: | |
|---|---|
| Format: | Article |
| Publication date: | 2019 |
| Country: | España |
| Institution: | Universitat Politècnica de Catalunya (UPC) |
| Repository: | UPCommons. Portal del coneixement obert de la UPC |
| Language: | English |
| OAI Identifier: | oai:upcommons.upc.edu:2117/180131 |
| Online Access: | https://hdl.handle.net/2117/180131 |
| Access Level: | Open access |
| Keyword: | Graph theory Grafs, Teoria de Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica |
| _version_ | 1878731430834470912 |
|---|---|
| author | Lozano Boixadors, Antoni|||0000-0002-3633-063X |
| author_browse | Lozano Boixadors, Antoni|||0000-0002-3633-063X |
| author_facet | Lozano Boixadors, Antoni|||0000-0002-3633-063X |
| author_role | author |
| collection | UPCommons. Portal del coneixement obert de la UPC |
| description | A d-distinguishing vertex (arc) labeling of a digraph is a vertex (arc) labeling using d labels that is not preserved by any nontrivial automorphism. Let ρ(T) (ρ′(T)) be the minimum size of a label class in a 2-distinguishing vertex (arc) labeling of a tournament T. Gluck's Theorem implies that ρ(T) ≤ ⌊n/2⌋ for any tournament T of order n. We construct a family of tournaments ℌ such that ρ(T) ≥ ⌊n/2⌋ for any tournament of order n in ℌ. Additionally, we prove that ρ′(T) ≤ ⌊7n/36⌋ + 3 for any tournament T of order n and ρ′(T) ≥ ⌈n/6⌉ when T ∈ ℌ and has order n. These results answer some open questions stated by Boutin. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | ES_2f73573584bc5bbf2bfce29ca8ff0dc6 |
| institution | Universitat Politècnica de Catalunya (UPC) |
| instname_str | Universitat Politècnica de Catalunya (UPC) |
| language | eng |
| network_acronym_str | ES |
| network_name_str | España |
| oai_identifier_str | oai:upcommons.upc.edu:2117/180131 |
| publishDate | 2019 |
| publishDateSort | 2019 |
| reponame_str | UPCommons. Portal del coneixement obert de la UPC |
| spelling | Distinguishing tournaments with small label classes Lozano Boixadors, Antoni|||0000-0002-3633-063X Graph theory Grafs, Teoria de Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica A d-distinguishing vertex (arc) labeling of a digraph is a vertex (arc) labeling using d labels that is not preserved by any nontrivial automorphism. Let ρ(T) (ρ′(T)) be the minimum size of a label class in a 2-distinguishing vertex (arc) labeling of a tournament T. Gluck's Theorem implies that ρ(T) ≤ ⌊n/2⌋ for any tournament T of order n. We construct a family of tournaments ℌ such that ρ(T) ≥ ⌊n/2⌋ for any tournament of order n in ℌ. Additionally, we prove that ρ′(T) ≤ ⌊7n/36⌋ + 3 for any tournament T of order n and ρ′(T) ≥ ⌈n/6⌉ when T ∈ ℌ and has order n. These results answer some open questions stated by Boutin. Peer Reviewed https://hdl.handle.net/2117/180131 |
| spellingShingle | Distinguishing tournaments with small label classes Lozano Boixadors, Antoni|||0000-0002-3633-063X Graph theory Grafs, Teoria de Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica |
| title | Distinguishing tournaments with small label classes |
| title_full | Distinguishing tournaments with small label classes |
| title_fullStr | Distinguishing tournaments with small label classes |
| title_full_unstemmed | Distinguishing tournaments with small label classes |
| title_short | Distinguishing tournaments with small label classes |
| title_sort | Distinguishing tournaments with small label classes |
| topic | Graph theory Grafs, Teoria de Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica |
| topic_facet | Graph theory Grafs, Teoria de Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica |
| url | https://hdl.handle.net/2117/180131 |