Uniquely proper distinguishing colorable graphs

Meysam Korivand^a , Nasrin Soltankhah^∗,^a , Kazem Khashyarmanesh^b

^aDepartment of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran ^bDepartment of Pure Mathematics, Ferdowsi University of Mashhad, P.O.Box 1159-91775, Mashhad, Iran

m.korivand@alzahra.ac.ir, soltan@alzahra.ac.ir, khashyar@ipm.ir,

* Corresponding author

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.

Keywords: uniquely distinguishing, unique coloring, symmetry breaking, UPDC.

Mathematics Subject Classification: 05C15

DOI: 10.5614/ejgta.2025.13.2.15

Received: 23 October 2023, Revised: 15 October 2025, Accepted: 28 October 2025.

1. Introduction

In 1977, a concept was introduced by Babai, which became the basis of one of the most important methods for distinguishing members of graphs by automorphism [4]. This concept, which we now know as asymmetric coloring (or distinguishing labeling), was added to the graph theory literature in 1996 by Albertson and Collins [2].

Two research subfields were followed in this concept. Experts in group theory, by taking into account that the automorphism group of graphs acts on the vertices of that graph, studied this concept in the general case when a group acts on an arbitrary set. For some outstanding achievements in this topic, we can refer to the articles [5, 6, 10, 17, 26].

Later, the distinguishing number was assigned to a graph and the proof techniques changed from the structure of automorphism group to the properties of automorphisms in graphs such as distance preservation. This fact had many advantages. In fact, we could distinguishably color graphs that we do not even know their automorphism group. Determining the automorphism group of a graph is a challenging task, and we do not want the coloring problem to depend on it. Many papers have been written in such a way. For some articles, we can refer to [1, 3, 13, 14, 25, 19, 16, 17, 20, 23, 24].

In 2006, Collins and Trenk combined this concept with proper coloring and proposed a new coloring called proper distinguishing coloring [13]. This coloring has attracted the attention of many researchers and a large number of articles have been published about it. To see some recent results related to this coloring, the reader can refer to the articles [18, 21, 22].

In [15], Harary, Hedetniemi and Robinson introduced and studied the uniquely colorable (UC, for short) graphs. In their work 'coloring' means the 'proper coloring'. The interested reader may refer to the papers [7] and [11] for further results about uniquely colorable graphs.

Details of the definitions are described as follows. Let G be a graph with vertex set V (G). A coloring of a graph G is a partition of the vertex set of G into classes, called the color classes. If a coloring contains exactly k disjoint non-empty color classes, then it is called a k-coloring. We say that a coloring with color classes V1, . . . , V^ℓ of G is a distinguishing coloring if there is no non-trivial automorphism f of G with f(Vi) = Vⁱ for all i = 1, . . . , ℓ. We denote the minimum such ℓ by D(G) and call the distinguishing number of G. A distinguishing coloring is proper distinguishing coloring if it is also a proper coloring. The distinguishing chromatic number of a graph G, denoted by χD(G), is the minimum ℓ such that {V1, . . . , Vℓ} is a proper distinguishing coloring.

If for any two proper distinguishing colorings c, c′ : V (G) −→ {1, . . . , χD(G)}, there exists a permutation α of colors such that c ′ = α ◦ c, then G is called a uniquely proper distinguishing colorable graph (UPDC, for short). In other words, a graph G is UPDC 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. The symbols for proper coloring and proper distinguishing coloring of a graph G will always represent [χ(G)] and [χD(G)], respectively. We say vertices u and v are siblings if they have a common neighbor. A fixed vertex of a graph G is a vertex that is mapped to itself by any automorphism of G. Let A, B ⊆ V (G). We say that A and B are isomorphic, if there exists an non-identity automorphism f of G such that f(A) = B. In the event of vertices x and y being adjacent (resp. non-adjacent), the notation x ∼ y (x ≁ y) is employed. We use [12] for any

Figure 1: Disconnected UPDC graphs G ∪ G with connected component G.

terminology and notation not defined here.

This paper focuses on the investigation of UPDC graphs. In Section 2, a comparison is drawn between UPDC and UC. Furthermore, definitions and illustrative examples have been provided to facilitate comprehension of the concept and to serve as a basis for the subsequent sections. The present paper establishes two primary results on UPDC graphs, which are substantiated in Sections 3 and 4. In Section 3, it is demonstrated that the only disconnected UPDC graphs are of the form G∪G, where G is an asymmetric connected bipartite graph. The result is illustrated in Figure 1 by means of a Venn diagram. In Section 4, UPDC trees are specified. It is demonstrated that the only UPDC trees are those that apply in 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. In Section 5, we characterize all graphs G of order n with the property that χD(G ∪ G) = χD(G) = k, where k = n − 2, n − 1, n. Also, 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, in Section 6, the text advances a research problem to be addressed in future studies.

2. Preliminaries

First, we provide two examples which show that the concepts of unique colorability and unique proper distinguishing colorability in a graph are different. To this end, consider the graph G in Figure 2. It is a connected bipartite graph, and so it is uniquely 2-colorable. However, it has two

proper distinguishing colorings as follows:

\[[\chi_D(G)]_1 = \{\{a, d\}, \{b, e\}, \{c\}\}, \{c\}\}, \{\chi_D(G)]_2 = \{\{a, d\}, \{c, e\}, \{b\}\}.\]

Hence it is not UPDC.

Figure 2: A UC graph G that is not UPDC.

Next, consider the graph H in Figure 3. Clearly

\[\begin{split} &[\chi(H)]_1 = \{\{a_1, a_3\}, \{a_2, a_5\}, \{a_4, a_6\}\}, \text{ and} \\ &[\chi(H)]_2 = \{\{a_1, a_6\}, \{a_3, a_4\}, \{a_2, a_5\}\} = [\chi_D(H)] \,. \end{split}\]

It is easy to see that H has the unique proper distinguishing color class [χD(H)]. Hence, H is UPDC but it is not UC.

Figure 3: A UPDC graph H that is not UC.

Definition 2.1. Let G be a graph and c¹ and c² be two vertex colorings. Then c¹ and c² are isomorphic (or equivalent) if there is an automorphism α such that for every vertex v we have c1(v) = c2(α(v)). We use c¹ ∼= c² and c¹ ≇ c² when c¹ and c² are isomorphic and non-isomorphic, respectively.

For instance, in the graph in Figure 2, [χD(G)]¹ and [χD(G)]² are equivalent.

Let G be a UPDC graph with the unique coloring [χD(G)] = {V1, V2, . . . , Vk}. Clearly, in a proper distinguishing k-coloring of G, one can assign k colors to V (G) with k! different ways. We call each of these assigning ways a labeling of the distinguishing color classes. For the sake of convenience, in the following definition, we introduce two types of graphs.

Definition 2.2. Let G be a connected graph. We say that G is of type 1 if it has only one proper distinguishing coloring up to coloring isomorphism. Otherwise, we say that G is of type 2.

For instance, the graphs in Figure 4(a) and 4(b) are UPDC of type 1 and type 2, respectively. As we see, the graph (b) has 3 different proper distinguishing colorings while the graph (a) has only one such a coloring up to coloring isomorphism.

Figure 4: UPDC graphs of type 1 and type 2.

Note that a graph of type 1 is not necessarily a UPDC graph. For example, see graph Q in Figure 5. It is easy to see that χD(Q) = 3 and a proper distinguishing coloring with 3 colors is already demonstrated in the figure. Moreover, Q is not a UPDC because we can exchange the colors of some pair of vertices and the result is not the same vertex partition, but it remains a proper distinguishing coloring: for example, make the top left vertex blue and the top right vertex green. Although Q is not a UPDC, but it has only one proper distinguishing coloring up to automorphism.

Figure 5: A graph Q of type 1 which is not a UPDC.

In the following remark, some results are derived directly from the definition.

Remark 2.3. (1) For positive integers n and m, the graphs Kn, Kn, Kn,m and P2ⁿ are UPDC. But Cⁿ (for n ≥ 5) and P2n+1 (for n ≥ 2) are not UPDC.

• (2) Let G be a UC graph and D(G) = 1. Then G is UPDC and \(\chi_D(G) = \chi(G)\).
• (3) Let G be a connected graph and \(\chi_D(G) = 2\). Then G is UPDC.

3. Disconnected graphs

In 1968, Cartwright and Harary [8] showed that the study of unique colorability is limited to connected graphs. In fact, they proved that every uniquely colorable graph is connected. In this section, we show that there exists some family of disconnected UPDC graphs, and we will specify them.

For an integer k, let \(\overset{k}{\cup} G\) denote the disjoint union of k copies of G.

Lemma 3.1. Let G be a connected graph. For a positive integer k, if \(\overset{k}{\cup} G\) is a UPDC graph, then G is UPDC.

Proof. Let \(k \geq 2\). If G is not UPDC, then it has at least two partitions of its vertices, as \([\chi_D(G)]_1\)and \([\chi_D(G)]_2\), into proper distinguishing colorings. If \([\chi_D(G)]_1\) and \([\chi_D(G)]_2\) are not isomorphic, then we can consider two components of \(\overset{k}{\cup} G\) and color each component with one of the proper distinguishing colorings of G each time. Therefore, a different partition of \(\overset{k}{\cup} G\) is achieved each time, which forms a proper distinguishing coloring. If \([\chi_D(G)]_1\) and \([\chi_D(G)]_2\) are isomorphic, then consider the proper distinguishing coloring of \(\overset{k}{\cup} G\). If both \([\chi_D(G)]_1\) and \([\chi_D(G)]_2\) are used in the proper distinguishing coloring of components of \(\overset{\kappa}{\cup} G\), we do the same as above. (Note that in this case there is a labeling of proper distinguishing color classes of \([\chi_D(G)]_1\) and \([\chi_D(G)]_2\)such that there is no color-preserving automorphism that maps \([\chi_D(G)]_1\) to \([\chi_D(G)]_2\).) Otherwise, at most one of \([\chi_D(G)]_1\) and \([\chi_D(G)]_2\) is used in the proper distinguishing coloring of components of \(\overset{k}{\cup} G\). Assume that \([\chi_D(G)]_1\) is not used in the proper distinguishing coloring of \(\overset{k}{\cup} G\). Consider an arbitrary labeling of proper distinguishing color classes of \([\chi_D(G)]_1\). There is at most one component of \(\overset{k}{\cup} G\) such that its coloring is mapped by an automorphism to the \([\chi_D(G)]_1\) with its considered labeling and preserves the labels. Replace the coloring of this component with \([\chi_D(G)]_1\)and its considered labeling. Thus we have another proper distinguishing coloring for \(\overset{\kappa}{\cup} G\). This means that \(\overset{k}{\cup} G\) has at least two proper distinguishing colorings and the result follows.

Lemma 3.2. Let G be a non-trivial connected graph. For a positive integer k, if \(\overset{k}{\cup} G\) is UPDC, then \(\chi_D(\overset{k}{\cup} G) = \chi_D(G)\).

Proof. For the sake of contradiction, assume that \(\chi_D(\overset{k}{\cup} G) > \chi_D(G)\). We claim that there exist two components of \(\overset{k}{\cup} G\) with at least one different color in the proper distinguishing coloring of \(\overset{k}{\cup} G\). For this purpose, suppose that exactly \(\chi_D(\overset{k}{\cup} G)\) colors are used in each component. Consider the coloring of one component of \(\overset{k}{\cup} G\) and replace it with the unique proper distinguishing coloring

of the graph G with \(\chi_D(G)\) colors. Therefore, we will have another proper distinguishing coloring for \(\overset{k}{\cup} G\). Now, we can select two components \(G_1\) and \(G_2\) of \(\overset{k}{\cup} G\) such that the colors used in them are not the same. Interchanging the proper distinguishing colorings of \(G_1\) and \(G_2\), gives us a new proper distinguishing coloring for \(\ddot{\cup} G\), a contradiction. Lemma 3.3. If G is connected graph of type 1, then \(\chi_D(G \cup G) = \chi_D(G) + 1\). Proof. Since G is of type 1, there is only one proper distinguishing coloring with \(\chi_D(G)\) colors up to automorphism. Hence, any proper coloring with \(\chi_D(G)\) colors cannot break symmetries that map one component of \(G \cup G\) onto the other. Therefore, another color is needed. Lemma 3.4. Let G be a non-trivial connected graph. For a positive integer k, if \(\overset{k}{\cup} G\) is a UPDC graph, then \(k \leq 2\). Proof. For the sake of contradiction, assume that \(k \geq 3\). Let \(G_1\), \(G_2\) and \(G_3\) be some components of \(\overset{\kappa}{\cup} G\). Lemmas 3.1, 3.2, conclude that the colorings of \(G_1\) and \(G_2\) are the same with a different assigned label for some color classes. There exists a color class of \([\chi_D(G)]\) that is labeled by 1 and 2 in \(G_1\) and \(G_2\), respectively. Interchanging the labels of the color classes of \(G_1\) and \(G_2\), and keeping the coloring of \(G_3\), give us another partition of vertices \(\overset{k}{\cup} G\) into a proper distinguishing coloring, a contradiction. Lemma 3.5. Let G be a connected graph. If \(G \cup G\) is UPDC, then there exists exactly two labelings of the proper distinguishing color classes of G up to automorphism. Proof. If G has only one labeling of the proper distinguishing color classes up to automorphism, then G is of type 1. So, Lemmas 3.3, 3.2 lead to a contradiction. Assume that G has more than two labelings up to automorphism. Let \(c_1\), \(c_2\) and \(c_3\) be three non-isomorphic labelings of the proper distinguishing color classes of G. Color components of \(G \cup G\) once with \(c_1\) and \(c_2\), and again with \(c_2\) and \(c_3\). We will obtain two partition of \(V(G \cup G)\) into proper distinguishing coloring, a contradiction. Lemma 3.6. Let G be a non-trivial connected graph. If \(G \cup G\) is UPDC, then \(\chi_D(G) = 2\). Proof. For a contradiction, suppose that \(\chi_D(G) \geq 3\). Thus, there exist at least 6 labelings of the proper distinguishing color classes of G. Lemma 3.5 concludes that there exist labelings \(c_1\) and \(c_2\) such that \(c_1 \ncong c_2\). Let \(c_3\) be another labeling of the proper distinguishing color classes of G. Therefore \(c_3 \cong c_1\) and so \(c_3 \ncong c_2\), a contradiction. Lemma 3.7. Let G be a non-trivial connected graph. If \(G \cup G\) is UPDC, then G is an asymmetric graph. Proof. Lemma 5.5 allows us to say G is a bipartite graph with parts V and U. So, \([\chi_D(G)] =\)\(\{V,U\}\) is the unique proper distinguishing coloring of G. If there exists a non-identity automorphism f of G, then there exist vertices \(v \in V\) and \(u \in U\) such that f(v) = u. Since the set of vertices at odd distance from v (which is U) must be mapped to the set at odd distance from f(v)

(which must now be V), f(V) = U and f(U) = V. This implies that there is only one labeling of

\([\chi_D(G)]\) up to automorphism. This is impossible because it contradicts Lemma 3.5.

Theorem 3.8. Let G be a non-empty disconnected graph. Then G is UPDC if and only if G isomorphic to H ∪ H, where H is an asymmetric connected bipartite graph.

Proof. (⇒) Let G be a disconnected UPDC graph. By Lemmas 3.1, 3.4, G has two UPDC components, say H¹ and H2. Consider a proper distinguishing coloring of G with minimum number of colors. Then H¹ and H² have at least one same color. Now suppose that H¹ ≇ H2. Since G has at least one edge, we may assume that χD(H1) ≥ 2. Thus H¹ has at least two color classes V¹ and V² in [χD(H1)]. Also, let U be a color class of H2. So we may assume that V¹ and U have a common color. Interchange the colors V¹ and V2, and produce a new partition of V (G) into proper distinguishing color classes. This is the required contradiction. Hence we have H¹ ∼= H2. Now Lemmas 5.5, 3.7 conclude that H¹ (and so H2) is an asymmetric bipartite graph.

(⇐) Since H is asymmetric connected bipartite, it has non-isomorphic parts V and U as the proper distinguishing color classes. This implies that H is of type 2 with exactly two labelings of the proper distinguishing color classes up to automorphism. Therefore, H ∪ H is UPDC.

The disconnected graph in Figure 6 is UPDC.

Figure 6: A disconnected UPDC graph.

Corollary 3.9. If G is a disconnected UPDC graph, then χD(G) = 2.

Corollary 3.10. Let G be a UPDC graph. If G is 2-regular, then G is isomorphic to C³ or C4.

4. Bipartite graphs

In this section, we study the UPDC trees. As main result of this section, we show that the only UPDC tree is a star graph, when distinguishing chromatic number is more than 2.

Lemma 4.1. Let G be a graph and x be a fixed vertex of G such that χD(G) − 1 > deg(x). Then G is not UPDC.

Proof. Let [χD(G)] = {V1, V2, . . . , V^χD(G)} be a proper distinguishing coloring of G such that N(x) has no intersection with at least two proper distinguishing color classes of G, say with V¹ and V2. Now, assume that the proper distinguishing color class of x is of cardinality one and that x ∈ V1. By replacing the color of V¹ with the color of V2, one can obtain a proper distinguishing coloring of G with less than χD(G) colors. This implies that the proper distinguishing color class

of x is of cardinality at least two. Suppose that x ∈ V¹ and that |V1| ≥ 2. Now, by replacing the color of x with the color of V2, we get another proper distinguishing color class of G. Hence G is not UPDC.

Proposition 4.2. Let G be a connected UPDC graph with a fixed pendant vertex. Then D(G) = 1 and χD(G) = 2.

Proof. By Lemma 4.1, χD(G) = 2. Hence G is bipartite. Assume that D(G) ̸= 1 and seek a contradiction. There is a non-trivial automorphism f of G such that f(v) = u, for two vertices v and u. Vertices v and u should be of the same distance from the pendant vertex. This implies that the distance between v and u must be even and so they will be in the same part in the bipartite graph G. Therefore, f preserves the unique proper distinguishing coloring and which is a contradiction.

Lemma 4.3. Let G be a UPDC graph with at least two sibling pendant vertices. Then G is a star graph.

Proof. Let a and b be sibling pendant vertices of G. Assume that G is not a star graph. Consider a proper distinguishing coloring of G. If at least one of a and b belongs to a non-singleton color class, by interchanging the colors of a and b we get another proper distinguishing color class of G, a contradiction. Suppose a and b belong to a singleton color class. Since G is not a star graph, there exists a vertex c such that a ≁ c ≁ b, and c is neither a sibling of a nor b. Now, by replacing the color of c with the color of a, we get another proper distinguishing color class of G, so we reach a contradiction.

Lemma 4.4. Let T be a tree. For two vertices v and u of T, if there exists an automorphism f of T with f(v) = u, then there exists an automorphism g of T with g(v) = u and g(u) = v.

Proof. Let v, u ∈ V (T) and f(v) = u, for an automorphism f of G. Let P be a maximal path containing v and u. There exist pendant vertices p^v and p^v that P is between them such that f(pv) = pu, where p^v and p^u are the closest endpoints of P to v and u, respectively. Considering that the length of P is odd or even, the center of P is a vertex w or an edge wz. Thus, f(w) = w or f(w) = z. If we delete w or the edge between w and z, then T has at least two isomorphic graphs H^v and Hu. Where H^v and H^u are the components that contain p^v and pu, respectively. We define the automorphism g as follows.

\[g(x) = \begin{cases} f(x), & \text{if } x \in V(H_v) \\ f^{-1}(x), & \text{if } x \in V(H_u), \\ x, & \text{if } x \in V(T) \setminus (V(H_v) \cup V(H_u)). \end{cases}\]

Therefore, g(v) = u and g(u) = v.

Let us recall the following interesting result about trees, which we shall use in the rest of the paper.

Theorem 4.5. [13, Theorem 3.1] Let T be a tree with at least 2 vertices. Then χD(T) = 2 if and only if T has no non-trivial automorphism, or the center of T is an edge xy and T has precisely one non-trivial automorphism, and this automorphism interchanges x and y.

Theorem 4.6. Let T be a UPDC tree with χD(T) ≥ 3. Then T is a star graph.

Proof. Assume that T is not a star, and seek a contradiction. Consider a proper distinguishing coloring of T with minimum number of colors. By Lemma 4.3, T cannot have sibling pendant vertices.

Now, we claim that there is at least one pendant vertex fixed by any automorphism of T which is the required contradiction. To achieve this, suppose that any given pendant vertex of T is moved by an automorphism of T. By Lemma 4.4, without loss of generality, we may assume that v and u are two pendant vertices of T mapped to each other by some automorphism of T. Consider the unique path from v to u. If the length of this path is even, then there exists a vertex, say a, in the unique path from v to u with the same distance from of v and u. Among the set of automorphisms of T which image v to u, consider an automorphism f with maximum set of fixed vertices of T. Let A denote the set of fixed vertices of T by f. Clearly A ̸= ∅, because a ∈ A. Assume that A and V (T) \ A have vertices with the same color in the proper distinguishing coloring of T. Now, consider the induced subgraph T[V (T) \ A] containing two isomorphic components. By interchanging the colors of the corresponding vertices in the two components, we get another proper distinguishing color class of T, a contradiction. This implies that the vertices in A and the vertices in V (T) \ A have different colors. Since A is non-empty, there is at least one color of vertices of A that is not assigned to any vertex of V (T) \ A. Now, we claim that, by replacing the color v (or u) with this color, one can obtain another proper distinguishing color class of T. To achieve this, it suffices to show that there is no automorphism of T that moves v (or u) which preserves the vertex colors. Assume that, by some automorphism of T which preserves the vertex colors, v (or u) is imaged to some vertex of T, say to b, and seek a contradiction. Clearly b ∈ A. Now, since T has no sibling pendant vertices, a ≁ b. Therefore, b and v (or u) have no common neighbors. Hence the neighbors of b (resp. v (or u)) that belongs to A (resp. V (T) \ A) have the same color, which is a contradiction.

Therefore the length of the unique path from v to u is odd. The general form of T is depicted in Figure 7. In Figure 7, Gⁱ ∼= Hⁱ for all i = 1, . . . , k. Thus the edge akb^k is the center of T.

Figure 7: Graph T.

Furthermore, a^k and b^k are imaged to each other by an automorphism of T, and T has only this non-trivial automorphism, otherwise, we obtain two pendant vertices with the same distance from

\(a_i\) (and \(b_i\)) for \(i=1,\ldots,k\), and so the distance between these two vertices is even, which is a contradiction. Thus Theorem 4.5 implies that \(\chi_D(T)=2\), a contradiction. So there is at least one pendant vertex fixed by any automorphism of T. Therefore, by Lemma 4.1, T is not a UPDC tree. This is a required contradiction.

M. Korivand et al.

The following corollary is immediate by Remark 2.3 and Theorems 4.5, 4.6.

Corollary 4.7. Let T be a UPDC tree. Then T 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.

5. Graphs with \(\chi_D(G \cup G) = \chi_D(G)\)

If G is a connected graph, then \(\chi_D(G \cup G) = \chi_D(G)\) or \(\chi_D(G \cup G) = \chi_D(G) + 1\). Clearly \(\chi_D(G \cup G) = \chi_D(G) + 1\) if and only if G is a connected graph of type 1. In the following, we investigate all graphs G such that \(\chi_D(G \cup G) = \chi_D(G)\), when \(\chi_D(G) = k\), for \(k \in \{|V(G)| - 2, |V(G)| - 1, |V(G)|\}\). To do this, we begin with Theorem 5.1, Theorem 5.2 and Theorem 5.3, in which all graphs of order n with distinguishing chromatic number n, n-1 and n-2 were characterized [13, 9]. We first state some necessary preliminaries.

For any graph G with vertices \((v_1,\ldots,v_n)\) and for any collection of vertex-disjoint graphs \(H_1,\ldots,H_n\), let \(G(H_1,\ldots,H_n)\) denote the graph obtained from G by replacing each \(v_i\) with a copy of \(H_i\) and replacing each edge \(v_iv_j\) by \(H_i\vee H_j\). If an \(H_i\) is vacuous, i.e., \(H_i=\emptyset\), then replacing \(v_i\) by \(\emptyset\) refers to deleting \(v_i\) and all edges incident to it. Note that the substituted H can be an independent set; i.e. both the empty set and independent sets are viewed as "complete multipartite" graphs. We present three graphs \(\hat{G}_5\), \(\hat{G}_6\) and \(\hat{G}_7\) along with a class of labelled graphs \(\mathcal{G}_3\) consisting of two non-isomorphic graphs. The labelled graphs \(\hat{G}_5\), \(\hat{G}_6\) and \(\hat{G}_7\) have vertices \((v_1,v_2,v_3,v_4)\), \((v_1,v_2,v_3,v_4,v_5)\) and \((v_1,v_2,v_3,v_4,v_5,v_6)\) respectively, while a labelled graph \(\hat{G}_3\) belonging to the class \(\mathcal{G}_3\) has vertices \((v_1,v_2,v_3,v_4,v_5)\), see Figure 6 and Figure 7. Furthermore, define \(\hat{K}_2\) and \(\hat{K}_3\) to be the labelled complete graphs of orders two and three respectively, where \(\hat{K}_2(v_1,v_2)\) has vertices \((v_1,v_2)\) and \(\hat{K}_3(v_1,v_2,v_3)\) has vertices \((v_1,v_2,v_3)\). In particular, if \(H_1\) and \(H_2\) are nonvacuous complete multipartite graphs, then \(\hat{K}_2(H_1,H_2)\) represents a complete multipartite graph with at least two parts. (For more details, see [9])

Theorem 5.1. [13, Theorem 2.3] Let G be a graph. Then \(\chi_D(G) = |V(G)|\) if and only of G is a complete multipartite graph.

Theorem 5.2. [9, Theorem 3.2] Let G be a graph of order n > 3. Then \(\chi_D(G) = n - 1\) if and only if G is the join of a complete multipartite graph (possibly vacuous) with one of the following:

• (1) \(2K_2\), or
• (2) \(H \cup K_1\), where H is a complete multipartite graph with at least two parts.

Figure 8: Graphs \(\hat{G}_5(v_1, v_2, v_3, v_4)\) and \(\hat{G}_6(v_1, v_2, v_3, v_4, v_5)\).

Figure 9: Graphs \(\hat{G}_7(v_1, v_2, v_3, v_4, v_5, v_6)\) and \(\mathcal{G}_3(v_1, v_2, v_3, v_4, v_5)\).

Theorem 5.3. [9, Theorem 3.5] Let G be a graph of order n > 4. Then \(\chi_D(G) = n - 2\) if and only if G is the join of a complete multipartite graph (possibly vacuous) with one of the following:

• (a) \(P_5\)
• (c) \(C_6\)
• (e) \(\overline{K_r} \cup K_2\), for \(r \geq 2\)
• (g) \(\hat{K}_3(H_1, H_2, H_3) \cup K_2\)
• (i) \(2K_2 \vee 2K_2\)
• (k) \(2K_2 \cup K_1\)
• (m) \(\hat{G}_3(H_1, H_2, H_3, K_1, K_1)\), for \(\hat{G}_3 \in \mathcal{G}_3\)
• (o) \(\hat{G}_5(K_1, H_1, H_2, K_1)\)
• (q) \(\hat{G}_7(H_1, H_2, H_3, H_4, K_1, K_1)\)

• (b) \(C_5\)
• (d) \(2K_2\)
• (f) \(\hat{K}_2(\overline{K_r}, H_1) \cup K_2\), for \(r \ge 2\)
• (h) \(\hat{K}_2(H_1, H_2) \cup \overline{K_2}\)
• (j) \(2K_2 \vee (\hat{K}_2(H_1, H_2) \cup K_1)\)
• (1) \((2K_2 \vee H_1) \cup K_1\)
• (n) \(\hat{G}_5(H_1, H_2, K_1, K_1)\)
• (p) \(\hat{G}_6(K_1, H_1, H_2, H_3, K_1)\)

where each of \(H_1, H_2, H_3, H_4\) is a nonvacuous complete multipartite graph.

Theorem 5.4. Let G be a graph of order n and \(\chi_D(G) = n\). Then

\[\chi_D(G \cup G) = \begin{cases} n+1, & \text{if } G \cong K_n, \\ 2n, & \text{if } G \cong \overline{K_n}, \\ n, & \text{Otherwise.} \end{cases}\]

Proof. By Theorem 5.1, G is a complete multipartite graph. The only non-trivial case is when G /∈ {Kn, Kn}. In this case, there is at least one part, say U, with cardinality more than 2. There exist at least two subsets of size |U| of {1, 2. . . . , χD(G)}. Color U with {1, 2, . . . , |U|} in a component of G ∪ G and color U in the other component with {1, 2, . . . , |U| − 1, |U| + 1}. Also, color other vertices of G ∪ G arbitrary. One can check that this is a distinguishing χD(G)-coloring for G ∪ G.

Lemma 5.5. Let G be the join of a nonvacuous complete multipartite graph with one of graphs (1) and (2) in Theorem 5.2 or one of graphs (a) - (q) in Theorem 5.3. Then χD(G ∪ G) = χD(G).

Proof. Let H be a nonvacuous complete multipartite graph and K be one of graphs (1) and (2) in Theorem 5.2 or one of graphs (a) - (q) in Theorem 5.3. Let Gⁱ , Hⁱ and Kⁱ denote the graphs isomorphic to G, H and K respectively, for i = 1, 2. We claim that if f is an automorphism with f(G1) = G2, then f(H1) = H2. For this, assume that all parts of H have cardinality more than one. On the other hand, all vertices of K adjacent to all vertices of H in G. This implies that we cannot replace some vertices of H with some vertices of K such that the structure of H is preserved. (Note that K is not a complete multipartite graph.) If H has a part {x}, then a necessary condition for that we can replace {x} with a vertex of K such that the structure of H is preserved, is that there exist a vertex y ∈ V (K) with degK(x) = |V (K)| − 1. One can check there is no such x in graphs (1) and (2) in Theorem 5.2 and graphs (a) - (q) in Theorem 5.3.

There exist two vertices with the same color in G. Assume that color 1 is assigned to two vertices in G¹ and color 2 is assigned to a vertex in H1. The vertices colored by 1 are in K1. Now, color the vertices of G² with the coloring of G¹ by interchanging colors 1 and 2. Therefore, any automorphism that maps G¹ to G² does not preserve the colors.

Theorem 5.6. Let G be a graph of order n > 3 with χD(G) = n − 1. Then

• (a) χD(G ∪ G) = χD(G) if and only if
  • (a1) G is the join of a nonvacuous complete multipartite graph with one of the following:
    • (a11) 2K2, or,
    • (a12) H ∪ K1.
  • (a2) G ∼= H ∪ K1, H ≇ Kn−1,

where H is a complete multipartite graph with at least two parts.

• (b) χD(G ∪ G) = χD(G) + 1 if and only if G is one of the following:
  • (b1) 2K²
  • (b2) Kn−¹ ∪ K1.

Proof. According to Theorem 5.2, assume first that G is the join of a nonvacuous complete multipartite graph with one of the graphs 2K² or H ∪ K1. Lemma 5.5 concludes the results in (a1). For (b1), let G = 2K2. Hence, χD(G ∪ G) = χD(4K2) = 4 = χD(G) + 1 and the result follows. Let G = H ∪ K1. Since H is a complete multipartite graph with at least two parts, H ≇ Kn−1. Now, the results in (b2) and (a2) conclude from Theorem 5.4.

Theorem 5.7. Let G be a graph of order n > 4 with χD(G) = n − 2. Then

• (a) χD(G ∪ G) = χD(G) if and only if
  • (a1) G is the join of a nonvacuous complete multipartite graph with one of the following:

(a2) G is one of the following:

(a21) P5
(a23) C6
(a25) 2K2 ∨ 2K2
(a27) (2K2 ∨ H1) ∪ K1
(a29) Gˆ
         7(H1, H2, H3, H4, K1, K1)
(a211) Gˆ
         6(K1, H1, H2, H3, K1)
                                             (a22) C5
                                             (a24) 2K3
                                             (a26) Kˆ
                                                     2(Kr, H1) ∪ K2, for r ≥ 2
                                             (a28) 2K2 ∨ (Kˆ
                                                             2(H1, H2) ∪ K1)
                                            (a210) Gˆ
                                                     3(H1, H2, H3, K1, K1), for Gˆ
                                                                                  3 ∈G3
(a212) Kˆ
         3(H1, H2, H3) ∪ K2, where Kˆ
                                       3(H1, H2, H3) is not a complete graph.
(a213) Kˆ
         2(H1, H2) ∪ K2, where Kˆ
                                  2(H1, H2) is not a complete graph and |Kˆ
                                                                           2(H1, H2)| ≥ 4.
(a214) Gˆ
         5(H1, H2, K1, K1), where H1 ̸= K1 or H2 ̸= K1.
(a215) Gˆ
         5(K1, H1, H2, K1), where H1 ̸= K1 or H2 ̸= K1.

where each of H1, H2, H3, H⁴ is a nonvacuous complete multipartite graph.

• (b) χD(G ∪ G) = χD(G) + 1 if and only if G is one of the following:
  • (b1) Kn−² ∪ K² (b2) K ∪ K2, K ∈ {P3, K3}. (b3) 2K² ∪ K¹ (b4) P⁴
• (c) χD(G ∪ G) = χD(G) + 2 if and only if G ∼= K² ∪ K2.
• (d) χD(G ∪ G) = 2χD(G) if and only if G ∼= K^r ∪ K2, for r ≥ 2.

Proof. The graph G is the join of a complete multipartite graph (possibly vacuous) with one of the graphs presented in Theorem 5.3. If G is the join of a nonvacuous complete multipartite graph with one of the graphs (a) - (q) presented in Theorem 5.3, then by Lemma 5.5, we have the results in (a1). Now, let G be one of the graphs (a) - (q) that are presented in Theorem 5.3. In some

• cases with \(\chi_D(G \cup G) = \chi_D(G)\), we will select distinct vertices \(v_1, v_2, v_3, v_4\) of each component of \(G \cup G\) for a coloring of \(G \cup G\) such that all vertices other than \(v_1, v_2, v_3, v_4\) receive distinct colors in G. Assign to \(v_1\) and \(v_2\) one color and to \(v_3\) and \(v_4\) another color in each component of \(G \cup G\).
• \((a_{21})\), \((a_{22})\) In these cases, there is a singleton color class in each distinguishing coloring. Asign color 1 and color 2 to the singleton color classes in each component.
  • \((a_{23})\) Assign color 1 to \(v_1\) and \(v_2\) and color 2 to \(v_3\) and \(v_4\) in a component. Also, assign color 3 to \(v_1\) and \(v_2\) and color 2 to \(v_3\) and \(v_4\) in the other component.
  • \((a_{24})\) In this case, we have four triangles \(K_3\). The vertices \(v_1\) and \(v_3\) are in a triangle in G and the vertices \(v_2\) and \(v_4\) are in the other triangle. Assign color 1 to \(v_1\) and \(v_2\), color 2 to \(v_3\) and \(v_4\) and renaming vertices are colored by colors 3 and 4 in a copy of G. For the other copy, assign color 3 to \(v_1\) and \(v_2\), color 4 to \(v_3\) and \(v_4\) and renaming vertices are colored by colors 1 and 2.
  • \((a_{25})\) In \(2K_2 \vee 2K_2\), let the vertices \(v_1\) and \(v_2\) be in a copy \(2K_2\) in \(2K_2 \vee 2K_2\) and the vertices \(v_3\) and \(v_4\) be in the other copy. Assign color 1 to \(v_1\) and \(v_2\) and color 2 to \(v_3\) and \(v_4\) in a component of \(G \cup G\). For the other component, assign color 3 to \(v_1\) and \(v_2\) and color 4 to \(v_3\) and \(v_4\).
  • (\(a_{26}\)) Since \(r \geq 2\), \(\hat{K}_2(\overline{K}_r, H_1) \ncong K_{n-2}\), \(\overline{K}_{n-2}\) and \(|\hat{K}_2(\overline{K}_r, H_1)| \geq 3\). Let \(v_1 \in V(H_1)\), \(v_2, v_3 \in V(K_2)\) and \(v_4 \in V(\overline{K}_r)\) in a copy of G. Assign color 1 to \(v_1\) and \(v_2\), color 2 to \(v_3\) and \(v_4\) and color 3 to an other vertex of \(\overline{K}_r\). For the other copy, let \(v_2, v_3 \in V(K_2)\) and \(v_1, v_4 \in V(\overline{K}_r)\). Assign color 1 to \(v_1\) and \(v_2\) and color 3 to \(v_3\) and \(v_4\).
• \((a_{27})\), \((a_{28})\) In both copies of \(G \cup G\), let \(v_1, v_2 \in V(2K_2)\), \(v_3 \in V(K_1)\) and \(v_4 \in V(\hat{K}_2(H_1, H_2))\) \((v_4 \in V(H_1))\). Assign color 1 to \(v_1\) and \(v_2\) and color 2 to \(v_3\) and \(v_4\) in a copy. For the other copy, assign color 2 to \(v_1\) and \(v_2\) and color 1 to \(v_3\) and \(v_4\).
  • (a₂₉) Let \(v_1 \in V(K_1) = \{v_5\}, v_3 \in V(K_1) = \{v_6\}, v_4 \in V(H_4) \text{ and } v_2 \in V(H_1) \text{ in the both components of } G \cup G.\) Assign color 1 to \(v_1\) and \(v_2\) and color 2 to \(v_3\) and \(v_4\), in a component. For the other component, assign color 3 to \(v_1\) and \(v_2\) and color 4 to \(v_3\) and \(v_4\).
  • \((a_{210})\) In both copies of \(G \cup G\), let \(v_1 \in V(K_1) = \{v_4\}, v_3 \in V(K_1) = \{v_5\}, v_2 \in V(H_3)\) and \(v_4 \in V(H_2)\). Assign color 1 to \(v_1\) and \(v_2\) and color 2 to \(v_3\) and \(v_4\), in a component. For the other component, assign color 1 to \(v_1\) and \(v_2\) and color 3 to \(v_3\) and \(v_4\).
  • (\(a_{211}\)) Let \(v_1 \in V(K_1) = \{v_1\}, v_3 \in V(K_1) = \{v_5\}, v_2 \in V(H_2)\) and \(v_4 \in V(H_1)\), in the both components of \(G \cup G\). Assign color 1 to \(v_1\) and \(v_2\) and color 2 to \(v_3\) and \(v_4\), in a component. For the other component, assign color 2 to \(v_1\) and \(v_2\) and color 1 to \(v_3\) and \(v_4\).
• \((a_{212}), (b_1)\) Let \(G = \hat{K}_3(H_1, H_2, H_3) \cup K_2\). If \(\hat{K}_3(H_1, H_2, H_3)\) is a complete graph, then \(\hat{K}_3(H_1, H_2, H_3) \cup \hat{K}_3(H_1, H_2, H_3)\) is not distinguished by \(\chi_D(G)\) colors. In this case, one can check that \(\chi_D(G \cup G) = \chi_D(G) + 1\). If \(\hat{K}_3(H_1, H_2, H_3)\) is not a complete graph, by Theorem 5.4, the result in \((a_{212})\) is immediate.

• \((a_{213}), (b_2), (c)\) Let \(G = \hat{K}_2(H_1, H_2) \cup \overline{K_2}\). If \(|\hat{K}_2(H_1, H_2)| \leq 3\), then for distinguishing the vertices \(\overline{K_4}\) in \(G \cup G\), we need at least 4 colors. For result in (c), let \(|\hat{K}_2(H_1, H_2)| = 2\). Then \(\hat{K}_2(H_1, H_2)\) is isomorphic with \(K_2\) and \(\chi_D(G) = 2\). If \(|\hat{K}_2(H_1, H_2)| = 3\), then \(\hat{K}_2(H_1, H_2)\) is isomorphic with \(K_3\) or \(P_3\). In both cases, \(\chi_D(G \cup G) = \chi_D(G) + 1\). If \(|\hat{K}_2(H_1, H_2)| \geq 4\) and \(\hat{K}_2(H_1, H_2)\) is a complete graph by Theorem 5.4, then \(\chi_D(G \cup G) = \chi_D(G) + 1\) and the result in \((b_2)\) is obtained. Otherwise, we have the results in \((a_{213})\).
  • \((a_{214}), (b_4)\) In this case, if \(H_1 = H_2 = K_1\), then \(\hat{G}_5(H_1, H_2, K_1, K_1) = P_4\) and clearly \(\chi_D(G \cup G) = \chi_D(G) + 1\). This is the result in \((b_4)\). If \(H_1 \neq K_1\) or \(H_2 \neq K_1\), let \(v_1 \in V(K_1) = \{v_3\}, v_3 \in V(K_1) = \{v_4\}, v_2 \in V(H_1)\) and \(v_4 \in V(H_2)\) in both components of \(G \cup G\). Assign color 1 to \(v_1\) and \(v_2\) and color 2 to \(v_3\) and \(v_4\) in a component. For the other component, assign color 2 to \(v_1\) and \(v_2\) and color 1 to \(v_3\) and \(v_4\).
  • \((a_{215}), (b_4)\) Similarly to the case \((a_{214}), (b_4)\), if \(H_1 = H_2 = K_1\), then we have the result in \((b_4)\). So, let \(H_1 \neq K_1\) or \(H_2 \neq K_1\). For both components of \(G \cup G\), let \(v_1 \in V(K_1) = \{v_1\}, v_3 \in V(K_1) = \{v_4\}, v_2 \in V(H_2)\) and \(v_4 \in V(H_1)\). Assign color 1 to \(v_1\) and \(v_2\) and color 2 to \(v_3\) and \(v_4\) in a component. For the other component, assign color 2 to \(v_1\) and \(v_2\) and color 3 to \(v_3\) and \(v_4\).
    • \((b_3)\) In this case, there are four copies of \(K_2\) in \(G \cup G\). For distinguishing those copies, we need four colors. Also the copies \(K_1\) are colored by the colors used in \(K_2\). Hence, \(\chi_D(G \cup G) = n 1 = \chi_D(G) + 1\).
    • (d) Since \(G \cup G = \overline{K_{2r}} \cup 2K_2\) and \(r \ge 2\), we can color the vertices of \(2K_2\) by the colors used in \(\overline{K_{2r}}\). So, \(\chi_D(G \cup G) = \chi_D(\overline{K_{2r}}) = 2r\).

6. Conclusions and Future Research

The study of the number of colorings of a graph has been a subject of interest in the literature on graph colorings. Meanwhile, the study of graphs that have only one coloring is of particular importance. In this paper, the focus is on graphs that have only one proper distinguishing coloring. As the two main results of this paper, the disconnected UPDC graphs and UPDC trees has been determined. The concept of the UPDC has considerable potential for further study in certain graph families. We end the paper with the following problem.

Problem 6.1. Find the family of connected graphs that are UPDC or not.

Acknowledgments

Two first authors have been supported by the Discrete Mathematics 439 Laboratory of the Faculty of Mathematical Sciences at Alzahra University.

Declarations

Conflict of interest The authors have no relevant financial or non-financial interests to disclose.

Data availability

Our manuscript has no associated data.

References

• [1] B. Ahmadi, F. Alinaghipour, and M.H. Shekarriz, Number of distinguishing colorings and partitions, Discrete Math. 343(9) (2020), 111984.
• [2] M.O. Albertson and K.L. Collins, Symmetry Breaking in Graphs, Electron. J. Combin. 3(1) (1996), #R18.
• [3] S. Alikhani and S. Soltani, Distinguishing index of Kronecker product of two graphs, Electron. J. Graph Theory Appl. 9(1) (2021), 77–85.
• [4] L. Babai. Asymmetric trees with two prescribed degrees, Acta Math. Hung., 29(1–2) (1977), 193–200.
• [5] L. Babai, Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's Conjecture confirmed, J. Algebra 607 (2022), 64–106.
• [6] R. F. Bailey and P. J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bull. Lond. Math. Soc. 43(2) (2011), 209–242.
• [7] B. Bollob´as and N. Sauer, Uniquely colorable graphs with large girth, Canad. J. Math. 28 (1976), 1340–1344.
• [8] D. Cartwright and F. Harary, On the coloring of signed graphs, Elem. Math. 23 (1968), 85–89.
• [9] M. Cavers and K. Seyffarth, Graphs with large distinguishing chromatic number, Electron. J. Combin. 20(1) (2013), #P19.
• [10] M, Chan, The distinguishing number of the direct product and wreath product action, J. Algebraic Combin. 24, (2006), 331–345.
• [11] C.Y. Chao and Z. Chen, On uniquely 3-colorable graphs, Discrete Math., 112 (1993), 21– 27.
• [12] G. Chartrand and P. Zhang, Chromatic Graph Theory, Chapman & Hall/CRC Press, Boca Raton, FL, 2009.
• [13] K.L. Collins and A.N. Trenk, The Distinguishing Chromatic Number, Electron. J. Combin. 13 (2006), #R16.

• [14] K.L. Collins and A.N. Trenk, The Distinguishing Number and Distinguishing Chromatic Number for Posets, Order 39 (2022), 361–380.
• [15] F. Harary, S.T. Hedetniemi, and R.W. Robinson, Uniquely colorable graphs, J. Combin. Theory 6 (1969), 264–270.
• [16] W. Imrich and S. Klavzar, Distinguishing Cartesian powers of graphs, ˇ J. Graph Theory 53 (2006), 250–260.
• [17] S. Klavzar, T.L. Wong, and X. Zhu, Distinguishing labellings of group action on vector ˇ spaces and graphs, J. Algebra 303 (2006), 626–641.
• [18] R. Kalinowski and M. Pilsniak, Proper distinguishing arc-colourings of symmetric di- ´ graphs, Appl. Math. Comput. 421 (2022).
• [19] R. Kalinowski, M. Pilsniak and M. Prorok, Distinguishing arc-colourings of symmetric ´ digraphs, Art Discrete Appl. Math. 6 (2023), #P2.04.
• [20] M. Korivand, D.A. Mojdeh, E.T. Baskoro, and A. Erfanian, Edge-locating coloring of graphs, Electron. J. Graph Theory Appl. 12(1) (2024), 55–73.
• [21] F. Lehner, M. Pilsniak, and M. Stawiski, Distinguishing infinite graphs with bounded de- ´ grees, J. Graph Theory 101(1) (2022), 52–65.
• [22] K. Meslem and E. Sopena, Distinguishing numbers and distinguishing indices of oriented graphs, Discrete Appl. Math. 285 (2020), 330–342.
• [23] A. Russell and R. Sundaram, A note on the asymptotics and computational complexity of graph distinguish-ability, Electron. J. Combin. 5 (1998), #R23.
• [24] M.H. Shekarriz, B. Ahmadi, S.A. Talebpour and M. H. Shirdareh Haghighi, Distinguishing threshold of graphs, J. Graph Theory, 103(2) (2023), 359–377.
• [25] T.W. Tucker, Distinguishing maps, Electron. J. Combin. 18(1) (2011), #P50.
• [26] J. Tymoczko, Distinguishing numbers for graphs and groups, Electron. J. Combin. 11(1) (2004), #R63.