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;mathematics;graph theory;distinguishing number;automorphism;infinite graphs;random graph;Cartesian product of graphs;ordinal numbers;cardinal numbers;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UM FNM - Faculty of Natural Sciences and Mathematics
UDC: 519.17
COBISS: 14287193 Link will open in a new window
ISSN: 1077-8926
Views: 23
Downloads: 16
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: 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
Recommended works:
, no subtitle data available
, no subtitle data available
, no subtitle data available
, no subtitle data available