Uniquely proper distinguishing colorable graphs - Korivand, Meysam; Soltankhah, Nasrin; Khashyarmanesh, Kazem (Electronic Journal of Graph Theory and Applications (EJGTA), 2025)
A proper vertex-coloring of a graph G is called distinguishing, if the only automorphism preserving the colors is the identity. The minimum number of colors for such a coloring is denoted by χD(G). We say a graph G is uniquely proper distinguishing colorable (UPDC, for short) if and only if there exists only one partition of V(G) into χD(G) independent sets such that the identity is the only automorphism of G preserving the partition.In this paper, we study the UPDC graphs. We show that a disconnected graph is UPDC if and only if it is the union of two isomorphic asymmetric connected bipartite graphs. We prove some results on bipartite UPDC graphs and show that any UPDC tree is one of the following: (i) an asymmetric tree, (ii) a tree with precisely one non-trivial automorphism and center xy such that this automorphism interchanges x and y, (iii) a star graph. Additional, a characterization of all graphs G of order n with the property that χD(G∪G) = χD(G) = k, where k=n-2, n-1, n, is given in this paper. Finally, we determine all graphs G of order n with the property that χD(G∪G) = χD(G)+1 = ℓ, where ℓ=n-1, n, n+1.