Uniquely Distinguishing Colorable Graphs

M. Korivand^1, N. Soltankhah^1,Corresponding author , and K. Khashyarmanesh^2

$^{1}$ Department of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran
e-mail<EMAIL_ADDRESS>or<EMAIL_ADDRESS><EMAIL_ADDRESS>
$^{2}$ Department of Pure Mathematics, Ferdowsi University of Mashhad,

P.O.Box 1159-91775, Mashhad, Iran.

e-mail<EMAIL_ADDRESS>
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 \geq 3$ is a star graph.
For a connected graph
we prove that
$\chi_D(G\cup G)=\chi_D(G)+1$
if and only if
is uniquely distinguishing colorable of type 1.
Also, a characterization of all graphs
$G$ of order $n$ with the property that $\chi_{D}(G\cup G) = \chi_{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 $\chi_{D}(G\cup G) = \chi_{D}(G)+1 = \ell$, where $\ell=n-1, n, n+1$.
Finally, we investigate the family of connected graphs $G$ with $\chi_{D}(G\cup G) = \chi_{D}(G)+1 = 3$.

Key words: Uniquely colorable graph, Distinguishing colorable graph, Automorphism of graph.

AMS Subj. Class: 05C15.

§ INTRODUCTION

In 1977, a concept was introduced by Babaei, which became the basis of one of the most important methods for partitioning and distinguishing members of graphs
by automorphism [3]. 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], motivated by the following problem:

Professor X, who is blind, keeps keys on a circular key ring. Suppose there are a variety of handle shapes available that can be distinguished by touch. Assume that all keys are symmetrical so that a rotation of the key ring about an axis in its plane is undetectable from an examination of a single key. How many shapes does Professor X need to use in order to keep $n$ keys on the ring and still be able to select the proper key by feel?

In the language of graph theory, this problem is
connected with the minimum number of colors needed to color the vertices of a
cycle graph such that there is a non-identity automorphism of the graph which preserves
all the vertices label. This topic has attracted a lot of attention.
Google Scholar lists more than 340 citations to the papers of Albertson and Collins 1996 on “Symmetry Breaking in Graphs".
First, this concept was completely brought up in the field of group theory.
So, the distinguishing number was computed for the automorphism group of graphs instead of the graphs,
and the proof techniques were in the field of group theory.
But the research path changed quickly and the graph theory researchers took up the topic.

However, 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 [4, 5, 9, 17, 25].

Later, the distinguishing number was assigned to a graph and the proof techniques changed from the structure of automorphism group to the properties of automorphism in graphs such as distance preservation.
This event had many advantages. In fact, we could color graphs that we do not even know their automorphism group. Because determining the automorphism group of a graph is a difficult problem and we are not interested in making the coloring problem dependent on it.
Many papers have been written in such a way. For some interesting articles, we can refer to [1, 12, 13, 24, 19, 16, 17, 22, 23].

In 2006, Collins and Trenk combined this concept with proper coloring and proposed a new coloring called proper distinguishing coloring (or distinguishing coloring) [12].
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, 20, 21].

In [15], Harary, Hedetniemi and Robinson introduced and studied the uniquely colorable graphs. In their  work  `coloring' means the  `proper coloring'. The interested reader may refer to the papers [6] and [10] for further  results about uniquely colorable graphs.

Details of the definitions are described as follows. All graphs considered in this paper are simple. Let $G$ be a graph with vertex set $V(G)$.
A coloring (or labeling) of a graph $ G $ is a partition of the vertex set of $G$ into classes,
called the color classes. If a coloring contains exactly $n$ disjoint non-empty color classes, then it is called an $n$-coloring.
The symbol of distinguishing labeling  of
$ G $  will always be denoted by $ \left[  D(G) \right]$.
We say that a coloring $[D(G)]$ with color classes $V_1, \ldots, V_{\ell}$ of $G$ is  distinguishing labeling if
there is no non-trivial automorphism $f$ of $G$ with $f(V_i)=V_i$ for all $i=1, \ldots, \ell$. We denote the minimum  such $\ell$ by $D(G)$ and is called distinguish number of $G$.  A distinguishing labeling  $[D(G)]$ is distinguishing coloring (or proper distinguishing coloring) if it provides a proper coloring for $G$.
The distinguishing chromatic number of a graph $G$,  denoted by $ \chi_{D}(G) $,  is the minimum $\ell$ such that
$[D(G)]=\{V_1, \ldots, V_{\ell} \}$ is a distinguishing coloring.

Recall that a graph which has a proper $k$-coloring with no proper $(k - 1)$-coloring is $k$-chromatic.
We say that a graph is uniquely distinguishing $ n $-colorable if it has exactly one distinguishing $n$-coloring.
Furthermore,  we say  a graph is uniquely distinguishing colorable if there is only one partition of its vertex set
into the smallest possible number of distinguishing color classes.
Actually a uniquely distinguishing colorable graph is a uniquely distinguishing $\chi_{D}(G)$-colorable. The symbols  of  proper coloring  and distinguishing coloring of
$ G $  will always denote $ \left[  \chi (G) \right]$  and  $ \left[  \chi_{D}(G) \right]$, respectively. We say vertices $ u $ and $ v $ are siblings if they have a common neighbor.
Finally, a fixed vertex of a graph $G$ is a vertex that is mapped to itself by any automorphism of $G$.
We use [11] for any terminology and notation not defined here.

In this paper, we show that the study and classification of uniquely distinguishing colorable (UDC for short) graphs help to calculate the distinguishing chromatic number of disconnected graphs.
In Section 2, we show that  the concepts of unique colorability and unique distinguishing colorability in a graph are different. However, these two concepts are not unrelated. We have determined the unique colorability of the distinguishing coloring for some known graphs.
In Section 3, we define two types of uniquely distinguishing colorable graphs, named type 1 and type 2, and prove that
if $ G $ is a non-empty uniquely distinguishing colorable graph, then $ G $ is connected or isomorphic to the union of two isomorphic graphs of type 2.
In Section 4, we study the properties and classification of uniquely distinguishing colorable bipartite graphs and specifically trees.
Moreover,  we show that any uniquely distinguishing $n$-colorable tree with $ n \geq 3$ is a star graph.
In Section 5, we prove that if
is a connected graph, then
$\chi_D(G\cup G)=\chi_D(G)+1$
if and only if
is uniquely distinguishing colorable of type 1.
In this section, we investigate the family of connected graphs $G$ that $\chi_{D}(G\cup G) = \chi_{D}(G)+1 = 3$.
Moreover, we characterize all graphs
$G$ of order $n$ with property that $\chi_{D}(G\cup G) = \chi_{D}(G) = k$, where $k=n-2, n-1, n$.
Also, we determine all graphs
$G$ of order $n$ with the property that $\chi_{D}(G\cup G) = \chi_{D}(G)+1 = \ell$, where $\ell=n-1, n, n+1$.
The results obtained for connected graphs are given above in the form of a Venn diagram.

§ GENERAL RESULTS

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

\begin{align*}
[\chi_{D}(G)]_{1} &= \{ \{a, d \}, \{b, e\}, \{c\} \},  \\
[ \chi_{D}(G)]_{2}&= \{ \{a, d \}, \{c, e\}, \{b\} \}.
\end{align*}

Hence it is not uniquely distinguishing colorable.

[scale=.8, thick, vertex/.style=scale=.5, ball color=black, circle, text=white, minimum size=.2mm,
Ledge/.style=to path=
.. controls +(45:2) and +(135:2) .. ()
[label=[label distance=.1cm]180:$a$] (a1) at (180:1) [vertex] ;
[label=[label distance=.1cm]90:$b$] (a2) at (90:1) [vertex] ;
[label=[label distance=.1cm]90:$d$] (a3) at (0:1) [vertex] ;
[label=[label distance=.1cm]-90:$c$] (a4) at (-90:1) [vertex] ;
[label=[label distance=.1cm]90:$e$] (a5) at (0:2.4) [vertex] ;
(a1) to(a2) to (a3) to (a4) to (a1) ;
(a3) to (a5);

A uniquely colorable graph $G$ that is not uniquely distinguishing colorable.

Next, consider the graph $H$ in Figure 2. Clearly

\begin{align*}
\left[  \chi(H) \right]_{1} &= \{ \{a_{1}, a_{3} \}, \{a_{2}, a_{5}\}, \{a_{4}, a_{6}\} \}, \ \T{and} \\
\left[  \chi(H) \right]_{2} &=  \{ \{a_{1}, a_{6} \}, \{a_{3}, a_{4}\}, \{a_{2}, a_{5}\} \} = \left[  \chi_{D}(H) \right].
\end{align*}

It is easy to see that $ H $ has the unique distinguishing color class $ \left[  \chi_{D}(H) \right] $. Hence,
$ H $
is uniquely distinguishing colorable but it is not uniquely colorable.

[scale=.8, thick, vertex/.style=scale=.5, ball color=black, circle, text=white, minimum size=.2mm,
Ledge/.style=to path=
.. controls +(45:2) and +(135:2) .. ()
[label=[label distance=.1cm]-90:$a_{4}$] (a1) at (0,0) [vertex] ;
[label=[label distance=.1cm]-90:$a_{5}$] (a2) at (2,0) [vertex] ;
[label=[label distance=.1cm]-90:$a_{6}$] (a3) at (4,0) [vertex] ;
[label=[label distance=.1cm]90:$a_{1}$] (a4) at (0,2) [vertex] ;
[label=[label distance=.1cm]90:$a_{2}$] (a5) at (2,2) [vertex] ;
[label=[label distance=.1cm]90:$a_{3}$] (a6) at (4,2) [vertex] ;
(a4) to(a1) to (a2) to (a3) ;
(a4) to (a5) to (a6);
(a5) to (a1);
(a5) to (a3);
(a6) to (a3);

A uniquely distinguishing colorable graph $H$ that is not uniquely colorable.

(1)  For positive integers $n$ and $m$, the graphs $ K_{n} $,
$ \overline{K_{n}}$,
$ K_{n,m} $ and $ P_{2n} $ are uniquely distinguishing colorable. But $ C_{n} $ (for  $ n \geq 5 $) and  $ P_{2n+1} $ (for  $ n \geq 2 $) are not uniquely distinguishing colorable.

(2)  Let  $ G $ be a uniquely colorable graph  and  $ D(G) = 1$. Then $ G $ is uniquely distinguishing colorable and
$ \chi_{D}(G) = \chi (G) $.

(3) Let  $ G $ be a connected graph and  $ \chi_{D}(G) = 2$. Then $ G $ is a uniquely distinguishing colorable.

Let  $G$ be a uniquely distinguishing $n$-colorable graph and
$n \neq \vert V(G) \vert$. Then  $G$ is uniquely distinguishing colorable with $\chi_{D}(G) = n$.

Clearly $  \chi_{D}(G)  \leq n < \vert V(G) \vert $. Assume that
$  \chi_{D}(G) < n $  and seek a contradiction. Suppose that
$[\chi_{D}(G)] = \{V_{1}, V_{2}, \ldots , V_{\chi_{D}(G)}\} $ and
choose the set
$ \{x_{1}, x_{2}, \ldots ,x_{\chi_{D}(G)}\}$
of vertices of $G$ such that $ x_{i} \in V_{i}$, for each $i$, $1\leq i\leq X_{D}(G)$.
Clearly there are at least two subsets of $V(G)$ of cardinality
$ n - \chi_{D}(G) $
from the remaining vertices.
Now, each time we can color one of these subsets with
$ \chi_{D}(G)+1, \chi_{D}(G)+2, \ldots , n  $
and  the remaining vertices with their colors given in
$ \left[  \chi_{D}(G) \right]$.
So we obtain at least two different colorings with $n$ colors of $G$, which is a contradiction.
Therefore $  \chi_{D}(G) =n$.

§ DISCONNECTED GRAPHS

In 1968, Cartwright and Harary [7] 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 uniquely distinguishing colorable graphs, and unlike proper coloring, the study of unique distinguishing colorability of disconnected graphs is challenging.

Let  $ G $ be a uniquely distinguishing colorable graph with the unique coloring
$ \left[  \chi_{D}(G) \right] = \{V_{1}, V_{2}, \ldots ,V_{n}\} $. Clearly,  in a  distinguishing $n$-coloring of  $G$, one can assign $n$ colors to $V(G)$ with $n!$ 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 uniquely distinguishing colorable graphs.

Let  $ G $ be a connected uniquely distinguishing colorable graph.
We say that $G$ has type 1 if for any labeling of the distinguishing color classes of components of
$G \cup G$
there exists an automorphism which embeds one component into the other and preserves all the distinguishing color class labels. Otherwise, we say that
is of type 2.

For instance, the graph in Figure 3(a) is of type 2, and the graph in Figure 3(b) is of type 1.

[][scale=.7,thick, vertex/.style=scale=.5, ball color=black, circle, text=white, minimum size=.2mm,
Ledge/.style=to path=
.. controls +(45:2) and +(135:2) .. ()
[label=[label distance=.1cm]90:$ 2 $] (a1) at (18:2) [vertex] ;
[label=[label distance=.1cm]90:$ 1 $] (a2) at (90:2) [vertex] ;
[label=[label distance=.1cm]90:$ 3 $] (a3) at (162:2) [vertex] ;
[label=[label distance=.1cm]-90:$ 2 $] (a4) at (234:2) [vertex] ;
[label=[label distance=.1cm]-90:$ 3 $] (a5) at (306:2) [vertex] ;
(a1) to (a2) to (a3) to (a4) to (a5) to (a1);
(a4) to (a2) to (a5);

[scale=.7,thick, vertex/.style=scale=.5, ball color=black, circle, text=white, minimum size=.2mm,
Ledge/.style=to path=
.. controls +(45:2) and +(135:2) .. ()
[label=[label distance=.1cm]-90:$1$] (a1) at (0,0) [vertex] ;
[label=[label distance=.1cm]-90:$ 2 $] (a2) at (2,0) [vertex] ;
[label=[label distance=.1cm]-90:$ 1 $] (a3) at (4,0) [vertex] ;
[label=[label distance=.1cm]90:$ 2 $] (a4) at (0,2) [vertex] ;
[label=[label distance=.1cm]90:$ 1 $] (a5) at (2,2) [vertex] ;
[label=[label distance=.1cm]90:$ 2 $] (a6) at (4,2) [vertex] ;
(a4) to(a1) to (a2) to (a3) ;
(a4) to (a5) to (a6);
(a2) to (a5);

Uniquely distinguishing colorable graphs of of type 2 and type 1.

We say that two colorings
$\left[  \chi_{D}(G) \right]_{1}$
$\left[  \chi_{D}(G) \right]_{2}$
are isomorphic, if we color each component of
$G \cup G$
with one of
$\left[  \chi_{D}(G) \right]_{1}$
$\left[  \chi_{D}(G) \right]_{2}$,
for any arbitrary labeling of  color classes of
$\left[  \chi_{D}(G) \right]_{1}$,
there is a labeling of  color classes of
$\left[  \chi_{D}(G) \right]_{2}$,
and an automorphism such that images one component of
$G \cup G$
into the other and preserves all the distinguishing color class labels.

For an integer
$\mathop{\cup}\limits^{n} G$
denote the disjoint union of
copies of

be a connected graph. For a positive integer
$\mathop{\cup}\limits^{n} G$
is a uniquely distinguishing colorable graph, then
$G$ is uniquely distinguishing colorable.

$n\geq 2$.
is not uniquely distinguishing colorable, then it has at least two partitions of its vertices, as
$\left[  \chi_{D}(G) \right]_{1}$
$\left[  \chi_{D}(G) \right]_{2}$,
into distinguishing colorings.
$\left[  \chi_{D}(G) \right]_{1}$
$\left[  \chi_{D}(G) \right]_{2}$
are not isomorphic, then we can consider two components of
$\mathop{\cup}\limits^{n} G$
and color each component with one of the distinguishing colorings of $G$ each time.
Therefore, a different partition of
$\mathop{\cup}\limits^{n} G$
is achieved each time, which forms a distinguishing coloring.
$\left[  \chi_{D}(G) \right]_{1}$
$\left[  \chi_{D}(G) \right]_{2}$
are isomorphic, then consider the distinguishing coloring of
$\mathop{\cup}\limits^{n} G$.
If both
$\left[  \chi_{D}(G) \right]_{1}$
$\left[  \chi_{D}(G) \right]_{2}$
are used in the distinguishing coloring of components of
$\mathop{\cup}\limits^{n} G$,
we do the same as above.
Note that in this case there is a labeling of distinguishing color classes of
$\left[  \chi_{D}(G) \right]_{1}$
$\left[  \chi_{D}(G) \right]_{2}$
such that there is no color-preserving automorphism that image
$\left[  \chi_{D}(G) \right]_{1}$
$\left[  \chi_{D}(G) \right]_{2}$.
Otherwise, at most one of
$\left[  \chi_{D}(G) \right]_{1}$
$\left[  \chi_{D}(G) \right]_{2}$
is used in the distinguishing coloring of components of
$\mathop{\cup}\limits^{n} G$.
Assume that
$\left[  \chi_{D}(G) \right]_{1}$
is not used in the distinguishing coloring of
$\mathop{\cup}\limits^{n} G$.
Consider an arbitrary labeling of distinguishing color classes of
$\left[  \chi_{D}(G) \right]_{1}$.
There is at most one component of
$\mathop{\cup}\limits^{n} G$
such that its coloring which image with an automorphism to the
$\left[  \chi_{D}(G) \right]_{1}$
with its considered labeling and preserves the labels.
Replace the coloring of this component with
$\left[  \chi_{D}(G) \right]_{1}$
and its considered labeling.
Thus we have another distinguishing coloring for
$\mathop{\cup}\limits^{n} G$.
This means that
$\mathop{\cup}\limits^{n} G$
has at least two distinguishing colorings and the result follows.

be a connected graph.
For a positive integer
$\mathop{\cup}\limits^{n} G$
is a uniquely distinguishing colorable, then
$\chi_{D}(\mathop{\cup}\limits^{n} G)=\chi_{D}(G)$.

For the sake of contradiction, assume that
$\chi_{D}(\mathop{\cup}\limits^{n} G)>\chi_{D}(G)$.
We claim that there exist two components of
$\mathop{\cup}\limits^{n} G$
with at least one different color in the distinguishing coloring of
$\mathop{\cup}\limits^{n} G$.
For this purpose, suppose that exactly
$\chi_{D}(\mathop{\cup}\limits^{n} G)$
colors are used in each component.
Consider the coloring of one component of
$\mathop{\cup}\limits^{n} G$
and replace it with the unique distinguishing coloring of graph
Therefore, we will have another distinguishing coloring for
$\mathop{\cup}\limits^{n} G$.
Now, we can select two components
$\mathop{\cup}\limits^{n} G$
such that the colors used in them are not the same.  Interchanging the distinguishing colorings of
gives us a new distinguishing coloring for
$\mathop{\cup}\limits^{n} G$,
a contradiction.

be a graph of type 1. Then
$\chi_{D}(G \cup G) =\chi_{D}(G)+1$.

is uniquely distinguishing colorable, there is only one partition of the vertex set
into a distinguishing coloring. Because $G$ is of type 1, it follows that for any two labelings of this partition,
there exists an automorphism of $G$ which embeds one of them into the other and preserves all the distinguishing color class labels.
Hence, we need a new color to distinguish any two components of

be a connected graph. For a positive integer
$\mathop{\cup}\limits^{n} G$
is a uniquely distinguishing colorable graph, then
$n\leq 2$.

For the sake of contradiction, assume that
$n\geq 3$.
be some components of
$\mathop{\cup}\limits^{n} G$.
Lemmas <ref>, <ref>, conclude that the colorings of
are the same with a different assigned label for some color classes.
denote a color class of
$\left[  \chi_{D}(G) \right]$
that is labelled by
respectively. Interchanging the labels of the color classes of
and keeping the coloring of
give us another partition of vertices
$\mathop{\cup}\limits^{n} G$
into a distinguishing coloring, a contradiction.

Let $ G $ be a non-empty uniquely distinguishing colorable graph. Then $ G $ is connected or it is isomorphic to $H\cup H$, where $H$ is a connected graph of type $2$.

Let  $ G $ be a disconnected uniquely distinguishing colorable graph.  By Lemmas <ref>, <ref>, $G$ has two uniquely distinguishing colorable components, say
$ H_{1} $ and $ H_{2}$.
Consider a distinguishing coloring of $G$ with minimum number of colors. Then
$ H_{2} $
have at least one same color.
Now suppose that $ H_{1} \ncong H_{2}$. Since $ G $ has at least one edge, we may assume that $ \chi_{D}(H_{1}) \geq 2$.
Thus $ H_{1} $ has at least two color classes  $ V_{1} $ and $ V_{2} $ in  $ \left[  \chi_{D}(H_{1}) \right]$.
Also, let $ U $ be a color class of $ H_{2}$. So we may assume that $ V_{1} $ and $ U$
have a common color. Interchange the colors
$ V_{1} $
$ V_2$,
and produce a new partition of $ V(G) $
into distinguishing color classes. This is the required contradiction. Hence we have $ H_{1} \cong H_{2}$. Now assume that $H_1$ (and so $H_2$) is of type 1.
Lemmas <ref>, <ref> conclude that
$H_1 \cup H_2$ is not uniquely distinguishing colorable. This implies that $ G $ is a union of copies of a graph of type 2.

The disconnected graph in Figure 4 is uniquely distinguishing $2$-colorable.  Clearly, each of its components  is of type 2.

[scale=.7, thick, vertex/.style=scale=.5, ball color=black, circle, text=white, minimum size=.2mm,
Ledge/.style=to path=
.. controls +(45:2) and +(135:2) .. ()
[label=[label distance=.1cm]-90:$2$] (a1) at (0,0) [vertex] ;
[label=[label distance=.1cm]-90:$1$] (a2) at (2,0) [vertex] ;
[label=[label distance=.1cm]-90:$2$] (a3) at (4,0) [vertex] ;
[label=[label distance=.1cm]90:$1$] (a4) at (0,2) [vertex] ;
[label=[label distance=.1cm]90:$2$] (a5) at (2,2) [vertex] ;
[label=[label distance=.1cm]90:$1$] (a6) at (4,2) [vertex] ;
[label=[label distance=.1cm]90:$2$] (a7) at (6,2) [vertex] ;
(a4) to(a1) to (a2) to (a3) ;
(a4) to (a5) to (a6)to (a7);
(a2) to (a5);

[scale=.7,thick, vertex/.style=scale=.5, ball color=black, circle, text=white, minimum size=.2mm,
Ledge/.style=to path=
.. controls +(45:2) and +(135:2) .. ()
[label=[label distance=.1cm]-90:$1$] (a1) at (0,0) [vertex] ;
[label=[label distance=.1cm]-90:$2$] (a2) at (2,0) [vertex] ;
[label=[label distance=.1cm]-90:$1$] (a3) at (4,0) [vertex] ;
[label=[label distance=.1cm]90:$2$] (a4) at (0,2) [vertex] ;
[label=[label distance=.1cm]90:$1$] (a5) at (2,2) [vertex] ;
[label=[label distance=.1cm]90:$2$] (a6) at (4,2) [vertex] ;
[label=[label distance=.1cm]90:$1$] (a7) at (6,2) [vertex] ;
(a4) to(a1) to (a2) to (a3) ;
(a4) to (a5) to (a6)to (a7);
(a2) to (a5);

A disconnected uniquely distinguishing colorable graph.

Let $ G $ be a   uniquely distinguishing colorable  graph. If $ G $ is 2-regular, then
$ G$ is isomorphic to $C_{3}$ or
$ C_{4}$.

Assume that we assign a distinguishing coloring to $G$ with minimum number of colors.
Clearly, each $2$-regular graphs is a union of some cycles. On the other hand,  it is easy to see that the uniquely distinguishing colorable cycles are
$ C_{3} $ and $ C_{4}$. Now, let $ G $ be  a $ 2 $-regular uniquely distinguishing  colorable graph.
We observe that $C_3$ and $C_4$ are of type 1 and type 2, respectively. If $G$ is disconnected, it
cannot be a union of some copies of $ C_{3} $,  by Theorem <ref>.
Suppose that  $G$ is a union of some copies of $ C_{4}$ and  that one component of $ G $ contains vertices  $ v_{1}, v_{2}, v_{3}$, $ v_{4} $  and  edges    $ v_{1}v_{2}, v_{2}v_{3}, v_{3}v_{4}$, $ v_{4}v_{1} $. Now, by replacing  the color of $ v_{1}$ with $v_{2}, v_{2}$ with $v_{3}, v_{3}$ with  $v_{4}$ and finally $ v_{4}$ with $v_{1} $,
one can obtain  another distinguishing color class of
$ G $.
This implies that
$ G $ is isomorphic to $C_{3}$ or $ C_{4} $.

The converse of Theorem <ref> is not correct. Actually, type 2 graphs exist in such a way that their union cannot be uniquely distinguishing colorable.
For instance, consider an $m$-partite graph
of order
$2\leq m < n$.
has at least a part
with cardinality greater than one. Also,
is a graph of type 2. Let
$v_1 , v_2 \in U$
be two vertices with colors
$2$, respectively.
Interchanging the colors
of the vertices produces a new partition of
$V (G \cup G)$
into distinguishing color classes.

be a connected graph.
$\mathop{\cup}\limits^{2} G$
is a uniquely distinguishing colorable, then for any colored graph
there exists an automorphism
and exactly one component
$\mathop{\cup}\limits^{2} G$
such that
preserves the distinguishing  color class labels.

For a contradiction, assume that there exists a colored graph
such that any automorphism
$f(G)= G'$,
do not preserve the color class labels. By replacing the coloring of one component of
$\mathop{\cup}\limits^{2} G$
with the distinguishing coloring of
we will obtain another distinguishing coloring of
$\mathop{\cup}\limits^{2} G$,
a contradicting.

be a connected graph.
$G \cup G$
is a uniquely distinguishing colorable, then there exists exactly two labeling of the distinguishing color classes of
that don't image together by a color-preserving automorphism.

be a bipartite graph.
is an asymmetric graph (that is, the automorphism group of
is trivial), then
is of type 2,
$G \cup G$
is a uniquely distinguishing colorable graph and so
$\chi_{D}(G \cup G)= \chi_{D}(G)=2$.
This means that there are an infinite number of disconnected uniquely distinguishing colorable graphs.

§ BIPARTITE GRAPHS

In this section, we study the uniquely distinguishing colorable bipartite graphs and specially uniquely distinguishing colorable trees.
As main result of this section, we show that the only uniquely distinguishing colorable tree is star graph, when distinguishing chramatic number is more than

Let $ G $ be a graph and $ x $
be a fixed  vertex of $G$ such  that $ \chi_{D}(G) - 1 >\T{deg}( x )$. Then $ G $ is not uniquely distinguishing colorable.

Let $[\chi_{D}(G)] = \{V_{1}, V_{2}, \ldots ,V_{\chi_{D}(G)} \} $
be a distinguishing coloring of $ G $ such that $ N(x) $
has no intersection with at least two distinguishing color classes of $G$, say with $ V_{1} $ and $ V_{2}$. Now, assume that  the distinguishing color class of $ x $ is of cardinality one and that $ x \in V_{1} $.
By replacing  the color of $ V_{1} $ with the color of $ V_{2} $, one can obtain a distinguishing coloring of
$ G $ with less than $ \chi_{D}(G) $ colors. This implies that  the distinguishing color class of $ x $
is of cardinality at least two. Suppose that
$ x \in V_{1} $  and that $ \vert V_{1} \vert \geq 2$. Now, by replacing the color of
$x$ with the color of $V_{2}$, we get another distinguishing color class of
$ G $. Hence $ G $ is not uniquely distinguishing colorable.

Let $ G $ be a connected uniquely distinguishing colorable graph with a fixed pendant vertex. Then
$ D(G) = 1 $ and $ \chi_{D}(G) = 2 $.

By Lemma <ref>,
$ \chi_{D}(G) = 2$. Hence $ G $ is bipartite. Assume that $ D(G) \neq 1$ and seek a contradiction.
There is a non-trivial automorphism
such that
for two vertices
should be of the same distance of the pendant vertex. This implies that the distance between
must be even and so
they will be in the same part in the bipartite graph
preserve the unique distinguishing coloring and which is a contradiction.

Let  $ G $ be a uniquely distinguishing colorable graph with at least two sibling pendant vertices. Then $ G $ is a star graph.

Let $ a $ and $ b $ be sibling pendant vertices of $ G$. Assume that $ G$ is not a star graph.  Consider a 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 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 \nsim c \nsim 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 distinguishing color class of $G$, so we reach a contradiction.

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

<cit.> Let $ T $ be a tree with at least $ 2 $ vertices. Then $ \chi_{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$.

Let $ T $ be a uniquely distinguishing colorable tree with $ \chi_{D}(T) \geq 3 $. Then $ T $ is a star graph.

Assume that  $ T $ is not a star, and seek a contrdiction.  Consider a distinguishing coloring
of $T$ with minimum number of colors. By Lemma <ref>, $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$ and  that $ v $ and $ u $ are  two pendant vertices of $T$ imaged 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 maximal set of  fixed vertices of $T$.
Let $A$ denote the set of fixed vertices of $T$ by $f$.
Clearly $A\neq \emptyset$, because $ a\in A $. Assume that $ A $ and $ V(T)\setminus A $ have vertices with the same color
in the distinguishing coloring of $ T $. Now, consider the induced  subgraph $ T[V(T)\setminus A]$ containing two isomorphic components. By interchanging the colors of the corresponding vertices in the two components,  we get another distinguishing color class of $ T$, a contradiction. This implies that  the vertices in  $ A $ and the vertices in $ V(T)\setminus 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 vertices of $ V(T)\setminus A$.  Now, we claim that, by replacing the color $ v$ (or $ u $) with this color,  one can obtain  another 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\in A$. Now, since $T$ has no sibling pendant vertices, $ a \nsim 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)\setminus 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 8.

[thick, vertex/.style=scale=.5, ball color=black, circle, text=white, minimum size=.2mm,
Ledge/.style=to path=
.. controls +(45:2) and +(135:2) .. ()
[label=[label distance=.1cm]-90:$u$] (u) at (0,0) [vertex] ;
/in 1,2,3,4/n

[label=[label distance=.1cm]-90:$a_\xtext$] () at (,0) [vertex] ;
[Ledge] (,0) to(,0) node[label=[label distance=.2cm]90:$G_\xtext$] ;;

/in 5/n,6/3,7/2,8/1

[label=[label distance=.1cm]-90:$b_\xtext$] () at (,0) [vertex] ;
[Ledge] (,0) to(,0) node[label=[label distance=.2cm]90:$H_\xtext$] ;;

[label=[label distance=.1cm]-90:$v$] (v) at (9,0) [vertex] ;
(u) to (1) to (2) to (3);
[dotted] (3) to (4);
(4) to (5);
[dotted] (5) to (6);
(6) to (7) to (8) to (v);

Graph $T$.

In Figure 8, $ G_{i} \cong H_{i} $ for all $i=1, \ldots , n$. Thus edge $ a_{n}b_{n} $ is the center of $ T$. Furthermore, $ a_{n}$ and $b_{n} $ 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 , n$,  and so the distance between these two vertices is even, which
is a contradiction.  Thus  Theorem <ref>  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 <ref>,
$ T $ is not a uniquely distinguishing colorable tree. This is a required contradiction.

§ GRAPHS WITH $\CHI_{D}(G \CUP G)= \CHI_{D}(G)$

is a connected graph, then
$\chi_{D}(G \cup G)= \chi_{D}(G)$
$\chi_{D}(G \cup G)= \chi_{D}(G)+1$.
$A, B \subseteq V(G)$.
We say that
are equal up to automorphism, if there exists an automorphism
such that
$f(A) = B$
$f(B) = A$.

be a connected graph. If $G$ is not uniquely distinguishing colorable, then
$\chi_{D}(G \cup G)= \chi_{D}(G)$.

By the way of contradiction, suppose that
$\chi_{D}(G \cup G)= \chi_{D}(G)+1$.
There exist two coloring
$\left[  \chi_{D}(G) \right]_1 = \{V_{1}, V_{2}, \ldots ,V_{\chi_{D}(G)}\}$
$\left[  \chi_{D}(G) \right]_2 = \{U_{1}, U_{2}, \ldots ,U_{\chi_{D}(G)}\}$
If both components of
$G \cup G$
are colored with one of
$\left[  \chi_{D}(G) \right]_1$
$\left[  \chi_{D}(G) \right]_2$,
or each component is colored with one of
$\left[  \chi_{D}(G) \right]_1$
$\left[  \chi_{D}(G) \right]_2$,
such that labels from
are used in each component,
there will be an automorphism which embeds one component into the other and preserves all the distinguishing color class labels.
This implies that all color classes of
$\left[  \chi_{D}(G) \right]_1$
$\left[  \chi_{D}(G) \right]_2$,
are equal up to automorphism.
$\left[  \chi_{D}(G) \right]_1$
$\left[  \chi_{D}(G) \right]_2$
give us different partitions of
we can consider
$A:=V_1 \cap U_1 \neq \emptyset$
$B:= V_1 - A = U_1 - A \neq \emptyset$.
In each color class, there is a copy of
For any
$1\leq i \leq \chi_{D}(G)$,
$V_i = A_{V_i } \cup B_{V_i }$
$U_i = A_{U_i } \cup B_{U_i }$,
$A_{V_i }$ ($A_{U_i }$)
$B_{V_i }$ ($B_{U_i }$)
are equal up to automorphism to
respectively. Clearly, for any
$1\leq i \leq \chi_{D}(G)$,
$A_{V_i } \cup B_{V_i }$
$A_{U_i } \cup B_{U_i }$
are independent sets. Also
$A_{U_1} \cup B_{V_1}$
is an independent set.

We claim that there is no edge between
$A_{V_i }$
$B_{V_j }$,
$1\leq i, j \leq \chi_{D}(G)$.
Assume, for the sake of contradiction, that there is an edge between a vertex of
and a vertex of
for some
$1\leq j<k \leq \chi_{D}(G)$.
Consider a coloring of components of
$G \cup G$
$\left[  \chi_{D}(G) \right]_1$
such a way that in the first component assign label
$V_i$, $1\leq i \leq \chi_{D}(G)$,
and in the second component assign label
and labeling other color classes
$i$, $2\leq i(\neq k)\leq \chi_{D}(G)$.
There exists an automorphism that images these two components to each other and preserves all the distinguishing color class labels.
Thus, there is an edge between a vertex of
and a vertex of

Again, consider a coloring of the components of
$G \cup G$
such that each component is colored with one of the
$\left[  \chi_{D}(G) \right]_1$
$\left[  \chi_{D}(G) \right]_2$
such a way that the first component is colored with
$\left[  \chi_{D}(G) \right]_1$
and assign label
$V_i$, $1\leq i \leq \chi_{D}(G)$,
and the second component is colored with
$\left[  \chi_{D}(G) \right]_2$, assign label
and labeling other color classes
$i$, $2\leq i(\neq j) \leq \chi_{D}(G)$.
The automorphism imaging these two components to each other and preserves all the distinguishing color class labels conclude that
there is an edge between a vertex of
and a vertex of
a contradiction.

Therefore, there is no edge between
$A_{V_i }$
$B_{V_j }$,
$1\leq i, j \leq \chi_{D}(G)$
and so
is a disconnected graph, which is the required contradiction.

The following corollary is immediate by Theorem <ref>, Lemma <ref>, Lemma <ref> and Theorem <ref>.

be a connected graph. Then
$\chi_D(G\cup G)=\chi_D(G)+1$
if and only if
is uniquely distinguishing colorable of type 1.

In what follows, we characterise all connected graphs
$\chi_D(G\cup G)=\chi_D(G)+1$

be a graph. For two vertices
if there exist an automorphism
then there exists an automorphism
$g(v_1)= v_2$
$g(v_2)= v_1$.

Assume that the order of
We claim that there exists an integer
$k \leq n$
such that
Suppose that for any
$f^{k}(v_1)\neq v_1$.
So, let
be the smallest integer for which
$ i\leq \ell$.
This implies that
$f^{\ell-i+1}(v_1)= v_1$,
a contradiction. Hence,
there are vertices
$v_1, v_2, \ldots , v_k$
such that
$1\leq i \leq k-1$.
The automorphism
appears a symmetry in the graph so that we can consider an automorphism

For a graph
$f \in {\rm Aut}(G)$,
${\rm Fix}(f)=\{v \in V(G) \; | \; f(v)=v\}$.

be a connected graph with
$\chi_{D}(G \cup G)=3$
if and only if
is a bipartite graph with
${\rm Aut}(G) \cong \mathbb{Z}_2 = \{id, f\}$,
${\rm Fix}(f)= \emptyset$
images the two parts
to each other.

By Remark <ref>(3),
is uniquely distinguishing colorable. Let
denote the parts of
The distinguishing coloring of
$\{V, U\}$.
The automorphism group of
is not trivial (since otherwise
$\chi_{D}(G \cup G)= \chi_{D}(G)$).
Assume first that there exists an automorphism
$f(v_1)= v_2$,
for two vertices
By Lemma <ref>, without loss of generality, we may assume that
$f(v_2)= v_1$.
does not preserve the coloring, there are vertices
$v_3 \in V$
$u_1 \in U$
such that
$f(v_3)= u_1$.
be a path between
Observation 16 [14] implies that one of vertices
cannot be in
and the other be out of the path. We now divide the proof into two cases.

Case 1. $v_3, u_1 \in V(P)$.
The distance between two vertices in the same parts and different parts is even and odd, respectively. Without loss of generality, we may assume that
${\rm d}(v_3, v_2)<{\rm d}(v_3, v_1)$
flips path
$v_1-u_1$ path
$v_2-v_3$ path
must be of the same size in
But the size of
$v_1-u_1$ path is odd
$v_2-v_3$ path is even.

Case 2. $v_3, u_1 \notin V(P)$.
In this case, if there exists a path including
flips this path and moves at least one of
similarity to case 1, it is impossible. Let $P'$ be a path including
Assume that when
flips, does not move
have the same distance from
a contradiction.

So, any automorphism image the two parts
together. Let
be such an automorphism. Suppose that
$w \in {\rm Fix}(f)$
for vertices
$v\in V$
$u \in U$.
${\rm d}(v, w)={\rm d}(u, w)$.
But, if
$w \in V$  ($w \in U$)
the distance between
is even (odd) and the distance between
is odd (even). This implies that
${\rm Fix}(f)= \emptyset$
and there is only an non-trivial automorphism of
(Note that if there are two automorphisms
that images the two parts of
together, then there are vertices
$v_1 \in V$
$u_1, u_2 \in U$
and it is impossible.)

$(\Leftarrow)$ Since
is a connected bipartite graph and there is an automorphism that images the two parts
is of type 1 and so $\chi_{D}(G \cup G)= \chi_{D}(G)+1$.

In following, we investigate all graphs $G$
such that
$\chi_D(G\cup G)=\chi_D(G)$,
$k\in \{|V(G)|-2, |V(G)|-1, |V(G)|\}$.
To do this, we begin with Theorem <ref>, Theorem <ref> and Theorem <ref>, in which all graphs
of order $n$ with distinguishing chromatic number $n$, $n-1$ and $n-2$ were charaterized [12, 8].
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_i v_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 defined graphs
$\hat{G}_5$, $\hat{G}_6$ and $\hat{G}_7$
along with a class of labelled graphs G$_3$ consisting of two non-isomorphic graphs.
The labelled graphs
$ \hat{G}_{5} $, $ \hat{G}_{6} $
$ \hat{G}_{7} $
have vertices
$ (v_1, v_2, v_3, v_4) $,
$ (v_1, v_2, v_3, v_4, v_5) $
$ (v_1, v_2, v_3, v_4, v_5, v_6) $
respectively, while a labelled graph
$ \hat{G}_{3} $
belonging to the class
has vertices $ (v_1, v_2, v_3, v_4, v_5)$,
see Figure 6 and Figure 7.
Furthermore, define
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)$
$\hat{K}_{3}(v_1, v_2, v_3)$
has vertices
$(v_1, v_2, v_3)$.
In particular, if
are nonvacuous complete multipartite graphs, then
$\hat{K}_{2}(H_1, H_2)$
represents a complete multipartite graph with at least two parts.

Let $G$ be a graph. Then $\chi_{D}(G)=|V(G)|$ if and only of $G$ is a complete multipartite graph.

be a graph of order
$n > 3$.
$\chi_D(G) = n-1$
if and only if
is the join of a complete multipartite graph (possibly vacuous) with one of the following:

$2K_2$, or

$H\cup K_1$,
is a complete multipartite graph with at least two parts.

[scale=.4, thick, vertex/.style=scale=.5, ball color=black, circle, text=white, minimum size=.2mm,
Ledge/.style=to path=
.. controls +(45:2) and +(135:2) .. ()
[label=[label distance=.1cm]90:$v_1$] (a1) at (-2, 4) [vertex] ;
[label=[label distance=.001cm]-90:$v_2$] (a2) at (-2, 0) [vertex] ;
[label=[label distance=.001cm]-90:$v_3$] (a3) at (2, 0) [vertex] ;
[label=[label distance=.001cm]90:$v_4$] (a4) at (2, 4) [vertex] ;
(a1) to (a2) ;
(a2) to (a3) ;
(a3) to (a4) ;

[scale=.4 ,thick, vertex/.style=scale=.5, ball color=black, circle, text=white, minimum size=.2mm,
Ledge/.style=to path=
.. controls +(45:2) and +(135:2) .. ()
[label=[label distance=.1cm]90:$v_1$] (a1) at (-2, 4) [vertex] ;
[label=[label distance=.001cm]-90:$v_2$] (a2) at (-2, 0) [vertex] ;
[label=[label distance=.001cm]-90:$v_3$] (a3) at (2, -1) [vertex] ;
[label=[label distance=.001cm]90:$v_4$] (a4) at (2, 1) [vertex] ;
[label=[label distance=.001cm]90:$v_5$] (a5) at (2, 4) [vertex] ;
(a1) to (a2) ;
(a2) to (a3) ;
(a3) to (a4) to (a2) ;

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)$.

[scale=.6, thick, vertex/.style=scale=.5, ball color=black, circle, text=white, minimum size=.2mm,
Ledge/.style=to path=
.. controls +(45:2) and +(135:2) .. ()
[label=[label distance=.001cm]90:$v_1$] (a1) at (-2, 1) [vertex] ;
[label=[label distance=.001cm]-90:$v_2$] (a2) at (-1, 0) [vertex] ;
[label=[label distance=.001cm]-90:$v_3$] (a3) at (1, 0) [vertex] ;
[label=[label distance=.001cm]90:$v_4$] (a4) at (2, 1) [vertex] ;
[label=[label distance=.001cm]90:$v_5$] (a5) at (1, 3) [vertex] ;
[label=[label distance=.001cm]90:$v_6$] (a6) at (-1, 3) [vertex] ;
(a1) to (a2) to (a3) to (a4) to (a5) to (a6) to (a1) ;
(a4) to (a1) to (a3);
(a4) to (a2);
(a6) to (a2);
(a5) to (a3);

[scale=1 ,thick, vertex/.style=scale=.5, ball color=black, circle, text=white, minimum size=.2mm,
Ledge/.style=to path=
.. controls +(45:2) and +(135:2) .. ()
[label=[label distance=.1cm]90:$v_1$] (a1) at (0, 0) [vertex] ;
[label=[label distance=.001cm]90:$v_2$] (a2) at (1, 1) [vertex] ;
[label=[label distance=.001cm]-90:$v_3$] (a3) at (1, -1) [vertex] ;
[label=[label distance=.001cm]90:$v_4$] (a4) at (3, 1) [vertex] ;
[label=[label distance=.001cm]-90:$v_5$] (a5) at (3, -1) [vertex] ;
[label=[label distance=.001cm]-90:$\vdots$] (a) at (3, 0) [] ;
[label=[label distance=.001cm]-90:$\vdots$] (a) at (3, .4) [] ;
[label=[label distance=.001cm]-90:$\vdots$] (a) at (3, .8) [] ;
[label=[label distance=.001cm]-90:$\vdots$] (a) at (3, 1.2) [] ;
[label=[label distance=.001cm]-90:$\vdots$] (a) at (3, 1.6) [] ;
(a3) to (a5) ;
(a2) to (a4) ;
(a2) to (a3) ;
(a3) to (a1) to (a2) ;

Graphs $\hat{G}_{7}(v_1, v_2, v_3, v_4, v_5, v_6)$  and G$_3$ $(v_1, v_2, v_3, v_4, v_5)$.

be a graph of order
$n > 4$.
Then $\chi_{D}(G) = n - 2$
if and only if
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$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_3 $

(f) $\hat{K}_{2}(\overline{K_r}, H_1) \cup K_2$, for $ r\geq 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) $

(l) $ (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.

be a graph of order

$\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}$

By Theorem <ref>,
is a complete multipartite graph.
The only non-trivial case is when
$G \notin \{K_n,  \overline{K_n}\}$.
In this case, there is at least one part, via $U$,  with cardinality more than
There exist at least two subsets of size
$\{1, 2. \ldots, \chi_D(G)\}$.
$\{1, 2, \ldots, |U|\}$
in a component of
$G \cup G$
and color
in the other component with
$\{1, 2, \ldots, |U|-1, |U|+1\}$.
Also, color other vertices of
$G \cup G$
One can check that this is a distinguishing $\chi_D(G)$-coloring for
$G \cup G$.

be the join of a nonvacuous complete multipartite graph
with one of graphs (1) and (2) in Theorem <ref> or one of graphs (a) - (q) in Theorem <ref>.
$\chi_{D}(G \cup G)= \chi_{D}(G)$.

be a nonvacuous complete multipartite graph and
be one of graphs (1) and (2) in Theorem <ref> or one of graphs (a) - (q) in Theorem <ref>.
denote the graphs isomorphic to
$i=1, 2$.
We claim that if
is an automorphism with
For this, assume that all parts of
have cardinality more than one. On the other hand, all vertices of
adjacent to all vertices of
This implies that we cannot replace some vertices of
with some vertices of
such that the structure of
is preserved.
(Note that
is not a complete multipartite graph.)
has a part $\{x\}$, then a necessary condition for that we can replace
with a vertex of
such that the structure of
is preserved, is that there exist a vertex
$y \in K$
${\rm deg}_{K}(x)=|V(K)|-1$.
One can check there is no such $x$ in graphs (1) and (2) in Theorem <ref> and graphs (a) - (q) in Theorem <ref>.

There exist two vertices with the same color in
Assume that color
is assigned to two vertices in
and color
is assigned to a vertex in
The vertices colored by $1$ are in
Now, color the vertices of
with the coloring of
by interchanging colors
Therefore, any automorphism that image
does not preserve the colors.

be a graph of order
$n > 3$
$\chi_D(G) = n-1$.

$\chi_D(G\cup G)=\chi_D(G)$
if and only if

is the join of a nonvacuous complete multipartite graph with one of the following:

$2K_2$, or,

$H\cup K_1$.

$G\cong H\cup K_1$, $H\ncong K_{n-1}$.

$\chi_D(G\cup G)=\chi_D(G)+1$
if and only if
is one of the following:

$K_{n-1}\cup K_1$.

is a complete multipartite graph with at least two parts.

According to Theorem <ref>, assume first that
is the join of a nonvacuous complete multipartite graph with one of the graphs
$H\cup K_1$.
Lemma <ref> concludes the results in
$\chi_D(G\cup G)= \chi_D(4K_2)=4=\chi_D(G)+1$
and the result follows.
$G=H\cup K_1$.
is a complete multipartite graph with at least two parts,
$H \ncong \overline{K_{n-1}}$.
Now, the results in
conclude from Theorem <ref>.

be a graph of order
$n > 4$
$\chi_D(G) = n-2$.

$\chi_D(G\cup G)=\chi_D(G)$
if and only if

is the join of a nonvacuous complete multipartite graph with one of the following:

($a_{11}$) $ P_5 $

($a_{13}$) $ C_6 $

($a_{15}$) $ \overline{K_r} \cup K_2 $, for $ r \geq 2$

($a_{17}$) $ \hat{K}_{3}(H_1, H_2, H_3) \cup K_2 $

($a_{19}$) $ 2K_2 \vee 2K_2 $

($a_{111}$) $ 2K_2 \cup K_1 $

($a_{113}$) $ (2K_2 \vee H_1) \cup K_1 $

($a_{115}$) $\hat{G}_{5}(K_1, H_1, H_2, K_1)$

($a_{117}$) $\hat{G}_{7}(H_1, H_2, H_3, H_4, K_1, K_1)$

($a_{12}$) $ C_5 $

($a_{14}$) $ 2K_3 $

($a_{16}$) $\hat{K}_{2}(\overline{K_r}, H_1) \cup K_2$, for $ r\geq 2 $

($a_{18}$) $\hat{K}_{2}(H_1, H_2) \cup \overline{K_2}$

($a_{110}$) $ 2K_2 \vee (\hat{K}_{2}(H_1, H_2) \cup K_1) $

($a_{112}$)$\hat{G}_{3}(H_1, H_2, H_3, K_1, K_1)$, for $\hat{G}_{3} \in$G$_3$

($a_{114}$) $\hat{G}_{5}(H_1, H_2, K_1, K_1)$

($a_{116}$) $\hat{G}_{6}(K_1, H_1, H_2, H_3, K_1)$

is one of the following:

($a_{21}$) $ P_5 $

($a_{23}$) $ C_6 $

($a_{25}$) $ 2K_2 \vee 2K_2 $

($a_{27}$) $ (2K_2 \vee H_1) \cup K_1 $

($a_{29}$) $\hat{G}_{7}(H_1, H_2, H_3, H_4, K_1, K_1)$

($a_{211}$) $\hat{G}_{6}(K_1, H_1, H_2, H_3, K_1)$

($a_{22}$) $ C_5 $

($a_{24}$) $ 2K_3 $

($a_{26}$) $\hat{K}_{2}(\overline{K_r}, H_1) \cup K_2$, for $ r\geq 2 $

($a_{28}$) $ 2K_2 \vee (\hat{K}_{2}(H_1, H_2) \cup K_1) $

($a_{210}$)$\hat{G}_{3}(H_1, H_2, H_3, K_1, K_1)$, for $\hat{G}_{3} \in$G$_3$

($a_{212}$) $ \hat{K}_{3}(H_1, H_2, H_3) \cup K_2 $, where $\hat{K}_{3}(H_1, H_2, H_3)$ is not a complete graph.

($a_{213}$) $\hat{K}_{2}(H_1, H_2) \cup \overline{K_2}$, where $\hat{K}_{2}(H_1, H_2)$ is not a complete graph and $|\hat{K}_{2}(H_1, H_2)|\geq 4$.

($a_{214}$) $\hat{G}_{5}(H_1, H_2, K_1, K_1)$, where $H_1 \neq K_1$ or $H_2 \neq K_1$.

($a_{215}$) $\hat{G}_{5}(K_1, H_1, H_2, K_1)$, where $H_1 \neq K_1$ or $H_2 \neq K_1$.

where each of
$H_1, H_2, H_3, H_4$
is a nonvacuous complete multipartite graph.

$\chi_D(G\cup G)=\chi_D(G)+1$
if and only if
is one of the following:

($b_{1}$) $K_{n-2}\cup K_2$

($b_{2}$)$K \cup \overline{K_2}$, $K \in \{P_3, K_{3}\}$.

($b_{3}$) $ 2K_2 \cup K_1 $

($b_{4}$) $P_4$

$\chi_D(G\cup G)=\chi_D(G)+2$
if and only if
$G\cong K_2 \cup \overline{K_2}$.

$\chi_D(G\cup G)=2\chi_D(G)$
if and only if
$G\cong \overline{K_r} \cup K_2 $, for $ r \geq 2$.

The graph
is the join of a complete multipartite graph (possibly vacuous) with one of the graphs presented in Theorem <ref>.
is the join of a nonvacuous complete multipartite graph with one of the graphs (a) - (q) presented in Theorem <ref>,
then by Lemma <ref>, we have the results in
Now, let
be one of the graphs (a) - (q) that are presented in Theorem <ref>.
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
Assign to
one color and to
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 is 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 is 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}}$
$|\hat{K}_{2}(\overline{K_r}, H_1)|\geq 3$.
Let $v_1 \in H_1, v_2, v_3 \in K_2$ and $v_4 \in \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 K_2$ and $v_1, v_4 \in \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 2K_2$, $v_3 \in K_1$ and
$v_4 \in \hat{K}_{2}(H_1, H_2)(v_4 \in 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$.

Let $v_1 \in K_1=\{v_5\}, v_3 \in K_1=\{v_6\}, v_4 \in H_4$ and $v_2 \in 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 $3$ to $v_1$ and $v_2$ and color $4$ to $v_3$ and $v_4$.

In both copies of $G \cup G$, let $v_1 \in K_1=\{v_4\}, v_3 \in K_1=\{v_5\}, v_2 \in H_3$ and $v_4 \in 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$.

Let $v_1 \in K_1=\{v_1\}, v_3 \in K_1=\{v_5\}, v_2 \in H_2$ and $v_4 \in 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}$)
$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 <ref>, 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
$G \cup G$,
we need at least
For result in
let $|\hat{K}_{2}(H_1, H_2)|= 2$. Then
$\hat{K}_{2}(H_1, H_2)$
is isomorphic with
If $|\hat{K}_{2}(H_1, H_2)|= 3$, then
$\hat{K}_{2}(H_1, H_2)$
is isomorphic with
In both cases, $\chi_D(G \cup G)=\chi_D(G)+1$.
$|\hat{K}_{2}(H_1, H_2)|\geq 4$
and $\hat{K}_{2}(H_1, H_2)$ is a complete graph by Theorem <ref>, 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_{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 K_1=\{v_3\}, v_3 \in K_1=\{v_4\}, v_2 \in H_1$ and $v_4 \in 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 K_1=\{v_1\}, v_3 \in K_1=\{v_4\}, v_2 \in H_2$ and $v_4 \in 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$.

In this case, there are four copies of
$G \cup G$.
For distinguishing those copies, we need
four colors. Also the copies
are colored by the colors used in
Hence, $\chi_D(G\cup G)= n-1 =\chi_D(G)+1$.

$G\cup G=\overline{K_{2r}} \cup 2K_2$ and $r \geq 2$,
we can color the vertices of $2K_2$ by the colors used in
$\chi_D(G \cup G)=\chi_D(\overline{K_{2r}})=2r$.

§ CONCLUSIONS AND FUTURE RESEARCH

Studying the distinguishing coloring of disconnected graphs depends on the number of colorings of its components.
Especially for calculating the distinguishing chromatic number of
$G\cup G$,
it is necessary to pay attention to unique colorability of
is a connected graph.
In this paper, our main focus is on the study of uniquely distinguishing colorable graphs, and with that, we have calculated and characterized the distinguishing chromatic number of the certain disconnected graphs.
This article can be a starting point for studying the distinguishing chromatic number of disconnected graphs.
We end the paper with the following problems.

Find the family of connected graphs that are uniquely distinguishing colorable or not.

For what subset of type 2 graphs, is the converse of Theorem <ref> correct?

For connected graphs
characterize uniquely distinguishing colorable graphs
$G\cup G$.

Characterize graphs of type 1.

Characterize the class  $\xi$  of graphs such that
$G \in \xi$
if and only if
$\chi_{D}(G\cup G) = \chi_{D}(G)$.

[1]
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz. Number of distinguishing colorings and partitions, Discrete Mathematics, 343(9):111984, (2020).

[2]
M. O. Albertson and K. L. Collins. Symmetry Breaking in Graphs, Electronic Journal of Combinatorics, 3, (1996).

[3]
L. Babai. Asymmetric trees with two prescribed degrees, Acta Mathematica Academiae Scientiarum Hungaricae, 29, no. 1–2, 193–200, (1977).

[4]
L. Babai. Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker’s Conjecture confirmed, Journal of Algebra, 607, 64–106, (2022).

[5]
R. F. Bailey and P. J. Cameron. Base size, metric dimension and other invariants of groups and graphs, Bulletin of the London Mathematical Society, 43(2), 209–242, (2011).

[6]
B. Bollob$\acute{\textmd{a}}$s and N. Sauer. Uniquely colorable graphs with large girth, Canadian Journal of Mathematics, 28, 1340-1344, (1976).

[7]
D. Cartwright and F. Harary. On colorings of signed graphs, Elemente der Mathematik, 23, 85-89, (1968).

[8]
M. Cavers and K. Seyffarth. Graphs with large distinguishing chromatic number, Electronic Journal of Combinatorics, 20(1), (2013), #P19.

[9]
M, Chan. The distinguishing number of the direct product and wreath product action, Journal of Algebraic Combinatorics, 24, 331–345, (2006).

[10]
C.-Y. Chao and Z. Chen. On uniquely 3-colorable graphs, Discrete Mathematics, 112, 21-27, (1993).

[11]
G. Chartrand and P. Zhang. Chromatic Graph Theory, Chapman & Hall/CRC Press, Boca Raton, FL, (2009).

[12]
K. L. Collins and A. N. Trenk. The Distinguishing Chromatic Number, Electronic Journal of Combinatorics,  13, (2006).

[13]
K. L. Collins and A. N. Trenk. The Distinguishing Number and Distinguishing Chromatic Number for Posets, Order, 39, 361–380, (2022).

[14]
D. Erwin and F. Harary. Destroying automorphisms by fixing nodes, Discrete Mathematics, 306(24), 3244–3252, (2006).

[15]
F. Harary, S. T. Hedetnjemi, and R. W. Robinson. Uniquely colorable graphs, Journal of combinatorial theory, 6, 264-270, (1969).

[16]
W. Imrich  and S. Klavžar. Distinguishing Cartesian powers of graphs, Journal of Graph Theory, 53, 250–260, (2006).

[17]
S. Klavžar, T. L. Wong, and X. Zhu. Distinguishing labelings of group action on vector spaces and graphs, Journal of Algebra, 303, 626–641, (2006).

[18]
R. Kalinowski and M. Pilśniak. Proper distinguishing arc-colourings of symmetric digraphs,
Applied Mathematics and Computation, 421, (2022).

[19]
R. Kalinowski, M. Pilśniak and M. Prorok. Distinguishing arc-colourings of symmetric digraphs, The Art of Discrete and Applied Mathematics, 2, P2.04,  (2023).

[20]
F. Lehner, Monika Pilsniak, and Marcin Stawiski. Distinguishing infinite graphs with bounded degrees, Journal of Graph Theory, 101(1):52–65, (2022).

[21]
K. Meslem and E. Sopena. Distinguishing numbers and distinguishing indices of oriented graphs, Discrete Applied Mathematics, 285,  330–342, (2020).

[22]
A. Russell and R. Sundaram. A note on the asymptotics and computational complexity of graph distinguish-ability, Electronic Journal of Combinatorics, 5,  R23, 7 p. (1998).

[23]
M. H. Shekarriz, B. Ahmadi, S. A. Talebpour and M. H. Shirdareh Haghighi. Distinguishing threshold of graphs, (2022)  arXiv:2107.14767

[24]
T. W. Tucker. Distinguishing maps, Electronic Journal of Combinatorics, 18(1), 50-21, (2011).

[25]
J. Tymoczko. Distinguishing numbers for graphs and groups, Electronic Journal of Combinatorics, 11(1), (2004), R63.

[26]
D. B. West. Introduction to Graph Theory, Second Edition. Prentice-Hall, Upper Saddle River, NJ (2001).


# Tomographic imaging of complete quantum state of matter by ultrafast
diffraction

Ming Zhang  State Key Laboratory for Mesoscopic Physics and Collaborative
Innovation Center of Quantum Matter, School of Physics, Peking University,
Beijing 10087, China  Shuqiao Zhang  State Key Laboratory for Mesoscopic
Physics and Collaborative Innovation Center of Quantum Matter, School of
Physics, Peking University, Beijing 10087, China  Haitan Xu  Institute for
Quantum Science and Engineering and Department of Physics, Southern University
of Science and Technology, Shenzhen, 518055, China  Hankai Zhang  State Key
Laboratory for Mesoscopic Physics and Collaborative Innovation Center of
Quantum Matter, School of Physics, Peking University, Beijing 10087, China
Xiangxu Mu  State Key Laboratory for Mesoscopic Physics and Collaborative
Innovation Center of Quantum Matter, School of Physics, Peking University,
Beijing 10087, China  R. J. Dwayne Miller  Departments of Chemistry and
Physics, University of Toronto, Toronto, Ontario M5S 3H6, Canada  Anatoly A.
Ischenko  Lomonosov Institute of Fine Chemical Technologies, RTU-MIREA -
Russian Technological University, Vernadskii Avenue 86, 119571 Moscow, Russia
Oriol Vendrell  Physikalisch-Chemisches Institut, Universität Heidelberg, Im
Neuenheimer Feld 229, D-69120 Heidelberg, Germany  Zheng Li
<EMAIL_ADDRESS>State Key Laboratory for Mesoscopic Physics and
Collaborative Innovation Center of Quantum Matter, School of Physics, Peking
University, Beijing 10087, China

With the ability to directly obtain the Wigner function and density matrix of
photon states, quantum tomography (QT) has had a significant impact on quantum
optics Lvovsky09:RMP299 ; Priebe17:NatPho11 ; Smithey93:PRL1244 , quantum
computing Jianwei12:Science363 ; Laflamme20:Nat59  and quantum information
Murch13:Nat214 ; saglamyurek15:83 . By an appropriate sequence of measurements
on the evolution of each degree of freedom (DOF), the full quantum state of
the observed photonic system can be determined. The first proposal to extend
the application of QT to reconstruction of complete quantum states of matter
wavepackets Leonhardt96:PRL1985  had generated enormous interest in ultrafast
diffraction imaging Yangjie18:Sci64 ; Wolf19:NatChem504 ; ischenko17:CR11066 ;
gao13:343 ; eichberger10:799 ; sciaini09:56 ; mehrabi19:1167 ; ishikawa15:1501
; miller14:6175 ; ernstorfer09:5917 ; siwick03:302 ; wolter16:308  and pump-
probe spectroscopy of molecules Dunn95:PRL884 . This interest was elevated
with the advent of ultrafast electron and X-ray diffraction techniques using
electron accelerators and X-ray free electron lasers to add temporal
resolution to the observed nuclear and electron distributions. In this
respect, quantum tomography holds great promise to enable imaging of molecular
wavefunctions beyond classical description. This concept could become a
natural area for quantum tomography of quantum states of matter
yang12:PRL133202 ; Cosmin12:Nat ; YangJie16:Nat11232 ; Fielding18:Science30 ;
Li19:AP296 ; YangJie16:Nat11232 . However, the great interest in this area has
been tempered by the illustration of an ”impossibility theorem”, known as the
dimension problem Mouritzen05:PRA ; Mouritzen06:JCP244311 . To obtain the
density matrix of a system, the established QT procedure relies on integral
transforms (e.g. the tomographic Radon transform), which preserves
dimensionality Lvovsky09:RMP299 . Unlike its quantum optics sibling, only a
single evolutionary parameter, time, is available for the molecular
wavepacket. Not being able to associate unitary evolution to every DOF of
molecular motion, quantum tomography could not be used beyond 1D and
categorically excludes most vibrational and all rotational motion of
molecules. Here we present a theoretical advance to overcome the notorious
dimension problem. Solving this challenging problem is important to push
imaging molecular dynamics to the quantum limit. The new theory has solved
this problem, which makes quantum tomography a truly useful methodology in
ultrafast physics and enables the making of quantum version of a “molecular
movie” Nango16:Science1552 ; Fielding18:Science30 ; Li19:AP296 ;
Nicholson18:Science821 ; Weinstein12:Nat157 ; gao13:343 ; miller14:6175 ;
Yang20:Sci885 . With the new theory, quantum tomography can be finally
advanced to a sufficient level to become a general method for reconstructing
quantum states of matter, without being limited in one dimension. Our new
concept is demonstrated using a simulated dataset of ultrafast diffraction
experiment of laser-aligned nitrogen molecules YangJie16:Nat11232 . The
analysis with the new method reveals the density matrix of the rotational
wavepacket (schematically shown in Fig. 1), which is otherwise impossible to
obtain with previously established QT procedures. We also show that our
approach can be naturally applied to quantum tomography of vibrational states
to cover the complete DOF of molecular motion, and provides the ultimate
information we can retrieve about dynamics of molecules from a quantum
perspective. This approach can be potentially used in quantum computing and
quantum information whenever quantum state information is tainted by
insufficient evolutionary dimensions or incomplete measurements.

Figure 1:  Schematic drawing of quantum tomography by ultrafast diffraction,
illustrated with a rotational wavepacket of N2 molecule. A rotational
wavepacket is prepared by an impulsive alignment laser pulse
Stapelfeldt03:RMP543 , and probed by diffraction of an incident X-ray pulses
for a series of time intervals. The mixed rotational quantum state represented
by its density operator $\hat{\rho}$ is determined from the diffraction
patterns.

The modern formulation of quantum tomography based on integral transform
Lvovsky09:RMP299 ; Leonhardt96:PRL1985 ; Dunn95:PRL884  conceals its
underlying nature as a retrieval procedure of wavefunction phases lost in the
measurement. Dating back to 1933, Pauli and Feenberg proposed that a
wavefunction $\psi(x,t)=|\psi(x,t)|e^{i\phi(x,t)}$ can be obtained by
measuring the evolution of 1D position probability distribution
$\text{Pr}(x,t)=|\psi(x,t)|^{2}$ and its time derivative
$\partial\text{Pr}(x,t)/\partial t$ for a series of times pauli33 .
Equivalently, a pure quantum state can also be recovered by measuring
$\text{Pr}(x,t)$ at time $t$ and monitoring its evolution over short time
intervals, i.e. $\text{Pr}(x,t+N\Delta t)=|\psi(x,t+N\Delta t)|^{2}$ for
$(N=0,1,2,\cdots)$. Reconstructing the phase of wavefunction can be considered
as the origin of quantum tomography. For a system with Hamiltonian
$\hat{H}=\hat{H}_{0}+\hat{H}_{\text{int}}$, the established 1D QT method makes
use of knowledge of the non-interacting part of the Hamiltonian $\hat{H}_{0}$,
so that its eigenfunctions can be pre-calculated and used in the tomographic
reconstruction of density matrix through integral inversion transform.
However, for higher dimensional QT, the dimension problem as demonstrated in
the pioneering works Mouritzen05:PRA ; Mouritzen06:JCP244311  mathematically
leads to singularity in the inversion from the evolving probability
distribution to the density matrix, namely, failure of quantum tomography.

The fundamental principle of our approach is simple. We solve the QT dimension
problem by exploiting the interaction Hamiltonian $\hat{H}_{\text{int}}$ and
the analogy between QT and crystallographic phase retrieval (CPR)
Rousse01:RMP17  in a seemingly distant field, crystallography. Further
exploiting the interaction Hamiltonian $\hat{H}_{\text{I}}$ provides us a set
of physical conditions, such as the selection rules of transitions subject to
$\hat{H}_{\text{I}}$ and symmetry of the system. These physical conditions can
be imposed as constraints in our QT approach, which is not feasible in the
established QT methods based on integral transform. By compensating with the
additional physical conditions as constraints in the iterative QT procedure,
the converged solution can be obtained as the admissible density matrix that
complies with all the intrinsic properties of the investigated physical
system.

We start by presenting the correspondence between QT and CPR. The research on
CPR has been the focus of crystallography for decades Rousse01:RMP17 ;
Chapman11:Nat73 ; Seibert11:Nat78 ; Yangjie18:Sci64 ; Yang20:Sci885 ;
yang12:PRL133202 . In crystallography, the scattered X-ray or electron wave
encodes the structural information of molecules. The measured X-ray
diffraction intensity is

$\displaystyle I(\textbf{Q})\sim|F(\textbf{Q})|^{2}\,,$ (1)

where $\textbf{Q}=\textbf{k}_{f}-\textbf{k}_{\text{in}}$ is momentum transfer
between incident and diffracted X-ray photon or electron, $F(\textbf{Q})$ is
the electronically elastic molecular form factor. For X-ray diffraction, the
form factor is connected to the electron density by a Fourier transform
$F_{\text{X}}(\textbf{Q})\sim\mathscr{F}[\text{Pr}(\textbf{x})]$,
$\text{Pr}(\textbf{x})$ is the probability density of electrons in a molecule,
and x is the electron coordinate. The form factor of electron diffraction has
a similar expression
$F_{\text{e}}(\textbf{Q})=[\Sigma_{\alpha}N_{\alpha}\exp(i\textbf{Q}\cdot\textbf{R}_{\alpha})-F_{\text{X}}(\textbf{Q})]/Q^{2}$,
where $N_{\alpha}$, $\textbf{R}_{\alpha}$ are the charge and position of
$\alpha^{\text{th}}$ nucleus. However, the phase of the form factor, which is
essential for reconstructing the molecular structure, is unknown in the
diffraction experiment, only the modulus $|F(\textbf{Q})|$ can be obtained
from measured diffraction intensity.

Phase retrieval is a powerful method that prevails in crystallography and
single particle coherent diffraction imaging yang12:PRL133202 ;
Chapman11:Nat73 ; Seibert11:Nat78 . Its basic idea is illustrated in Fig. 2.
Employing projective iterations between real space and Fourier space and
imposing physical constraints in both spaces, the lost phases of the form
factor $F(\textbf{Q})$ can be reconstructed with high fidelity. Fourier space
constraint utilizes measured diffraction intensity data, and real space
constraints comes from a priori knowledge, e.g. the positivity of electron
density.

Figure 2:  Analogy between crystallographic phase retrieval (CPR) and quantum
tomography (QT) based on their common nature pauli33 . The CPR iterative
transform between real space electron density $\text{Pr}(\textbf{x})$ and
Fourier space form factor $F(\textbf{Q})$ is analogously made for QT iterative
transform between blockwise probability distribution
$\text{Pr}_{m_{1},m_{2}}(\theta,t)$ in real space and elements in density
matrix space.

We present the new theory of quantum tomography based on this conceptual
approach by applying it to a rotational wavepacket of nitrogen molecule
prepared by impulsive laser alignment, using the ultrafast X-ray diffraction
data. Quantum tomography of rotational wavepackets is strictly impossible in
the previously established QT theory, because the full quantum state of a
rotating linear molecule is a 4D object
$\langle\theta,\phi|\hat{\rho}|\theta^{\prime},\phi^{\prime}\rangle$, while
the measured probability density evolution $\text{Pr}(\theta,\phi,t)$ is only
3D. It is obvious that the inversion problem to obtain the density matrix is
not solvable by dimensionality-preserving transform.

From a dataset consisting of a series of time-ordered snapshots of diffraction
patterns HO08:PRA052409

$\displaystyle I(\textbf{Q},t)=\int_{0}^{2\pi}d\phi\int_{0}^{\pi}\sin\theta
d\theta\text{Pr}(\theta,\phi,t)|F(\textbf{Q},\theta,\phi)|^{2}\,,$ (2)

the time-dependent molecular probability distribution
$\text{Pr}(\theta,\phi,t)$ can be obtained by solving the Fredholm integral
equation of the first kind (see Supplementary Information section 1 for
details).

Figure 3: Probability distribution and diffraction pattern of rotational
wavepacket. The first row shows the initial angular probability for N2
molecules prepared at rotational temperature of 30K and the expectation values
of $\cos^{2}\theta$ of the time evolving wavepacket for N2 molecules after
laser pulse Stapelfeldt03:RMP543 . The alignment laser pulse is linearly
polarized with a Gaussian envelope of duration $\tau_{L}=50$fs and
$10^{13}$W/cm2 peak intensity, and $\theta$ is the polar angle between the
polarization and the molecular axes. The duration is much shorter than the
characteristic rotational time $\tau_{L}\ll T$. The second and third rows show
the angular probability distribution changes from aligned to anti-aligned, and
the difference of their diffraction intensity with respect to $t=0$ shown in
Fig. 1. The X-ray photon energy is assumed to be 20keV.

The probability distribution of rotational wavepacket is

$\displaystyle\text{Pr}(\theta,\phi,t)=\sum_{J_{1}m_{1}}\sum_{J_{2}m_{2}}\langle
J_{1}m_{1}|\hat{\rho}|J_{2}m_{2}\rangle
Y_{J_{1}m_{1}}(\theta,\phi)Y_{J_{2}m_{2}}^{*}(\theta,\phi)e^{-i\Delta\omega
t}\,,$ (3)

where $\Delta\omega=E_{J_{1}}-E_{J_{2}}$ is the energy spacing of rotational
levels. As shown in Fig. 2, we devise an iterative procedure to connect the
spaces of density matrix and temporal wavepacket density.

For the system of rotating molecules, the dimension problem limits the
invertible mapping between density matrix and temporal wavepacket density to
the reduced density of fixed projection quantum numbers $m_{1}$, $m_{2}$,

$\displaystyle\text{Pr}_{m_{1},m_{2}}(\theta,t)=\sum_{J_{1}J_{2}}\langle
J_{1}m_{1}|\hat{\rho}|J_{2}m_{2}\rangle\tilde{P}_{J_{1}}^{m_{1}}(\cos\theta)\tilde{P}_{J_{2}}^{m_{2}}(\cos\theta)e^{-i\Delta\omega
t}\,.$ (4)

The analytical solution of the inverse mapping from
$\text{Pr}_{m_{1},m_{2}}(\theta,t)$ to density matrix $\langle
J_{1}m_{1}|\hat{\rho}|J_{2}m_{2}\rangle$ is elaborated in the Supplementary
Information section 2. However, due to the dimension problem, there is no
direct way to obtain $\text{Pr}_{m_{1},m_{2}}(\theta,t)$ from the measured
wavepacket density, only their sum is traceable through
$\sum_{m_{1},m_{2}}\delta_{m_{1}-m_{2},k}\text{Pr}_{m_{1},m_{2}}(\theta,t)=\frac{1}{2\pi}\int_{0}^{2\pi}\text{Pr}(\theta,\phi,t)e^{ik\phi}d\phi$.

Our method starts from an initial guess of density matrix and an iterative
projection algorithm is used to impose constraints in the spaces of density
matrix and spatial probability density. The initial guess of quantum state,
$\hat{\rho}_{\text{ini}}=\sum_{J_{0}m_{0}}\omega_{J_{0}}|J_{0}m_{0}\rangle\langle
J_{0}m_{0}|$, is assumed to be an incoherent state in the thermal equilibrium
of a given rotational temperature, which can be experimentally determined
YangJie16:Nat11232 . $\omega_{J_{0}}=\frac{1}{Z}g_{J_{0}}e^{-\beta E_{J_{0}}}$
is the Boltzmann weight, and $g_{J_{0}}$ represents the statistical weight of
nuclear spin, for the bosonic 14N2 molecule, $g_{J_{0}}$ is 6 for even $J_{0}$
(spin singlet and quintet) and 3 for odd $J_{0}$ (spin triplet).

In the probability density space, constraint is imposed by uniformly scaling
each reduced density $\text{Pr}_{m_{1},m_{2}}(\theta,t)$ with the measured
total density $\text{Pr}(\theta,\phi,t)$. Constraints in the density matrix
space enable us to add all known properties of a physical state to the QT
procedure, which supply additional information to compensate the missing
evolutionary dimensions. The constraints contain general knowledge of the
density matrix, i.e. the density matrix is positive semidefinite, Hermitian
and with a unity trace. Besides, the selection rules of the alignment laser-
molecule interaction imply further constraints on physically nonzero
$m$-blocks of the density matrix and invariant partial traces of density
matrix elements subject to rotational quantum number $J$ (see Supplementary
Information section 3 for details of the algorithm).

Figure 4: Quantum tomography of rotational wavepacket of nitrogen molecule.
The modulus and phases of density matrix elements are shown in the upper and
middle panel, within each $m$-block $J=|m|,|m|+1,\cdots,J_{\text{max}}$
(phases are at $t=0$). The density matrix element of opposite magnetic quantum
number $m$ and $-m$ are identical (see Supplementary Information section 3).
The lower panel shows the wavepacket probability distribution
$\text{Pr}(\theta,t)$. The convergence of the procedure is illustrated in the
rightmost column.

We demonstrate the capability of the new approach to recover the density
matrix despite the dimension problem. We use simulated ultrafast diffraction
dataset of impulsively aligned nitrogen molecule, prepared at rotational
temperature of 30 K. The order of the recovered density matrix sets the
requirement on the resolution. From Eq. 4, the characteristic time scale of
rotation is $\frac{2\mathcal{I}}{|\beta|(\alpha+1)}$, where $\mathcal{I}$ is
the moment of inertia of nitrogen molecule, $\alpha$ and $\beta$ are two
integral parameters satisfying $\beta(\alpha+1)=\Delta J(J+1)$ and $|\Delta
J|\leq|\beta|\leq\alpha\leq J$ where $\Delta J=J_{1}-J_{2}$ and
$J=J_{1}+J_{2}$ for any two eigenstates with $J_{1},J_{2}$ (see Supplementary
Information section 2). Using the Nyquist–Shannon sampling theorem, the
required temporal resolution $\delta t$ should be $\delta
t\leq\frac{\mathcal{I}}{|\beta|(\alpha+1)}$. The spatial resolution
$\delta\theta$ and $\delta\phi$ can be determined with the argument that the
nodal structure of spherical harmonic basis in Eq. 3 must be resolved, i.e.
$\delta\theta<\frac{\pi}{2J_{\text{max}}}$. To recover density matrix up to
the order $J_{\text{max}}=5$, it demands time resolution $\delta t\lesssim
10^{2}$ fs and spatial resolution $\delta\theta\lesssim 10^{-1}$ rad. Quantum
tomography of the rotational wavepacket gives the result shown in Fig. 4.
After 50 iterations, both density matrix and probability distribution are
precisely recovered. The error of density matrix is
$\epsilon_{50}(\hat{\rho})=2.9\times 10^{-2}$ and error of probability
achieves $\epsilon_{50}(\text{Pr})=3.8\times 10^{-5}$.

Figure 5: Quantum tomography of vibrational state. The iterative transform is
again between the spaces of density matrix and the blockwise probability
distribution
$\text{Pr}_{\Delta_{1},\Delta_{2},\cdots,\Delta_{N}}(x_{1},x_{2},\cdots,x_{N})$.

The new quantum tomography procedure can be straightforwardly extended to
obtain quantum state of vibrational wavepacket, which suffers from the
dimension problem as well, when more than one vibrational modes are involved.
By ultrafast diffraction technique, we can measure the joint spatial
probability density of $N$ vibrational modes for different time $t$
Ischenko14:Adv . This gives an $(N+1)$-dimensional probability density
$\text{Pr}(x_{1},x_{2},\cdots,x_{N},t)$, where $x_{i}$’s are the spatial
coordinates of vibrational eigenmodes. The density matrix of the quantum state
is however a $2N$-dimensional object $\langle n_{1}n_{2}\cdots
n_{N}|\hat{\rho}|m_{1}m_{2}\cdots m_{N}\rangle$ in the eigenmode basis, which
cannot be obtained by dimensionality-preserving transform for $N>1$ (detailed
proof is presented in Supplementary Information section 6).

The new approach provides a similar iterative quantum tomography procedure for
vibrational wavepacket, with the capability to extract the vibrational density
matrix $\langle n_{1}n_{2}\cdots n_{N}|\hat{\rho}|m_{1}m_{2}\cdots
m_{N}\rangle$ from the lower dimensional wavepacket density evolution
$\text{Pr}(x_{1},x_{2},\cdots,x_{N},t)$. The density matrix of vibrational
wavepacket is to be recovered from the probability distribution

$\displaystyle\text{Pr}(x_{1},x_{2},\cdots,x_{N},t)=\sum_{\\{m_{i}\\}_{i=1}^{N}}\sum_{\\{n_{i}\\}_{i=1}^{N}}\langle
n_{1}n_{2}\cdots n_{N}|\hat{\rho}|m_{1}m_{2}\cdots m_{N}\rangle$ (5)
$\displaystyle\times\prod_{i=1}^{N}\phi_{n_{i}}(x_{i})\phi^{*}_{m_{i}}(x_{i})e^{i(m_{i}-n_{i})\omega_{i}t}$

where $\omega_{i}$ and $\phi_{n_{i}}(x_{i})$ are frequency and eigenstate of
$n_{i}$-th vibrational mode. Again, the dimension problem restricts the
integral transformation between probability and density matrix in a subspace,
in which the difference between two quantum numbers $\Delta_{i}$ of each
vibrational mode is fixed

$\displaystyle\text{Pr}_{\Delta_{1},\Delta_{2},\cdots,\Delta_{N}}(x_{1},x_{2},\cdots,x_{N})$
$\displaystyle=$
$\displaystyle\sum_{\\{m_{i}\\}_{i=1}^{N}}\sum_{\\{n_{i}\\}_{i=1}^{N}}\langle
n_{1}n_{2}\cdots n_{N}|\hat{\rho}|m_{1}m_{2}\cdots m_{N}\rangle$
$\displaystyle\times\prod_{i=1}^{N}\phi_{n_{i}}(x_{i})\phi^{*}_{m_{i}}(x_{i})\delta_{m_{i}-n_{i},\Delta_{i}}$
$\displaystyle\langle n_{1}n_{2}\cdots n_{N}|\hat{\rho}|m_{1}m_{2}\cdots
m_{N}\rangle$ $\displaystyle=$ $\displaystyle\int
d^{N}\textbf{x}\text{Pr}_{\Delta_{1},\Delta_{2},\cdots,\Delta_{N}}(x_{1},x_{2},\cdots,x_{N})\times\prod_{i=1}^{N}f_{m_{i}n_{i}}(x_{i})$
(7)

where the sampling functions $f_{mn}(x)$ are derivation of product of regular
and irregular wavefunctions Leonhardt96:PRL1985 , which is bi-orthogonal to
both $\phi_{m}(x)$ and $\phi_{n}(x)$ provided the frequency constraint. Then
effective constraints can be imposed by iterative projection method to get the
converged result satisfying physical condition in the density matrix and
probability density spaces. For example, the information of measurable
probability distribution makes up of the following constraint

$\displaystyle\sum_{\\{\Delta_{i}\\}_{i=1}^{N}}\text{Pr}_{\Delta_{1},\Delta_{2},\cdots,\Delta_{N}}(x_{1},x_{2},\cdots,x_{N})\delta_{\sum_{i=1}^{N}\Delta_{i}r_{i},k}=\frac{1}{T}\int_{0}^{T}dte^{-ik\omega_{0}t}\text{Pr}(x_{1},x_{2},\cdots,x_{N},t)$
(8)

where we assume $\omega_{i}=r_{i}\omega_{0}$ ($r_{i}$ are integers and
$T={2\pi}/{\omega_{0}}$). To determine density matrix for vibrational
wavepackets up to $N$th order, it demands measurement with
$\delta{x}\leq\pi/2\sqrt{2N+1}$ and $\delta{t}\leq
T/2(N+1)\Sigma_{i}r_{i}$(see Supplementary Information section 6). This leads
to the requirement of spatial temporal resolution of $\delta{x}\sim 1$pm and
$\delta{t}\sim 10$fs, which sets an ultimate demand for resolution in
ultrafast diffraction.

The resemblance between the vibration and rotation problem proves the
generality of our method, and sets up solid foundation to solve other quantum
tomography problems as well as its application in relevant experiments.

In summary, we have demonstrated a new iterative quantum tomography approach
that is capable of extracting the density matrix of high-dimensional
wavepacket of matter from its evolutionary probability distribution in time.
The notorious dimension problem, which has prohibited for almost two decades
the quantum tomographic reconstruction of molecular quantum state from
ultrafast diffraction, has been finally resolved. We expect this advance to
have a broad impact in many areas of science and technology, not only for
making the quantum version of molecular movie, but also for quantum state
measurement in condensed matter physics, quantum computing and quantum
information with imperfect knowledge of phase information, e.g. due to
incomplete measurement for the sake of speed and efficiency.

##  .1 Acknowledgements

We thank Jie Yang and Stefan Pabst for useful discussions. This work was
supported by NSFC Grant No. 11974031, funding from state key laboratory of
mesoscopic physics and RFBR Grant No. 20-02-00146.

##  .2 Author Contribution

Z.L. designed the study. M.Z., S.Q.Z., H.K.Z. and Z.L. carried out the
calculations. M.Z., S.Q.Z., H.K.Z., X.X.M., H.T.X., O.V., R.J.D.M., A.I. and
Z.L. analysed the data. All authors contributed to the writing of the
manuscript.

## References

  * (1) Lvovsky, A. I. & Raymer, M. G.  Continuous-variable optical quantum state tomography.  _Rev. Mod. Phys._ 81, 299–332 (2009).
  * (2) Priebe, K. E. _et al._ Attosecond electron pulse trains and quantum state reconstruction in ultrafast transmission electron microscopy.  _Nature Photonics_ 11, 793–797 (2017).
  * (3) Smithey, D., Beck, M., Raymer, M. & Faridani, A.  Measurement of the Wigner distribution and the density matrix of a light mode using optical homodyne tomography: Application to squeezed states and the vacuum.  _Phys. Rev. Lett._ 70, 1244 (1993).
  * (4) Cai, X. _et al._ Integrated compact optical vortex beam emitters.  _Science_ 338, 363–366 (2012).
  * (5) Laflamme, R. _et al._ Interpretation of tomography and spectroscopy as dual forms of quantum computation.  _Nature_ 418, 59–62 (2002).
  * (6) Murch, K. W., Weber, S. J., Macklin, C. & Siddiqi, I.  Observing single quantum trajectories of a superconducting quantum bit.  _Nature_ 502, 211–214 (2013).
  * (7) Saglamyurek, E. _et al._ Quantum storage of entangled telecom-wavelength photons in an erbium-doped optical fibre.  _Nature Photonics_ 9, 83–87 (2015).
  * (8) Leonhardt, U. & Raymer, M. G.  Observation of moving wave packets reveals their quantum state.  _Phys. Rev. Lett._ 76, 1985 (1996).
  * (9) Yang, J. _et al._ Imaging cf3i conical intersection and photodissociation dynamics with ultrafast electron diffraction.  _Science_ 361, 64–67 (2018).
  * (10) Wolf, T. _et al._ The photochemical ring-opening of 1,3-cyclohexadiene imaged by ultrafast electron diffraction.  _Nature Chem._ 11, 504–509 (2019).
  * (11) Ischenko, A. A., Weber, P. M. & Miller, R. J. D.  Capturing chemistry in action with electrons: realization of atomically resolved reaction dynamics.  _Chem. Rev._ 117, 11066–11124 (2017).
  * (12) Gao, M. _et al._ Mapping molecular motions leading to charge delocalization with ultrabright electrons.  _Nature_ 496, 343–346 (2013).
  * (13) Eichberger, M. _et al._ Snapshots of cooperative atomic motions in the optical suppression of charge density waves.  _Nature_ 468, 799–802 (2010).
  * (14) Sciaini, G. _et al._ Electronic acceleration of atomic motions and disordering in bismuth.  _Nature_ 458, 56–59 (2009).
  * (15) Mehrabi, P. _et al._ Time-resolved crystallography reveals allosteric communication aligned with molecular breathing.  _Science_ 365, 1167–1170 (2019).
  * (16) Ishikawa, T. _et al._ Direct observation of collective modes coupled to molecular orbital–driven charge transfer.  _Science_ 350, 1501–1505 (2015).
  * (17) Miller, R. J. D.  Femtosecond crystallography with ultrabright electrons and X-rays: Capturing chemistry in action.  _Science_ 343, 1108–1116 (2014).
  * (18) Ernstorfer, R. _et al._ The formation of warm dense matter: experimental evidence for electronic bond hardening in gold.  _Science_ 323, 1033–1037 (2009).
  * (19) Siwick, B. J., Dwyer, J. R., Jordan, R. E. & Miller, R. J. D.  An atomic-level view of melting using femtosecond electron diffraction.  _Science_ 302, 1382–1385 (2003).
  * (20) Wolter, B. _et al._ Ultrafast electron diffraction imaging of bond breaking in di-ionized acetylene.  _Science_ 354, 308–312 (2016).
  * (21) Dunn, T. J., Walmsley, I. A. & Mukamel, S.  Experimental determination of the quantum-mechanical state of a molecular vibrational mode using fluorescence tomography.  _Phys. Rev. Lett._ 74, 884–887 (1995).
  * (22) Hensley, C. J., Yang, J. & Centurion, M.  Imaging of isolated molecules with ultrafast electron pulses.  _Phys. Rev. Lett._ 109, 133202 (2012).
  * (23) Blaga, C. I. _et al._ Imaging ultrafast molecular dynamics with laser-induced electron diffraction.  _Nature_ 483, 194–197 (2012).
  * (24) Yang, J., Guehr, M., Vecchione, T., Robinson, M. S. & Wang, X.  Diffractive imaging of a rotational wavepacket in nitrogen molecules with femtosecond megaelectronvolt electron pulses.  _Nature Commun._ 7, 11232 (2016).
  * (25) Fielding, H. H.  Molecular movies filmed at conical intersections.  _Science_ 361, 30–31 (2018).
  * (26) Li, Z., Gyawali, S., Ischenko, A. A., Hayes, S. & Miller, R. J. D.  Mapping atomic motions with electrons: Toward the quantum limit to imaging chemistry.  _ACS Photonics_ 7, 296–320 (2019).
  * (27) Mouritzen, A. S. & Mølmer, K.  Tomographic reconstruction of quantum states in $N$ spatial dimensions.  _Phys. Rev. A_ 73, 042105 (2006).
  * (28) Mouritzen, A. S. & Mølmer, K.  Quantum state tomography of molecular rotation.  _J. Chem. Phys._ 124, 244311 (2006).
  * (29) Nango, E. _et al._ A three-dimensional movie of structural changes in bacteriorhodopsin.  _Science_ 354, 1552–1557 (2016).
  * (30) Nicholson, C. W. _et al._ Beyond the molecular movie: Dynamics of bands and bonds during a photoinduced phase transition.  _Science_ 362, 821–825 (2018).
  * (31) Weinstein, J. A. & Hunt, N. T.  Ultrafast chemical physics: In search of molecular movies.  _Nature Chem._ 4, 157–158 (2012).
  * (32) Yang, J. _et al._ Simultaneous observation of nuclear and electronic dynamics by ultrafast electron diffraction.  _Science_ 368, 885 (2020).
  * (33) Stapelfeldt, H. & Seideman, T.  Colloquium: Aligning molecules with strong laser pulses.  _Rev. Mod. Phys._ 75, 543–557 (2003).
  * (34) Pauli, W.  _Handbook of Physics_ (Springer Verlag, 1933).
  * (35) Rousse, A., Rischel, C. & Gauthier, J.-C.  Femtosecond X-ray crystallography.  _Rev. Mod. Phys._ 73, 17–31 (2001).
  * (36) Chapman, H. N. _et al._ Femtosecond X-ray protein nanocrystallography.  _Nature_ 470, 73 (2011).
  * (37) Seibert, M. M. _et al._ Single mimivirus particles intercepted and imaged with an X-ray laser.  _Nature_ 470, 78 (2011).
  * (38) Ho, P. J. & Santra, R.  Theory of X-ray diffraction from laser-aligned symmetric-top molecules.  _Phys. Rev. A_ 78, 053409 (2008).
  * (39) Ischenko, A. A. & Aseyev, S. A.  _Time-resolved Electron Diffraction: For Chemistry, Biology and Materials Science_ , vol. 184 of _Advances in Imaging and Electron Physics_ (Academic Press, 2014).

See pages 1 of supplementary_information.pdf See pages 2 of
supplementary_information.pdf See pages 3 of supplementary_information.pdf See
pages 4 of supplementary_information.pdf See pages 5 of
supplementary_information.pdf See pages 6 of supplementary_information.pdf See
pages 7 of supplementary_information.pdf See pages 8 of
supplementary_information.pdf See pages 9 of supplementary_information.pdf See
pages 10 of supplementary_information.pdf See pages 11 of
supplementary_information.pdf See pages 12 of supplementary_information.pdf
See pages 13 of supplementary_information.pdf See pages 14 of
supplementary_information.pdf See pages 15 of supplementary_information.pdf
See pages 16 of supplementary_information.pdf See pages 17 of
supplementary_information.pdf See pages 18 of supplementary_information.pdf
See pages 19 of supplementary_information.pdf See pages 20 of
supplementary_information.pdf See pages 21 of supplementary_information.pdf