Summary: A graph is said to be \(d\)-distinguishable if there exists a \(d\)-labeling of its vertices which is only preserved by the identity map. The distinguishing number of a graph \(G\) is the smallest number \(d\) for which \(G\) is \(d\)-distinguishable. We show that the distinguishing number of trees and forests can be computed in linear time, improving the previously known \(O(n\log n)\) time algorithm.
Recommendations
- On computing the distinguishing numbers of trees and forests
- Trees with distinguishing number two
- On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach
- Distinguishability of locally finite trees
- On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results
Cited in
(9)- On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results
- A note on the asymptotic and computational complexity of graph distinguishability
- Trees with distinguishing number two
- On the Complexity of Extracting Subtree with Keeping Distinguishability
- scientific article; zbMATH DE number 3885345 (Why is no real title available?)
- On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach
- scientific article; zbMATH DE number 2080269 (Why is no real title available?)
- On computing the distinguishing numbers of trees and forests
- Identifying \(X\)-trees with few characters
This page was built for publication: Distinguishing trees in linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q426889)
