Distinguishing infite graphs

Wilfried Imrich (Avtor), Sandi Klavžar (Avtor), Vladimir Ivanovič Trofimov (Avtor)

Povzetek

Razlikovalno število, ▫$D(G)$▫, grafa ▫$G$▫, je najmanjše kardinalno število ▫$\aleph$▫, tako da ▫$G$▫ premore označitev z ▫$\aleph$▫ oznakami, ki jo ohranja samo trivialni avtomorfizem. Dokažemo, da je razlikovalno število števnega slučajnega grafa enako dva in da imajo drevesom podobni grafi z ne več kot kontinuum vozlišči razlikovalno število enako dva. Določimo tudi razlikovalno število za mnoge razrede neskončnih kartezičnih produktov. Na primer, ▫$D(Q_n) = 2$▫, kjer je ▫$Q_n$▫ neskončna hiperkocka dimenzije ▫$n$▫.

Ključne besede

matematika;teorija grafov;razlikovalno število;avtomorfizem;neskončni grafi;slučajni graf;kartezični produkt grafov;kardinalna števila;ordinalna števila;mathematics;graph theory;distinguishing number;automorphism;infinite graphs;random graph;Cartesian product of graphs;ordinal numbers;cardinal numbers;

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
COBISS:	14287193
ISSN:	1077-8926
Št. ogledov:	23
Št. prenosov:	16
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Razlikovanje neskončnih grafov
Sekundarni povzetek:	The distinguishing number ▫$D(G)$▫ of a graph ▫$G$▫ is the least cardinal number ▫$\aleph$▫ such that ▫$G$▫ has a labeling with ▫$\aleph$▫ labels that is only preserved by the trivial automorphism. We show that the distinguishing number of the countable random graph is two, that tree-like graphs with not more than continuum many vertices have distinguishing number two, and determine the distinguishing number of many classes of infinite Cartesian products. For instance, ▫$D(Q_n) = 2$▫, where ▫$Q_n$▫ is the infinite hypercube of dimension ▫$n$▫.
Sekundarne ključne besede:	matematika;teorija grafov;razlikovalno število;avtomorfizem;neskončni grafi;slučajni graf;kartezični produkt grafov;kardinalna števila;ordinalna števila;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	R36 (12 str.)
Letnik:	ǂVol. ǂ14
Zvezek:	ǂno. ǂ1
Čas izdaje:	2007
ID:	1473064