Geodesic
On computing the distinguishing numbers of trees and forests
The electronic journal of combinatorics, Tome 13 (2006)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $G$ be a graph. A vertex labeling of $G$ is distinguishing if the only label-preserving automorphism of $G$ is the identity map. The distinguishing number of $G$, $D(G)$, is the minimum number of labels needed so that $G$ has a distinguishing labeling. In this paper, we present $O(n \log n)$-time algorithms that compute the distinguishing numbers of trees and forests. Unlike most of the previous work in this area, our algorithm relies on the combinatorial properties of trees rather than their automorphism groups to compute for their distinguishing numbers.
DOI : 10.37236/1037
Classification : 05C78, 05C05, 05C85, 68R10
Mots-clés : labeling, algorithms 
@article{10_37236_1037,
     author = {Christine T. Cheng},
     title = {On computing the distinguishing numbers of trees and forests},
     journal = {The electronic journal of combinatorics},
     year = {2006},
     volume = {13},
     doi = {10.37236/1037},
     zbl = {1080.05081},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1037/}
}
TY  - JOUR
AU  - Christine T. Cheng
TI  - On computing the distinguishing numbers of trees and forests
JO  - The electronic journal of combinatorics
PY  - 2006
VL  - 13
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1037/
DO  - 10.37236/1037
ID  - 10_37236_1037
ER  - 
%0 Journal Article
%A Christine T. Cheng
%T On computing the distinguishing numbers of trees and forests
%J The electronic journal of combinatorics
%D 2006
%V 13
%U http://geodesic.mathdoc.fr/articles/10.37236/1037/
%R 10.37236/1037
%F 10_37236_1037
Christine T. Cheng. On computing the distinguishing numbers of trees and forests. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1037

Cité par Sources :