On Computing the Distinguishing Numbers of Trees and Forests

Citations Over TimeTop 10% of 2006 papers

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.

Related Papers

• → Automorphisms of normal quasi-circular domains(2013)18 cited
• → X-Inner Automorphisms, Automorphisms, and Isomorphisms of Skew Polynomial Rings(2003)2 cited
• → Representation of Groups by Means of Effect Automorphisms and Mixture Automorphisms(1983)
• → Examples of irreducible automorphisms of handlebodies(2004)
• → On tensor analogues of commuting automorphisms and central automorphisms(2019)