Language: | English |
---|---|
Year of publishing: | 2008 |
Typology: | 1.08 - Published Scientific Conference Contribution |
Organization: | UM FNM - Faculty of Natural Sciences and Mathematics |
UDC: | 519.17 |
COBISS: | 14626905 |
ISSN: | 0195-6698 |
Views: | 1121 |
Downloads: | 75 |
Average score: | 0 (0 votes) |
Metadata: |
Secondary language: | Slovenian |
---|---|
Secondary title: | Razlikovalno število kartezičnih produktov polnih grafov |
Secondary abstract: | The distinguishing number ▫$D(G)$▫ of a graph ▫$G$▫ is the least integer ▫$d$▫ such that ▫$G$▫ has a labeling with ▫$d$▫ labels that is preserved only by a trivial automorphism. We prove that Cartesian products of relatively prime graphs whose sizes do not differ too much can be distinguished with a small number of colors. We determine the distinguishing number of the Cartesian product ▫$K_k \square K_k$▫ forall ▫$k$▫ and ▫$n$▫, either explicitly or by a short recursion. We also introduce column-invariant sets of vectors and prove a switching lemma that plays a key role in the proofs. |
Secondary keywords: | Matematika;Teorija grafov; |
URN: | URN:SI:UM: |
Type (COBISS): | Article |
Pages: | Str. 922-929 |
DOI: | 10.1016/j.ejc.2007.11.018 |
ID: | 1473512 |