2023/08/15 by Meysam Korivand, Korivand, M., Nasrin Soltankhah +3
Computer Science · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2308.07677
openalex publication_date 2023/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph is called uniquely distinguishing colorable if there is only one partition of vertices of the graph that forms distinguishing coloring with the smallest possible colors. In this paper, we study the unique colorability of the distinguishing coloring of a graph and its applications in computing the distinguishing chromatic number of disconnected graphs. We introduce two families of uniquely distinguishing colorable graphs, namely type 1 and type 2, and show that every disconnected uniquely distinguishing colorable graph is the union of two isomorphic graphs of type 2. We obtain some results on bipartite uniquely distinguishing colorable graphs and show that any uniquely distinguishing n-colorable tree with n ≥ 3 is a star graph. For a connected graph G, we prove that χD(G∪ G)=χD(G)+1 if and only if G is uniquely distinguishing colorable of type 1. Also, 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. Moreover, we determine all graphs G of order n with the property that χD(G∪ G) = χD(G)+1 = ℓ, where ℓ=n-1, n, n+1. Finally, we investigate the family of connected graphs G with χD(G∪ G) = χD(G)+1 = 3.