Distinguishing infite graphs

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

Abstract

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$▫.

Keywords

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

Data

Language:	English
Year of publishing:	2007
Typology:	1.01 - Original Scientific Article
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	Electronic Journal of Combinatorics
UDC:	519.17
COBISS:	14287193
ISSN:	1077-8926
Views:	23
Downloads:	16
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Razlikovanje neskončnih grafov
Secondary abstract:	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$▫.
Secondary keywords:	matematika;teorija grafov;razlikovalno število;avtomorfizem;neskončni grafi;slučajni graf;kartezični produkt grafov;kardinalna števila;ordinalna števila;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	R36 (12 str.)
Volume:	ǂVol. ǂ14
Issue:	ǂno. ǂ1
Chronology:	2007
ID:	1473064