Sandi Klavžar (Author), Xuding Zhu (Author)

Abstract

The distinguishing number ▫$D(G)$▫ of a graph ▫$G$▫ is the least integer ▫$d$▫ such that there is a ▫$d$▫-labeling of the vertices of ▫$G$▫ which is not preserved by any nontrivial automorphism. For a graph ▫$G$▫ let ▫$G^r$▫ be the ▫$r$▫-th power of ▫$G$▫ with respect to the Cartesian product. It is proved that ▫$D(G^r) = 2$▫ for any connected graph ▫$G$▫ with at least 3 vertices and for any ▫$r = 3$▫. This confirms and strengthens a conjecture of Albertson. Other graph products are also considered and a refinement of the Russell and Sundaram motion lemma is proved.

Keywords

matematika;teorija grafov;razlikovalno število;grafovski avtomorfizem;produkti grafov;mathematics;graph theory;distingushing number;graph automorphism;products of graphs;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UM FNM - Faculty of Natural Sciences and Mathematics
UDC: 519.17:512.54
COBISS: 14130009 Link will open in a new window
ISSN: 0195-6698
Views: 36
Downloads: 23
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary keywords: matematika;teorija grafov;razlikovalno število;grafovski avtomorfizem;produkti grafov;
URN: URN:SI:UM:
Type (COBISS): Not categorized
Pages: str. 303-310
Volume: ǂVol. ǂ28
Issue: ǂno. ǂ1
Chronology: 2007
ID: 1472870