On computing the distinguishing numbers of trees and forests

MaRDI QIDQ813439zbMATH OpenFDO

Authors Christine T. Cheng

Publication date 9 February 2006

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/125525, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r11.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

algorithmslabeling

Mathematics Subject Classification ID

Trees (05C05) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

Summary: 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.

Recommendations

• Distinguishing trees in linear time
• On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach
• Trees with distinguishing number two
• On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results
• Distinguishability of locally finite trees

Cited in

(30)

• 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
• Extending precolorings to distinguish group actions
• On the distinguishing number of cyclic tournaments: towards the Albertson-Collins conjecture
• Equitable distinguishing chromatic number
• Trees with distinguishing index equal distinguishing number plus one
• Trees with distinguishing number two
• On the local distinguishing chromatic number
• On the distinguishing number of functigraphs
• List-distinguishing Cartesian products of cliques
• The distinguishing number of Cartesian products of complete graphs
• The distinguishing number of the augmented cube and hypercube powers
• Distinguishing number of hierarchical products of graphs
• scientific article; zbMATH DE number 2186866 (Why is no real title available?)
• Generation of Colourings and Distinguishing Colourings of Graphs
• On upper bound of vertex distinguishing word length on vertex labeled graph
• On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach
• Distinguishing trees in linear time
• A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
• Distinguishing graphs by edge-colourings
• ‎Distinguishing index of Kronecker product of two graphs
• The list distinguishing number equals the distinguishing number for interval graphs
• scientific article; zbMATH DE number 971754 (Why is no real title available?)
• A combinatorial approach to Golomb forests
• On the graphs with distinguishing number equal list distinguishing number
• Computing some Laplacian coefficients of forests
• On the distinguishing chromatic number of the Kronecker products of graphs
• Tyshkevich's graph decomposition and the distinguishing numbers of unigraphs
• Distinguishing chromatic number of the hierarchical product of graphs
• The distinguishing chromatic number of Cartesian products of two complete graphs

This page was built for publication: On computing the distinguishing numbers of trees and forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q813439)