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: |
2007 |
Typology: |
1.01 - Original Scientific Article |
Organization: |
UM FNM - Faculty of Natural Sciences and Mathematics |
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 |