Abstract
Let G be a connected graph. The distinguishing number of G, denoted by D(G), is the least integer d such that G has a vertex d-labeling that is preserved only by the trivial automorphism. In this paper, we will show that given an integer d, we can find all trees of radius at most two with distinguishing number d. Moreover, we provide an algorithm to find the distinguishing labeling of any tree with radius at most two.
Full text article
References
M. O. Albertson, and K. L. Collins, Symmetry breaking in graphs, Electronic Journal of Combinatorics, 3 (1996), 1–17. https://doi.org/10.37236/1242
S. Alikhani and S. Soltani, Trees with distinguishing number two, AKCE International Journal of Graphs and Combinatorics, 16 (2019), 280–283. https://doi.org/10.1016/j.akcej.2018.02.001
B. Bogstad and L. J. Cowen, The distinguishing number of the hypercube. Discrete Mathematics, 283(1-3) (2003), 29-35. https://doi.org/10.1016/j.disc.2003.11.018
C. T. Cheng, On computing the distinguishing numbers of trees and forests, The Electronic Journal of Combinatorics, 13 (2006), R11–R11. https://doi.org/10.37236/1037
W. Imrich, S. Klavˇzar, Distinguishing Cartesian products of graphs. Journal of Graph Theory, 23(1) (2000), 117–129. https://doi.org/10.1002/jgt.20190
A. P. Rahadi, E. T. Baskoro, and S. W. Saputro, Distinguishing Number of the Generalized Theta Graph, Advances in Computer Science Research: Proceedings of the IC-MaGeStiC 2021 96, (2022) 22–25. https://doi.org/10.2991/acsr.k.220202.005
A. P. Rahadi, E. T. Baskoro, and S. W. Saputro, All Graphs of Order n with Distinguishing Number n − 1 or n − 2. Theory & Applications Of Graphs. 12(1), 3 (2025). https://doi.org/10.20429/tag.2025.120103.
Authors
Copyright (c) 2026 Journal of the Indonesian Mathematical Society
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Article Details
