Cartesian powers of graphs can be distinguished by two labels

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Angleški jezik
Leto izida:	2007
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
UDK:	519.17:512.54
COBISS:	14130009
ISSN:	0195-6698
Št. ogledov:	36
Št. prenosov:	23
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarne ključne besede:	matematika;teorija grafov;razlikovalno število;grafovski avtomorfizem;produkti grafov;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 303-310
Letnik:	ǂVol. ǂ28
Zvezek:	ǂno. ǂ1
Čas izdaje:	2007
ID:	1472870