Geodesic
Distinguishing infinite graphs
The electronic journal of combinatorics, Tome 14 (2007)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
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}$.
DOI : 10.37236/954
Classification : 05C25, 05C80, 03E10
Mots-clés : labeling, automorphism, countable random graph 
Wilfried Imrich; Sandi Klavžar; Vladimir Trofimov. Distinguishing infinite graphs. The electronic journal of combinatorics, Tome 14 (2007). doi: 10.37236/954
@article{10_37236_954,
     author = {Wilfried Imrich and Sandi Klav\v{z}ar and Vladimir Trofimov},
     title = {Distinguishing infinite graphs},
     journal = {The electronic journal of combinatorics},
     year = {2007},
     volume = {14},
     doi = {10.37236/954},
     zbl = {1124.05044},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/954/}
}
TY  - JOUR
AU  - Wilfried Imrich
AU  - Sandi Klavžar
AU  - Vladimir Trofimov
TI  - Distinguishing infinite graphs
JO  - The electronic journal of combinatorics
PY  - 2007
VL  - 14
UR  - http://geodesic.mathdoc.fr/articles/10.37236/954/
DO  - 10.37236/954
ID  - 10_37236_954
ER  - 
%0 Journal Article
%A Wilfried Imrich
%A Sandi Klavžar
%A Vladimir Trofimov
%T Distinguishing infinite graphs
%J The electronic journal of combinatorics
%D 2007
%V 14
%U http://geodesic.mathdoc.fr/articles/10.37236/954/
%R 10.37236/954
%F 10_37236_954

Cité par Sources :