Distinguishing Cartesian powers of graphs

Wilfried Imrich (Author), Sandi Klavžar (Author)

Abstract

Razlikovalno število ▫$D(G)$▫ grafa je najmanjše celo število ▫$d$▫, za katero obstaja taka ▫$d$▫-označitev točk grafa ▫$G$▫, da je ne ohranja noben avtomorfizem grafa ▫$G$▫. Dokažemo, da je razlikovalno število kvadrata in višjih potenc povezanega grafa ▫$G \ne K_2, K_3$▫, glede na kartezični produkt, vedno enako 2. Ta rezultat je močnejši od rezultatov Albertsona [Electron J Combin, 12 (2005), N17] za potence pra-grafov in tudi od rezultatov Klavžarja and Zhuja [European J. Combin, v tisku]. Bolj splošno, dokažemo tudi, da je ▫$(G \Box H) = 2$▫, če sta ▫$G$▫ in ▫$H$▫ relativno tuja grafa in je ▫$|H| \le |G| < 2^{|H|} - |H|$▫. Pod podobnimi pogoji veljajo sorodni rezultati tudi za potence grafov glede na krepki in direktni produkt grafov.

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:	2006
Typology:	1.01 - Original Scientific Article
Organization:	UM PEF - Faculty of Education
UDC:	519.17:512.54
COBISS:	14075481
ISSN:	0364-9024
Views:	42
Downloads:	23
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Razlikovanje kartezičnih potenc grafov
Secondary abstract:	The distinguishing number ▫$D(G)$▫ of a graph is the least integer ▫$d$▫ such that there is a ▫$d$▫-labeling of the vertices of ▫$G$▫ that is not preserved by any nontrivial automorphism of ▫$G$▫. We show that the distinguishing number of the square and higher powers of a connected graph ▫$G \ne K_2, K_3$▫ with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 (2005), N17] on powers of prime graphs, and results of Klavžar and Zhu [Eu J Combin, to appear]. More generally, we also prove thatd ▫$(G \Box H) = 2$▫ if ▫$G$▫ and ▫$H$▫ are relatively prime and ▫$\|H\| \le \|G\| < 2^{\|H\|} - \|H\|$▫. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product.
Secondary keywords:	matematika;teorija grafov;razlikovalno število;grafovski avtomorfizem;produkti grafov;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 250-260
Volume:	ǂVol. ǂ53
Issue:	ǂiss. ǂ3
Chronology:	2006
ID:	1472826