On Computing the Distinguishing Numbers of Trees and Forests
Open Access
- 7 January 2006
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 13 (1) , R11
Abstract
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.
Keywords
This publication has 6 references indexed in Scilit:
- The distinguishing number of the augmented cube and hypercube powersDiscrete Mathematics, 2008
- Distinguishing labellings of group action on vector spaces and graphsJournal of Algebra, 2006
- The distinguishing number of the direct product and wreath product actionJournal of Algebraic Combinatorics, 2006
- The Maximum Distinguishing Number of a GroupThe Electronic Journal of Combinatorics, 2006
- Distinguishing Numbers for Graphs and GroupsThe Electronic Journal of Combinatorics, 2004
- A Note on the Asymptotics and Computational Complexity of Graph DistinguishabilityThe Electronic Journal of Combinatorics, 1998