# Distinguishing threshold for some graph operations

M.H. Shekarriz<EMAIL_ADDRESS>Department of Mathematics, Yazd
University, 89195-741, Yazd, Iran.  S.A. Talebpour
<EMAIL_ADDRESS>Department of Mathematics, Shiraz
University, Shiraz, Iran  B. Ahmadi<EMAIL_ADDRESS>Department of
Mathematics, Shiraz University, Shiraz, Iran  M.H. Shirdareh Haghighi
<EMAIL_ADDRESS>Department of Mathematics, Shiraz University, Shiraz,
Iran  S. Alikhani<EMAIL_ADDRESS>Department of Mathematics, Yazd
University, 89195-741, Yazd, Iran.

###### Abstract

A vertex coloring of a graph $G$ is distinguishing if non-identity
automorphisms do not preserve it. The distinguishing number, $D(G)$, is the
minimum number of colors required for such a coloring and the distinguishing
threshold, $\theta(G)$, is the minimum number of colors $k$ such that any
arbitrary $k$-coloring is distinguishing. Moreover, $\Phi_{k}(G)$ is the
number of distinguishing coloring of $G$ using at most $k$ colors. In this
paper, for some graph operations, namely, vertex-sum, rooted product, corona
product and lexicographic product, we find formulae of the distinguishing
number and threshold using $\Phi_{k}(G)$.

Keywords: distinguishing coloring, distinguishing threshold, graph product,
vertex-sum

Mathematics Subject Classification: 05C09, 05C15, 05C30, 05C76

##  1 Introduction

A Graph’s symmetry is called an _automorphism_. A vertex coloring of a graph
is said to be _distinguishing_ (aka symmetry breaking) if the identity is the
only automorphism that preserves it. The _distinguishing number_ of a graph
$G$, denoted by $D(G)$, is the smallest number of colors required for such a
coloring. For a positive integer $d$, if $G$ can be distinguishingly colored
by $d$ colors, we say that $G$ is $d$-distinguishable. Obviously, if a graph
$G$ is asymmetric, that is, if $\mathrm{Aut}(G)=\\{\text{\rm id}\\}$, then
$D(G)=1$. Furthermore, it is easy to verify that $D(K_{n})=n$,
$D(K_{n,n})=n+1$, $D(P_{n})=2$, for $n\geq 2$, $D(C_{n})=2$, for $n\geq 6$,
while $D(C_{3})=D(C_{4})=D(C_{5})=3$ [2].

The concept is not new and dates back to 1970s, when Babai considered it for
the first time [7]. However, after appearance of [2] by Albertson and Collins
in 1996, the concept captured a lot of interests and large number of novel
methods and results were introduced to the community. Here we only mention
those that are related to our results.

Collins and Trenk [10], and independently Klavžar, Wong and Zhu [19], showed
that $D(G)\leq\Delta+1$, where $\Delta$ is the maximum degree of a connected
graph $G$. Moreover, the inequality turns into equality if and only if $G$ is
either the complete graph $K_{\Delta}$, the complete bipartite graph
$K_{\Delta,\Delta}$ or the cycle of length 5.

A big portion of results in the literature is about product graphs. For
example, the hypercubes $Q_{k}$, for $k\geq 4$, which are the Cartesian powers
of $P_{2}$, are shown to be 2-distinguishable by Bogstad and Cowen [9]. Imrich
and Klavžar in [18] generalized this result by showing that, except for some
small graphs, the distinguishing number of any Cartesian power of a connected
graph is 2. Moreover, the Cartesian products of relatively prime graphs, whose
sizes are close to each other, are shown to be distinguishable by a small
number of colors by Imrich, Jerebic and Klavžar [17]. Furthermore, Estaji et
al. in [12] showed that two colors is enough to distinguish $G\square H$, for
every pair of connected graphs $G$ and $H$, with $|H|\leq|G|<2^{|H|}-|H|$,
where $|X|$ is the number of vertices of the graph $X$.

The _corona product_ was also studied for their distinguishing indices by
Alikhani and Soltani in [4]. We will remind their results in Section 5. The
_lexicographic product_ , is another interesting graph operation from symmetry
breaking point of view. Alikhani and Soltani showed in another paper [5] that
under some conditions on the automorphism group of a graph $G$, we have
$D(G)\leq D(G^{k})\leq D(G)+k-1$, where $G^{k}$ is the $k$’th lexicographic
power of $G$. Moreover they showed that if $G$ and $H$ are connected, then
$D(H)\leq D(G\circ H)\leq|G|\cdot D(H)$, where $G\circ H$ stands for the
lexicographic product of $G$ and $H$.

In order to accurately calculate the distinguishing number of the
lexicographic product, $D(G\circ H)$, Ahmadi, Alinaghipour and Shekarriz [1]
defined some indices such as $\Phi_{k}(G)$, which stands for the number of
non-equivalent distinguishing colorings of the graph $G$ with at most $k$
colors. They proved that $D(G\circ H)=k$, where $k$ is the least integer such
that $\Phi_{k}(H)\geq D(G)$, provided that the automorphisms of $G\circ H$ are
all natural, i.e., the automorphisms that keep the product’s skeleton [15].

To overcome some computation difficulties, the authors of [1] further defined
the distinguishing threshold $\theta(G)$ as the minimum number $k$ of colors
such that any coloring of the graph $G$ with $k$ colors is distinguishing.
They showed that $\theta(K_{n})=\theta(\overline{K_{n}})=n$,
$\theta(K_{m,n})=m+n$, $\theta(P_{n})=\lceil\frac{n}{2}\rceil+1$, for $n\geq
2$, and $\theta(C_{n})=\lfloor\frac{n}{2}\rfloor+2$, for $n\geq 3$. Moreover,
for $n\geq 5$, they proved that $\theta(K(n,2))=\frac{1}{2}(n^{2}-3n+6)$,
where $K(n,k)$ stands for the Kneser graph. Calculating this index for several
classes of product graphs is one of our intentions throughout this paper.

The distinguishing threshold turns out to be an interesting index on its own.
Shekarriz et al. [21] considered this index more thoroughly. They proved that
this index is related to the cycle structure of the automorphisms of the
graph. They also showed that $\theta(G)=2$ if and only if $|G|=2$. Moreover,
they studied graphs whose distinguishing threshold is 3 and graphs with
$D(G)=\theta(G)$. Furthermore, they considered the distinguishing threshold
for graphs in the Johnson scheme.

The distinguishing threshold for the Cartesian product of connected graphs has
recently been studied. Alikhani and Shekarriz [3] showed that when
$G=G_{1}\square G_{2}\square\ldots\square G_{k}$ is a prime factorization to
mutually non-isomorphic connected graphs, we have

$\theta(G)=\max\left\\{\left(\theta(G_{i})-1\right)\cdot\frac{|G|}{|G_{i}|}\;:\;i=1,\dots,k\right\\}+1.$

Meanwhile, they showed that when $G$ is a connected prime graph and $k\geq 2$
is a positive integer, we have

$\theta(G^{k})=|G|^{k-1}\cdot\max\left\\{\frac{|G|+1}{2},\left(\theta(G)-1\right)\right\\}+1,$

where $G^{k}$ is the $k$th Cartesian power of $G$.

There are still some interesting graph operations whose symmetry breaking
indices are yet to be calculated. The _vertex-sum_ , whose definition is
mentioned in Section 3, is one of these operations. For some results on this
graph operation, the reader may refer, for example, to [8, 16]. We found this
operation interesting enough to be considered for their symmetry breaking
indices.

We start our study by first recalling some fundamental results in Section 2.
Vertex-sum graphs are studied for breaking their symmetries in Section 3. The
distinguishing number and the distinguishing threshold for the rooted products
are considered in Section 4 after considering their automorphism groups. For
the corona products in Section 5, we not only refine Alikhani and Soltani’s
result in [4] by exactly calculating their distinguishing number, but also
calculate their distinguishing threshold. Finally, the distinguishing
threshold of the lexicographic product graphs is evaluated in Section 6.

All graphs in this paper are assumed to be finite and simple, and the groups
are finite. Undefined concepts and notation can be found in [11] by Diestel.

##  2 Preliminaries

Two colorings $c_{1}$ and $c_{2}$ of a graph $G$ are said to be equivalent if
there is an automorphism $\alpha\in\mathrm{Aut}(G)$ such that
$c_{1}(v)=c_{2}(\alpha(v))$, for all $v\in V(G)$. The number of non-equivalent
distinguishing colorings of $G$ with colors from the set $\\{1,\ldots,k\\}$ is
shown by $\Phi_{k}(G)$, while $\varphi_{k}(G)$ stands for the number of non-
equivalent $k$-distinguishing colorings of $G$ (i.e., the number of non-
equivalent colorings which use exactly $k$ colors) [1]. The following formula
reveals the relationship between these two indices:

$\Phi_{k}(G)=\sum_{i=D(G)}^{k}{k\choose i}\varphi_{i}(G).$

Using simple counting argument, it can easily be shown that for $n,k\geq 1$ we
have

$\Phi_{k}(P_{n})=\frac{1}{2}(k^{n}-k^{\lceil\frac{n}{2}\rceil}),$ (2.1)

and $\Phi_{k}(K_{n})={k\choose n}$ when $n\geq 2$ and $k\geq n$ [1].

Knowing the distinguishing threshold of a graph $G$ makes calculations of
$\varphi_{k}(G)$ easier when $k$ is large enough: when every $k$-coloring of
$G$ is distinguishing, i.e., when $k\geq\theta(G)$, we have

$\varphi_{k}(G)=\frac{k!\genfrac{\\{}{\\}}{0.0pt}{}{n}{k}}{|\mathrm{Aut}(G)|},$
(2.2)

where $\genfrac{\\{}{\\}}{0.0pt}{}{n}{k}$ denotes the Stirling number of the
second kind [1].

When $G$ is a disconnected graph, its distinguishing threshold is given by the
following theorem. To state it, we will follow the notation from [21]. Suppose
that $G$ is a graph with connected components $G_{1},\ldots,G_{k}$, where all
$G_{i}$ are asymmetric. Then, we consider the isomorphism congruence classes
$\mathcal{C}_{1},\ldots,\mathcal{C}_{m}$ of the graphs $G_{1},\ldots,G_{k}$,
where we assume that the $\mathcal{C}_{j}$’s are increasingly ordered in the
sense that if $j<\ell$, and $G_{i_{j}}\in\mathcal{C}_{j}$ and
$G_{i_{\ell}}\in\mathcal{C}_{\ell}$, then $|G_{i_{j}}|\leq|G_{i_{\ell}}|$.
Define $\nu(G)$ to be $|G_{i_{s}}|$, where $G_{i_{s}}\in\mathcal{C}_{s}$ and
$s$ is the smallest integer with the property that $|\mathcal{C}_{s}|>1$; and
if there is no such $s$, then define $\nu(G)$ to be $|G|$. Note that, for
example, if $k=1$ (i.e., if $G$ is a connected asymmetric graph), then
$\nu(G)=|G|$.

######  Theorem 2.1.

[21] Let $G_{1},\ldots,G_{k}$ be arbitrary connected graphs and let
$G=\cup_{i=1}^{k}G_{i}$.

  1. (a)

If $\mathrm{Aut}(G_{i})\neq\\{\mathrm{id}\\}$, for all $1\leq i\leq n$, then

$\theta(G)=\max_{1\leq i\leq k}\;\left\\{\theta(G_{i})+\sum_{j\neq
i}|G_{j}|\right\\}.$

  2. (b)

If $\mathrm{Aut}(G_{i})=\\{\mathrm{id}\\}$, for all $1\leq i\leq k$, then
$\theta(G)=|G|-\nu(G)+1$.

  3. (c)

If $\\{1,\ldots,k\\}=A\cup B$ is a non-trivial partition,
$\mathrm{Aut}(G_{i})\neq\\{\mathrm{id}\\}$, for $i\in A$, and
$\mathrm{Aut}(G_{i})=\\{\mathrm{id}\\}$, for $i\in B$, then set
$G_{A}=\bigcup_{i\in A}G_{i}$ and $G_{B}=\bigcup_{i\in B}G_{i}$. In this case,
we have

$\theta(G)=\max\\{\theta(G_{A})+|G_{B}|,\;\theta(G_{B})+|G_{A}|\\},$

unless $G_{B}$ is asymmetric and
$\theta(G_{A})+|G_{B}|\leq\theta(G_{B})+|G_{A}|$, in which case we have
$\theta(G)=\theta(G_{A})+|G_{B}|$.∎

It was mentioned in the introduction that the distinguishing threshold of a
graph $G$ is related to the cycle structure of its automorphism group
$\mathrm{Aut}(G)$. Formally, when $\alpha\in\mathrm{Aut}(G)$ and $v\in G$, the
ordered tuple $\sigma=(v,\alpha(v),\alpha^{2}(v),\ldots,\alpha^{r-1}(v))$
forms a cycle of length $r$ provided that $r$ is the smallest integer such
that $\alpha^{r}(v)=v$. Note that a length-one cycle $(v)$ fixes the vertex
$v$ and that the order $o(\sigma)$ of a cycle $\sigma$ in the automorphism
group is the length of $\sigma$. Following the notation of [21], we denote the
number of cycles of an automorphism $\alpha$ by $|\alpha|$. For example if
$\alpha=(13)(45)$ is an automorphism of a graph $G$ with
$V(G)=\\{1,\ldots,5\\}$, then $|\alpha|=3$. Then, the distinguishing threshold
is given by the following lemma.

######  Lemma 2.2.

[21] For any graph $G$, we have
$\theta(G)=\max\left\\{|\alpha|\;:\;\alpha\in\mathrm{Aut}(G)-\\{\mathrm{id}\\}\right\\}+1$.

##  3 Vertex-sum

In this section, we focus on the distinguishing number and the distinguishing
threshold of some vertex-sum graphs. Given disjoint graphs
$G_{1},\ldots,G_{k}$ with $u_{i}\in V(G_{i})$, $i=1,\ldots,k$, the vertex-sum
of $G_{1},\ldots,G_{k}$, at the vertices $u_{1},\ldots,u_{k}$, is the graph
$G_{1}\makebox[0.0pt][l]{$+$}\raisebox{-3.22916pt}{\makebox[8.61108pt]{${}_{u}$}}G_{2}\makebox[0.0pt][l]{$+$}\raisebox{-3.22916pt}{\makebox[8.61108pt]{${}_{u}$}}\cdots\makebox[0.0pt][l]{$+$}\raisebox{-3.22916pt}{\makebox[8.61108pt]{${}_{u}$}}G_{k}$
obtained from $G_{1},\ldots,G_{k}$ by identifying the vertices $u_{i}$,
$i=1,\ldots,k$, as the same vertex $u$. This definition is from [8] by
Barioli, Fallat and Hogben. We call $u$ the central vertex of the vertex-sum.
The vertex-sum of $t$ copies of a graph $G$ at a vertex $u$ is denoted by
$G_{u}^{t}$, $t\geq 2$. For the sake of simplicity, we may assume that the
vertex $u$ belongs to all the $G_{i}$.

Recall that when a group $\Gamma$ acts on a set $X$ and $x\in X$,
$\mathrm{Stab}_{\Gamma}(x)$ denotes the stabilizer of $x$ in $\Gamma$, that
is, the subgroup of $\Gamma$ consisting of the elements $g$ such that
$g(x)=x$. Let $G$ be a graph and consider the natural action of
$\mathrm{Aut}(G)$ on $V(G)$ and fix a $u\in V(G)$. It is straightforward to
see that the function which maps any
$\alpha\in\mathrm{Stab}_{\mathrm{Aut}(G)}(u)$ to its restriction on $G-u$ is a
group injection. This proves the following well-known fact.

######  Lemma 3.1.

Let $G$ be a graph and $u\in V(G)$. Then $\mathrm{Stab}_{\mathrm{Aut}(G)}(u)$
is isomorphic to a subgroup of $\mathrm{Aut}(G-u)$. ∎

This motivates us to consider the vertices $u\in V(G)$ for which these two
groups are isomorphic.

######  Definition  3.2.

Let $G$ be a graph and $u\in V(G)$. We say that $u$ is a steady vertex of $G$
if $\mathrm{Stab}_{\mathrm{Aut}(G)}(u)\cong\mathrm{Aut}(G-u)$.

Note that $u$ is a steady vertex of $G$ if and only if for any
$\alpha\in\mathrm{Aut}(G-u)$, $\alpha$ maps the neighborhood $N_{G}(u)$ of $u$
onto itself. Therefore when $u$ is a steady vertex, $D(G-u)$ must be equal to
either $D(G)-1$ or $D(G)$, because in a distinguishing coloring of $G$, $u$ is
either uniquely colored or not. As some easy examples, note that every vertex
of a regular graph is steady, while no vertex of the path $P_{n}$ is steady,
for $n\geq 4$.

Later in this section, we will see that being steady is an important property
for evaluating the distinguishing number of some vertex-sum graphs. However,
before addressing this problem, we take a closer look at this property. An
interesting result is the relationship between the rather algebraic concept of
being steady and the graph theoretical concept of distinguishing coloring.
More specifically, we show that for a connected graph $G$, an equivalent
condition for a vertex $u\in V(G)$ to be steady is that every distinguishing
coloring of $G$ induces a distinguishing coloring on $G-u$ (Theorem 3.5).
First, we state one direction of the claim in the following proposition whose
proof is trivial.

######  Proposition 3.3.

Let $G$ be a connected graph. If a vertex $u\in V(G)$ is steady, then every
distinguishing coloring of $G$ induces a distinguishing coloring on $G-u$.∎

For the converse, then, we make use of the following lemma.

######  Lemma 3.4.

Suppose that $G$ is a graph, $p$ is a prime, $Q=\\{0,\ldots,p-1\\}\subseteq
V(G)$ and the cycle $(0,1,\ldots,p-1)$ appears in the cycle decomposition of
an automorphism $\alpha$ of $G$. Suppose also that $\beta\in\mathrm{Aut}(G)$
fixes $Q$ set-wise and is not the identity on $Q$. If $Q$ is partitioned into
two nonempty sets $A$ and $B$, then there exists $0<\ell<p$ such that the
automorphism $\alpha^{-\ell}\beta\alpha^{\ell}$ maps a vertex of $A$ to a
vertex of $B$.

###### Proof.

All differences and additions below take place in the group $\mathbb{Z}_{p}$.
It suffices to consider the restrictions of $\alpha$ and $\beta$ to $Q$. Let
$\beta=\sigma_{1}\cdots\sigma_{r}$ be the cycle decomposition of $\beta$ where
$\sigma_{i}=(t_{1}^{i},t_{2}^{i},\ldots,t_{o(\sigma_{i})}^{i})$, for
$i=1,\ldots,r$. Note that

$\alpha^{-1}\beta\alpha=\sigma_{1}^{\prime}\sigma_{2}^{\prime}\cdots\sigma_{r}^{\prime},$

where,
$\sigma_{i}^{\prime}=(t_{1}^{i}-1,t_{2}^{i}-1,\ldots,t_{o(\sigma_{i})}^{i}-1)$.

Suppose on contrary that the claim does not hold. Moreover, assume that $0\in
A$ and $(\alpha^{-1}\beta\alpha)(0)=x$. Thus, in particular we have $x\in A$.
Note that for any positive integer $\ell$,

$(\alpha^{-(\ell+1)}\beta\alpha^{(\ell+1)})(-\ell)=x-\ell.$ (3.1)

According to the contrary assumption, for any $\ell$, either both vertices
$-\ell$ and $x-\ell$ belong to $A$ or both of them belong to $B$. The equation
(3.1), further implies that

$\alpha^{kx-1}\beta\alpha^{-(kx-1)}(kx)=(k+1)x,\quad k\geq 0.$

Therefore, all multiples of $x$ belong to $A$, and since $\gcd(p,x)=1$, this
implies that $A=Q$, which is a contradiction. ∎

We are, now, ready to give a characterization of a steady vertex in terms of
distinguishing colorings.

######  Theorem 3.5.

Let $G$ be a connected graph. A vertex $u\in V(G)$ is steady if and only if
any distinguishing coloring of $G$ induces a distinguishing coloring on $G-u$.

###### Proof.

According to proposition 3.3, it suffices to prove the “if” part. Assume that
any distinguishing coloring of $G$ induces a distinguishing coloring on $G-u$
and suppose that $u$ is not steady. Thus, there exists an automorphism
$\alpha\in\mathrm{Aut}(G-u)$ which cannot be extended to any automorphism in
$\mathrm{Stab}_{\mathrm{Aut}(G)}(u)$. This means that there are two vertices
$v,w\in G-u$ such that $v\sim u$ but $w\nsim u$ in $G$ and $\alpha(v)=w$. Let
$\mathcal{A}$ be the set of all such automorphisms $\alpha$, and let
$\lambda\in\mathcal{A}$ be such that

$|\lambda|=\max\\{|\alpha|\;:\;\alpha\in\mathcal{A}\\}.$

Let $\lambda=\sigma_{1}\sigma_{2}\ldots\sigma_{r}$ be its cycle decomposition
and $|\lambda|=r+s$, where $s$ is the number of vertices that are fixed by
$\lambda$. Note that since $|\lambda|$ is the maximum, the orders
$o(\sigma_{j})$, $1\leq j\leq r$, are all equal to a prime number $p$. Let
$\sigma_{j}=(x_{1}^{j},\ldots,x_{p}^{j})$ and
$M_{j}=\\{x_{1}^{j},\ldots,x_{p}^{j}\\}$ and consider a coloring $c$ of $G$
with $1+r+s$ colors as follows: for $j=1,\ldots,r$, color all the vertices in
$M_{j}$ by the color $j$ and color any other vertices of $G$ (including $u$)
by a new color. It is clear that $\lambda$ preserves the restriction of $c$ to
$G-u$ and hence $c$ does not induce a distinguishing coloring on $G-u$.
Therefore, in order to conclude the proof, it is enough to show that $c$ is a
distinguishing coloring for $G$.

Assume that $\beta\in\mathrm{Aut}(G)$ is a non-identity automorphism that
preserves $c$. We deduce that $\beta(M_{j})=M_{j}$, for each $j=1,\ldots,r$,
and $\beta$ fixes all other vertices in $G$. Since
$\beta\in\mathrm{Stab}_{\mathrm{Aut}(G)}(u)$, the restriction $\tilde{\beta}$
of $\beta$ to $G-u$ is an automorphism of $G-u$. For some $1\leq j\leq r$, the
set $M_{j}$ contains a vertex $v$ such that $v\sim u$ while $\lambda(v)\nsim
u$. Without loss of generality, we assume that $v\in M_{1}$.

> Claim. $\tilde{\beta}$ is not the identity on $M_{1}$.
>
> Proof. First consider the case in which there exists an edge between $M_{i}$
> and $M_{j}$, for some $i,j\in\\{1,\ldots,r\\}$, where $\tilde{\beta}$ is
> identity on $M_{i}$ but non-identity on $M_{j}$. Let $w=x_{k}^{j}$ and
> $z=x_{\ell}^{j}$ be distinct vertices of $M_{j}$ such that
> $\tilde{\beta}(w)=z$. It follows that the set $N$ of neighbors of $w$ in
> $M_{i}$ is the same as the set of neighbors of $z$ in $M_{i}$. Let
> $k-\ell=t\;(\mathrm{mod}\;p)$. If $a\in N$, then $\lambda^{t}(a+ht)\in N$,
> for all $1\leq h\leq p$. Since $p$ is prime, we deduce that $N=M_{i}$; that
> is, each vertex in $M_{i}$ is adjacent to each vertex in $M_{j}$.
>
> Set $T=\\{j\;:\;\tilde{\beta}\;\;\text{is identity on}~{}M_{j}\\}$. We have
> $1\in T$ and $T^{\prime}=\\{1,\ldots,r\\}-T\neq\emptyset$. Define
> $\mu=\prod_{i\in T}\sigma_{i}.$ We show that $\mu$ is an automorphism of
> $G-u.$ Let $x$ and $y$ be two arbitrary adjacent vertices in $G-u$. We show
> that $\mu(x)$ is adjacent to $\mu(y)$, as well. If both $x$ and $y$ are
> fixed by $\mu$, then there is nothing to prove. We assume $x\in M_{i}$, for
> some $i\in T$, so $\mu(x)=\sigma_{i}(x)=\lambda(x)$. If $y$ also belongs to
> $M_{i}$, then $\mu(y)=\sigma_{i}(y)=\lambda(y)$ and, since $\lambda$ is an
> automorphism, we have $\mu(x)\sim\mu(y)$. Thus we assume $y\in M_{j}$, for
> some $j\neq i$. If $j\in T$, then
> $\mu(y)=\sigma_{j}(y)=\lambda(y)\sim\lambda(x)=\mu(x).$ If $j\notin T$, then
> $\mu(y)=y$ and, as we showed above, each vertex of $M_{i}$ is adjacent to
> each vertex of $M_{j}$. In particular, $\mu(x)\sim\mu(y)$. Finally, if
> $y\notin M_{i}$, for all $1\leq i\leq r$, then $\mu(y)=y=\lambda(y)$ and
> again $\mu(x)\sim\mu(y)$.
>
> Since $\mu=\lambda$ on $M_{1}$, it follows that $\mu$ is also in
> $\mathcal{A}$, while
>
> $|\mu|=|T|+\sum_{i\in T^{\prime}}|M_{i}|+s>r+s=|\lambda|.$
>
> This is a contradiction, which implies that $\tilde{\beta}$ is not the
> identity on $M_{1}$ and nor is $\beta$, which proves the claim.

To complete the proof of the theorem, we partition $M_{1}$ into nonempty sets
$A$ and $B$ where $A$ is the set of the vertices adjacent to $u$ in $G$.
According to Lemma 3.4, there exists an $0<\ell<p$ such that the automorphism
$\pi=\lambda^{-\ell}\,\tilde{\beta}\,\lambda^{\ell}$ of $G-u$ maps a vertex of
$A$ to a vertex of $B$. This shows that $\pi\in\mathcal{A}.$ Also, since $\pi$
and $\tilde{\beta}$ are conjugate, $|\pi|=|\tilde{\beta}|$. On the other hand,
$\tilde{\beta}(A)=A$ and $\tilde{\beta}$ has at least two cycles on $M_{1}$.
Thus $|\pi|>|\lambda|$, which contradicts the definition of $\lambda$. This
contradiction shows that $\tilde{\beta}$ is the identity on $M_{1}$ which, in
turn, contradicts the claim and, therefore, the proof is done. ∎

Next, as a straightforward use of steady vertices, we evaluate the
distinguishing number of the vertex-sum of $t$ copies of a single graph at a
given vertex. We will make use of the following lemma which is easy to prove.

######  Lemma 3.6.

Let $G_{1},\ldots,G_{t}$ be connected graphs. A vertex $u$ is steady in each
$G_{i}$ if and only if $u$ is steady in the vertex-sum of $G_{1},\ldots,G_{t}$
at $u$.∎

Recall that the _eccentricity_ of a vertex $v$ in a graph $G$ is the maximum
distance of $u$ from other vertices of $G$.

######  Theorem 3.7.

Given a connected graph $G$ and a vertex $u\in V(G)$, we have

$D(G_{u}^{t})\leq\min\left\\{k\,:\,\Phi_{k}(G-u)\geq t\right\\}.$

Moreover, equality holds when $u$ is a steady vertex of $G$.

###### Proof.

First note that every automorphism of $G_{u}^{t}$ fixes $u$, because $u$ is
the unique vertex of $G_{u}^{t}$ with the minimum eccentricity. Let
$q=\min\left\\{k\,:\,\Phi_{k}(G-u)\geq t\right\\}$ and
$\mathcal{A}_{q}=\\{c_{1},...,c_{\Phi_{q}(G-u)}\\}$ be the set of non-
equivalent distinguishing colorings of $G-u$ with at most $q$ colors. Consider
the coloring of $G_{u}^{t}$ in which each of the $t$ different copies of $G-u$
in $G_{u}^{t}$ is colored according to a distinct coloring in
$\mathcal{A}_{q}$. Since the central vertex $u$ is fixed by any automorphism
of $G_{u}^{t}$ and can be given any color, this coloring is clearly
distinguishing. Thus the first part of the theorem follows.

Now we assume that $u$ is a steady vertex of $G$. According to Lemma 3.6 and
Theorem 3.5, every distinguishing coloring of $G_{u}^{t}$ must induce a
distinguishing coloring on $G_{u}^{t}-u$.

Now suppose $\Phi_{k}(G-u)<t$ and that we want to color $G_{u}^{t}$ using $k$
colors. Then, even if the copies of $G-u$ in $G_{u}^{t}-u$ are colored
distinguishingly, there are two of them, say $G_{1}$ and $G_{2}$, which have
equivalent distinguishing colorings. Thus the automorphism of $G_{u}^{t}-u$
which only swaps these two copies preserves this coloring. We deduce that this
coloring is not distinguishing for $G_{u}^{t}-u$ and, consequently,
$D(G_{u}^{t})>k$ and the proof is complete. ∎

As an immediate consequence of Theorems 3.7, one observes the following.

######  Corollary 3.8.

If $G$ is the vertex-sum of $t$ copies of $K_{n}$ at any vertex, then

$D(G)=\min\left\\{k\,:\,{k\choose n-1}\geq t\right\\}.$

In particular, for the cases $n=3,4,5$, we have

$\displaystyle D\left({(K_{3})}_{u}^{t}\right)$
$\displaystyle=\left\lfloor{\frac{1+\sqrt{8t+1}}{2}}\right\rfloor,$
$\displaystyle D\left({(K_{4})}_{u}^{t}\right)$
$\displaystyle=\left\lceil\frac{\sqrt[3]{81t+3\sqrt{729t^{2}-3}}}{3}+\frac{1}{\sqrt[3]{81t+3\sqrt{729t^{2}-3}}}\right\rceil,$
$\displaystyle D\left({(K_{5})}_{u}^{t}\right)$
$\displaystyle=\left\lceil\frac{3+\sqrt{5+4\sqrt{24t+1}}}{2}\right\rceil.\qed$

We note that if $u$ is not steady, either strict inequality or equality may
hold in theorem 3.7. For example, let $H$ be the graph obtained by removing an
edge from $K_{4}$ and $u$ be a vertex of degree $2$ in $H$. Then $u$ is not
steady in $H$, $\Phi_{k}(H-u)={k\choose 3}$ and
$\min\left\\{k\,\middle|\,{k\choose 3}\geq 2\right\\}=3$; however
$D(H_{u}^{2})=2$. As another example, since $\Phi_{1}(P_{3})=0$ and
$\Phi_{2}(P_{3})=2$, the equality in Theorem 3.7 holds for the vertex-sum of
$P_{4}$ with itself at one of the end vertices, while none of the vertices of
$P_{4}$ is steady.

The case of vertex-sum of triangles has already been stated in [6]. For the
vertex-sums of cycles of the same length, using the formula 2.1, we obtain the
following result.

######  Corollary 3.9.

Let $G$ be the vertex-sum of $t$ cycles of length $n$. Then

$D(G)=\min\left\\{k\;:\;k^{n-1}-k^{\lceil\frac{n-1}{2}\rceil}\geq
2t\right\\}.$

In particular, for the case where $n$ is odd, we have

$D(G)=\left\lceil{\sqrt[\frac{n-1}{2}]{\frac{1+\sqrt{8t+1}}{2}}}\,\,\right\rceil.\qed$

Now, turn our attention to the vertex-sums of non-isomorphic graphs. It turns
out that the evaluation for the case of $2$-connected non-isomorphic graphs is
straightforward.

######  Theorem 3.10.

Let $G_{1},\ldots,G_{t}$ be 2-connected mutually non-isomorphic graphs all
having $u$ as a steady vertex, and let $G$ be their vertex-sum at $u$. Then
$D(G)=\max_{i}\\{D(G_{i}-u)\\}$.

###### Proof.

The vertex $u$ is fixed by any automorphism of $G$ because it is the only cut
vertex of $G$. The automorphisms of $G$ map each $G_{i}$ on itself. Since $u$
is steady in all $G_{i}$, one can distinguishingly color $G$ with
$\max_{i}\\{D(G_{i}-u)\\}$ colors. On the other hand, no distinguishing
coloring of $G$ can be found using less than $\max_{i}\\{D(G_{i}-u)\\}$
colors. Hence the result follows. ∎

In order to explain the necessity of the assumptions of Theorem 3.10, we note
that in Figure 1, both graphs $H_{1}$ and $H_{2}$ are 2-connected, the vertex
$u$ is not steady in $H_{2}$, $D(H_{1}-u)=2$, $D(H_{2}-u)=3$ and
$D(H_{1}\makebox[0.0pt][l]{$+$}\raisebox{-3.22916pt}{\makebox[8.61108pt]{${}_{u}$}}H_{2})=2$.
Furthermore, in Figure 2, the vertex $u$ is steady in both $H_{1}$ and
$H_{2}$, $D(H_{1}-u)=3$, $D(H_{2}-u)=2$ and
$D(H_{1}\makebox[0.0pt][l]{$+$}\raisebox{-3.22916pt}{\makebox[8.61108pt]{${}_{u}$}}H_{2})=5$.

$u\textnormal{ }$ | $u\textnormal{ }$ |  |  |  |  | $u\textnormal{ }$
---|---|---|---|---|---|---
$H_{1}$ | $H_{2}$ |  |  |  |  | $H_{1}\makebox[0.0pt][l]{$+$}\raisebox{-3.22916pt}{\makebox[8.61108pt]{${}_{u}$}}H_{2}$
Figure 1: a vertex-sum of two 2-connected graphs in which $u$ is not steady in one of them $u\textnormal{ }$ | $u\textnormal{ }$ |  |  |  |  | $u\textnormal{ }$
---|---|---|---|---|---|---
$H_{1}$ | $H_{2}$ |  |  |  |  | $H_{1}\makebox[0.0pt][l]{$+$}\raisebox{-3.22916pt}{\makebox[8.61108pt]{${}_{u}$}}H_{2}$
Figure 2: a vertex-sum of two graphs which are not 2-connected, albeit $u$ is
steady in both of them

In the rest of the section, we study the distinguishing threshold of vertex-
sum graphs. As an example, one can easily observe that if $G$ is a vertex-sum
of some complete graphs then $\theta(G)=|G|$. To deal with some non-trivial
cases, we start by the following theorem.

######  Theorem 3.11.

Let $G$ be the vertex-sum at $u$ of the 2-connected graphs
$G_{1},\cdots,G_{t}$, which all have $u$ as a steady vertex. If $G^{\prime}$
is the disjoint union of $G_{i}-\\{u\\}$, $1\leq i\leq t$, then

$\theta(G)=\theta(G^{\prime})+1.$

###### Proof.

Since $u$ is the only cut vertex of $G$,
$\mathrm{Aut}(G)=\mathrm{Stab}_{\mathrm{Aut}(G)}(u)$. In addition, according
to Lemma 3.6, $u$ is also steady in $G$. Hence,

$\mathrm{Aut}(G)=\mathrm{Stab}_{\mathrm{Aut}(G)}(u)\cong\mathrm{Aut}(G-u)=\mathrm{Aut}(G^{\prime}).$

Therefore, every coloring of $G$ with $\theta(G^{\prime})+1$ colors is
distinguishing and hence $\theta(G)\leq\theta(G^{\prime})+1.$ On the other
hand, consider a non-distinguishing coloring of $G^{\prime}$ with
$\theta(G^{\prime})-1$ colors and extend it to a coloring of $G$ by assigning
a new color to $u$. This coloring is not distinguishing for $G$. Thus
$\theta(G)=\theta(G^{\prime})+1$. ∎

As a non-trivial example, we consider the distinguishing threshold of vertex-
sum of cycles of the same length. The reader should note that this result can
be proved directly, but using Theorems 2.1 and 3.11, the proof is much
shorter.

######  Theorem 3.12.

Let $G$ be a vertex-sum of $t$ cycles of length $n$, Then

$\theta(G)=\left\lceil\frac{n-1}{2}\right\rceil+(n-1)(t-1)+2.$

###### Proof.

Any cycle $C_{n}$ is 2-connected and, obviously, every vertex of it is steady.
Therefore by Theorem 3.11, we have $\theta(G)=\theta(G^{\prime})+1$ where
$G^{\prime}$ is the disjoint union of $t$ copies of $P_{n-1}$. The
distinguishing threshold of this graph can be calculated using Theorem 2.1 (a)
as

$\theta(G^{\prime})=\max_{1\leq i\leq t}\;\left\\{\theta(P_{n-1})+\sum_{j\neq
i}|P_{n-1}|\right\\}=\left\lceil\frac{n-1}{2}\right\rceil+1+(n-1)(t-1).$

Therefore, the result follows. ∎

##  4 Rooted product

A rooted graph $(G,v)$ is a graph $G$ with a vertex $v$ which is called
_root_. Two rooted graphs $(G_{1},v_{1})$ and $(G_{2},v_{2})$ are said to be
isomorphic if there is an isomorphism $\alpha:G\rightarrow H$ such that
$\alpha(v_{1})=v_{2}$. By $\operatorname{Aut}(H,v)$ we mean all the
automorphisms of $H$ that fix $v$; in other words,
$\operatorname{Aut}(H,v)=\mathrm{Stab}_{\operatorname{Aut}(H)}(v)$. Moreover,
$D(H,v)$, $\varphi_{k}(H,v)$, $\Phi_{k}(H,v)$ and $\theta(H,v)$ are defined as
analogous symmetry breaking indices of $(H,v)$ by breaking
$\operatorname{Aut}(H,v)$ instead of $\operatorname{Aut}(H)$.

The _rooted product_ was defined by Godsil and McKay in [13] as follows. Let
$G$ be a labeled graph on $n$ vertices and $\mathcal{L}$ be a sequence of $n$
rooted graphs $(H_{1},v_{1}),\ldots,(H_{n},v_{n})$. Then the rooted product
graph, $G(\mathcal{L})$, is obtained by identifying $v_{i}$ with the $i$’th
vertex of $G$.

When $H_{i}$’s are not isomorphic to each other, the automorphisms of the
rooted product can be very complicated because there might be some
automorphisms that cannot be expressed by the product factors. For example,
suppose that $G=P_{2}$ and $\mathcal{L}=\left((P_{2},1),(P_{3},1)\right)$.
Then $G(\mathcal{L})$ is $P_{5}$. While $G$ has no non-identity automorphism
that fix a vertex, $G(\mathcal{L})$ has such an automorphism.

However, when $(H_{1},v_{1}),\dots,(H_{n},v_{n})$ are all isomorphic to a
rooted graph $(H,v)$ and both $G$ and $H$ are connected, all the automorphisms
of the rooted product keep the product structure and they can be treated
easier. This fact is shown in Theorem 4.2. For convenience, we limit our
attention to this special case which is defined below and illustrated in
Figure 3.

######  Definition  4.1.

Let $G$ and $H$ be two graphs, $|G|=n$ and $v\in H$. Then the smooth rooted
product, denoted by $G_{s}(H)$, is the rooted product graph $G(\mathcal{L})$
such that $\mathcal{L}$ is a sequence of $n$ copies of $(H,v)$.

|  | $v$ |  |  |  |
---|---|---|---|---|---|---
$G$ |  | $H$ |  |  |  | $G_{s}(H)$
Figure 3: the smooth rooted product of two graphs

It is easy to see that the smooth rooted product of $G_{s}(H)$ is a graph on
$|G|\cdot|H|$ vertices and a subgraph of the Cartesian product $G\square H$,
but it is not commutative. For this product, unlike the Cartesian product,
every copy of $(H,v)$ can be automorphically mapped onto itself separated from
other such copies. We show such automorphisms by $n$-tuples
$\left(\gamma_{1},\ldots,\gamma_{n}\right)$, where $\gamma_{i}$ is an
automorphism of the $i$’th copy of $(H,v)$. Consequently, an arbitrary
automorphism of the smooth rooted product is of a simple form which is
characterized in the following theorem.

######  Theorem 4.2.

Let $G$ and $H$ be connected graphs, $H$ be rooted at $v$ and $|G|=n\geq 2$.
Then $\alpha\in\operatorname{Aut}(G_{s}(H))$ if and only if there are
$\beta\in\operatorname{Aut}(G)$ and
$\gamma_{1},\ldots,\gamma_{n}\in\operatorname{Aut}(H,v)$ such that

$\alpha=\beta\circ\left(\gamma_{1},\ldots,\gamma_{n}\right).$

###### Proof.

It is obvious that $\beta\circ\left(\gamma_{1},\ldots,\gamma_{n}\right)$ is an
automorphism of $G_{s}(H)$. We prove that there is not any other. Suppose that
$\alpha\in\operatorname{Aut}(G_{s}(H))$ and $V(G)=\\{v_{1},\ldots,v_{n}\\}$.
Then, one of the following two cases holds.

  * Case 1.

The set $V(G)$ is mapped by $\alpha$ onto itself. Then, $\alpha$ induces an
automorphism on the subgraph induced by $V(G)$, which is isomorphic to $G$.
Since $H$ is connected, we deduce that $\alpha(H_{i},v_{i})=(H_{j},v_{j})$
when $\alpha(v_{i})=v_{j}$. This means that
$\alpha=\beta\circ\left(\gamma_{1},\ldots,\gamma_{n}\right)$ for some
$\beta\in\operatorname{Aut}(G)$ and
$\gamma_{1},\ldots,\gamma_{n}\in\operatorname{Aut}(H,v)$.

  * Case 2.

There is a vertex $v_{i}$ such that $\alpha(v_{i})\notin V(G)$; hence
$\alpha(v_{i})\in H_{j}$, for some $j$. Since $v_{i}$ is a cut vertex in
$G_{s}(H)$, $\alpha(v_{i})$ is also a cut vertex. Assume that
$\mathcal{A}_{j}$ is the union of all connected components of
$H_{j}-\\{\alpha(v_{i})\\}$ which do not contain $v_{j}$. We have

$G_{s}(H)-\\{v_{i}\\}=\left(H_{i}-\\{v_{i}\\}\right)\cup\left(G-\\{v_{i}\\}\right)_{s}(H)$

and

$G_{s}(H)-\\{\alpha(v_{i})\\}=\mathcal{A}_{j}\cup\left(G_{s}(H)-\left(\mathcal{A}_{j}\cup\\{\alpha(v_{i})\\}\right)\right).$

However, $G_{s}(H)-\mathcal{A}_{j}\cup\\{\alpha(v_{i})\\}$ is a connected
component which cannot be embedded into$\left(G-\\{v_{i}\\}\right)_{s}(H)$
because the former has more vertices. On the other hand, since $n\geq 2$, we
have

$|G_{s}(H)-\mathcal{A}_{j}|\geq|H|>|H_{i}-\\{v_{i}\\}|,$

which means that
$G_{s}(H)-\left(\mathcal{A}_{j}\cup\\{\alpha(v_{i})\\}\right)$ cannot be
mapped into $H_{i}-\\{v_{i}\\}$ either. Consequently neither
$H_{i}-\\{v_{i}\\}$ nor $\left(G-\\{v_{i}\\}\right)_{s}(H)$ contains the
connected component
$G_{s}(H)-\left(\mathcal{A}_{j}\cup\\{\alpha(v_{i})\\}\right)$, which is a
contradiction.

Therefore, the result follows. ∎

Using Theorem 4.2, we can evaluate the distinguishing number and the
distinguishing threshold of the smooth rooted products. The results appear in
the next two theorems.

######  Theorem 4.3.

Let $G$ and $H$ be two connected finite graphs, $H$ be rooted at $v$ and
$|G|,|H|\geq 2$. Then

$D(G_{s}(H))=\min\left\\{k\;:\;\Phi_{k}(H,v)\geq\frac{D(G)}{k}\right\\}.$

###### Proof.

When $D(G)\leq D(H,v)$ we have $D(G_{s}(H))=D(H,v)$, because using this number
of colors we can break all the automorphisms of $\operatorname{Aut}(H,v)$ and
$\operatorname{Aut}(G)$ and hence, according to Theorem 4.2, all the
automorphisms of $G_{s}(H)$ are also broken. In this case, the minimum $k$
such that $k\cdot\Phi_{k}(H,v)\geq D(G)$ is $D(H,v)$ because $\Phi_{k}(H,v)=0$
for $k<D(H,v)$. Consequently, the statement follows.

Now, suppose that $D(G)>D(H,v)$, $V(G)=\\{v_{1},\ldots,v_{n}\\}$ and

$q=\min\left\\{k\;:\;\Phi_{k}(H,v)\geq\frac{D(G)}{k}\right\\}.$

Obviously, $q\geq D(H,v)$ and therefore $\Phi_{q}(H,v)>0$. Let
$\mathcal{A}_{q}$ be the set of non-equivalent distinguishing colorings of
$(H,v)$ with at most $q$ colors and set

$\mathcal{B}_{q}=\left\\{(a,f)\;:\;1\leq a\leq
q,f\in\mathcal{A}_{q}\right\\}.$

We have $|\mathcal{A}_{q}|=\Phi_{q}(H,v)$ and
$|\mathcal{B}_{q}|=q\cdot\Phi_{q}(H,v)\geq D(G)$. Hence, there is a
distinguishing coloring $c$ of $G$ using elements of $\mathcal{B}_{q}$ as
colors. Define a $q$-coloring $\tilde{c}$ of $G_{s}(H)$ as follows:

$\tilde{c}(x)=\left\\{\begin{array}[]{lll}a;&&\textnormal{ if
}\;x=v_{i},\;i\in\\{1,\ldots,n\\}\textnormal{ and }c(x)=(a,f),\\\\[5.0pt]
f(x);&&\textnormal{ if }\;x\in
H_{i}-\\{v_{i}\\},\;i\in\\{1,\ldots,n\\}\textnormal{ and
}c(v_{i})=(a,f).\end{array}\right.$

One can easily see that $\tilde{c}$ is a distinguishing coloring, which means
that $D(G_{s}(H))\leq q$.

On the other hand, if $r<q$, then $|\mathcal{B}_{r}|=r\cdot\Phi_{r}(H,v)<D(G)$
which means that any coloring of $G$ with elements of $\mathcal{B}_{r}$ cannot
be distinguishing. Therefore, there is no $r$-coloring which breaks both
symmetries in copies of $(H,v)$ and symmetries in $G$. Consequently,
$D(G_{s}(H))\geq q$. ∎

######  Theorem 4.4.

Let $G$ and $H$ be connected graphs, $H$ be rooted at $v$ and $|G|,|H|\geq 2$.
Then

$\theta\left(G_{s}(H)\right)=\left(|G|-1\right)\cdot|H|+\theta(H,v),$

unless both $G$ and $H$ are asymmetric in which case we have
$\theta\left(G_{s}(H)\right)=1$.

###### Proof.

The “unless” part is clear by Theorem 4.2 and the fact that the distinguishing
threshold of an asymmetric graph is 1. Hence we may assume that $G$ or $H$ has
some symmetries and $t=\left(|G|-1\right)\cdot|H|+\theta(H,v)-1$. We color the
vertices of $G_{s}(H)$ with $t$ colors in such a way that
$(H_{1},v_{1})-\\{v_{1}\\}$ receives a non-distinguishing
$\left(\theta(H,v)-1\right)$-coloring and all other vertices receive the
remaining colors. The resulting coloring is not distinguishing because
$\text{\rm id}\circ(\gamma,\text{\rm id},\ldots,\text{\rm id})$ preserves it,
where $\gamma$ is a non-identity automorphism of $(H,v)$ which preserves the
$\left(\theta(H,v)-1\right)$-coloring of $(H_{1},v_{1})$. Therefore,
$\theta\left(G_{s}(H)\right)>t$.

Conversely, let $c$ be a $(t+1)$-coloring of $G_{s}(H)$. According to Theorem
4.2, any automorphism $\alpha\in\mathrm{Aut}(G_{s}(H))$ is of the form
$\alpha=\beta\circ(\gamma_{1},\ldots,\gamma_{n})$, for some
$\beta\in\operatorname{Aut}(G)$ and
$\gamma_{1},\ldots,\gamma_{n}\in\operatorname{Aut}(H,v)$. Since $c$ assigns
$(H_{i},v_{i})$ a color which is not assigned to $(H_{j},v_{j})$, for any
$i\neq j$, we have that $\beta=\text{\rm id}$. On the other hand,
$(H_{i},v_{i})$ receives no fewer color than $\theta(H,v)$, which implies that
$\gamma_{i}=\text{\rm id}$, for each $i$; that is, $\alpha=\text{\rm
id}\circ(\text{\rm id},\ldots,\text{\rm id})=\text{\rm id}$. This shows that
$c$ is distinguishing and the result follows. ∎

##  5 Corona product

In this section we study the distinguishing number and the distinguishing
threshold of the corona product of two graphs. We recall that given two graphs
$G$ and $H$, their corona product $G\odot H$ is a graph on
$|G|\cdot\left(|H|+1\right)$ vertices obtained by taking one copy of $G$ and
$|G|$ copies of $H$ and joining each vertex of the $i$-th copy of $H$ to the
$i$-th vertex of $G$, for $1\leq i\leq|G|$. An illustration for this product
is drawn in Figure 4. The reader may refer to [14] for more details.

|  |  |  |  |  |
---|---|---|---|---|---|---
$G$ |  | $H$ |  |  |  | $G\odot H$
Figure 4: the corona product of two graphs

The automorphisms of the corona product graphs were studied in [4] with an
erratum. The correct version is as follows: when $G\not\cong K_{1}$, any
$\alpha\in\mathrm{Aut}(G\odot H)$ can be expressed by a combination of an
automorphism $\beta\in\mathrm{Aut}(G)$ and $|G|$ automorphisms
$\gamma_{1},\ldots\gamma_{|G|}\in\mathrm{Aut}(H)$, i.e.,
$\alpha=\beta\circ\gamma_{1}\circ\ldots\circ\gamma_{|G|}$. Consequently, we
have

$|\mathrm{Aut}(G\odot H)|=|\mathrm{Aut}(G)|\cdot|\mathrm{Aut}(H)|^{|G|}.$
(5.1)

It was also shown that when $D(G)\leq D(H)$, the distinguishing number of the
corona product $G\odot H$ is $D(H)$. Moreover, for the case where $D(G)>D(H)$,
some lower and upper bounds were also given [4]. In this section, we obtain
similar results as in Section 4. We first evaluate $D(G\odot H)$ precisely in
terms of $\Phi_{k}(H)$.

######  Theorem 5.1.

Let $G$ and $H$ be two graphs and $G\not\cong K_{1}$. Then

$D(G\odot H)=\min\left\\{k\;:\;\Phi_{k}(H)\geq\frac{D(G)}{k}\right\\}.$

###### Proof.

When $D(G)\leq D(H)$ we have $D(G\odot H)=D(H)$ [4]. In this case, the minimum
$k$ such that $k\cdot\Phi_{k}(H)\geq D(G)$ is $D(H)$ because $\Phi_{k}(H)=0$
for $k<D(H)$. Consequently, the statement follows.

Suppose that $D(G)>D(H)$ and
$q=\min\left\\{k\;:\;\Phi_{k}(H)\geq\frac{D(G)}{k}\right\\}$. In this case,
the argument is quite similar to the proof of Theorem 4.3, so we only need to
rephrase it. Obviously, $q\geq D(H)$ and therefore $\Phi_{q}(H)>0$. Let
$\mathcal{A}_{q}$ be the set of non-equivalent distinguishing colorings of $H$
with at most $q$ colors and set

$\mathcal{B}_{q}=\left\\{(a,f)\;:\;1\leq a\leq
q,f\in\mathcal{A}_{q}\right\\}.$

Therefore $|\mathcal{A}_{q}|=\Phi_{q}(H)$ and
$|\mathcal{B}_{q}|=q\cdot\Phi_{q}(H)\geq D(G)$. Hence, there is a
distinguishing coloring $c$ of $G$ using elements of $\mathcal{B}_{q}$ as
colors. Define a $q$-coloring $\tilde{c}$ of $G\odot H$ as follows:

$\tilde{c}(v)=\left\\{\begin{array}[]{lll}a;&&\textnormal{ if }v\in
G\textnormal{ and }c(v)=(a,f),\\\\[5.0pt] f(v);&&\textnormal{ if }v\in
H_{u},u\in G\textnormal{ and }c(u)=(a,f).\end{array}\right.$

We can easily see that $\tilde{c}$ is a distinguishing coloring, which means
that $D(G\odot H)\leq q$.

Finally, if $r<q$, then $|\mathcal{B}_{r}|=r\cdot\Phi_{r}(H)<D(G)$ which means
that any coloring of $G$ with elements of $\mathcal{B}$ cannot be
distinguishing. Therefore, there is no $r$-coloring that breaks both
symmetries in copies of $H$ and symmetries in $G$. Consequently, $D(G\odot
H)\geq q$. ∎

We point out that Alikhani and Soltani in [4] showed that $D(H)\leq
D(K_{1}\odot H)\leq D(H)+1$, which completes the study. We conclude this
section by evaluating the distinguishing threshold of the corona product of
two graphs.

######  Theorem 5.2.

Let $G$ and $H$ be two graphs.

  * (a)

If $\mathrm{Aut}(H)\neq\\{\text{\rm id}\\}$, then $\theta(G\odot
H)=|G|+|H|\cdot(|G|-1)+\theta(H)$.

  * (b)

If $\mathrm{Aut}(H)=\\{\text{\rm id}\\}$, then $\theta(G\odot
H)=(|H|+1)\cdot\theta(G)-|H|$.

###### Proof.

Let $|G|=n$ and $|H|=m$. To prove (a), assume $s=n+m(n-1)+\theta(H)$. It is
evident that $\theta(G\odot H)\geq s$, thus it suffices to show that any
coloring of $G\odot H$ with $s$ colors is distinguishing. Any such coloring
assigns unique colors to $s$ vertices of $G\odot H$ and we assume, without
loss of generality, that a remaining subset $X\subset V(G\odot H)$, with
$|X|=m-\theta(H)$, receives only one color, say $1$. If $X\cap
V(G)=\emptyset$, then in any copy of $H$ in $G\odot H$, at least $\theta(H)$
colors have been used that are not used elsewhere. This shows that the
coloring of each copy of $H$ and, hence, the coloring of the entire graph
$G\odot H$ is distinguishing. If, otherwise, $X\cap V(G)\neq\emptyset$, then
any copy of $H$ contains a color which no other copy does. Note that if
$\alpha\in\mathrm{Aut}(G\odot H)$ maps $v_{1}\in G$ to $v_{2}\in G$, then it
has to map the copy of $H$ adjacent to $v_{1}$ onto the copy of $H$ adjacent
to $v_{2}$. Therefore, no automorphism of $G\odot H$ can preserve the
coloring.

To prove (b), we note that there is a group isomorphism
$f:\mathrm{Aut}(G)\to\mathrm{Aut}(G\odot H)$. Assume that $\alpha$ is a non-
identity automorphism of $G$ with maximum number of disjoint cycles in its
cycle decomposition. Then $\tilde{\alpha}=f(\alpha)$ is a non-identity
automorphism of $G\odot H$ with maximum number of disjoint cycles in its cycle
decomposition and $|\tilde{\alpha}|=(m+1)|\alpha|$. On the other hand,
according to Lemma 2.2, $|\alpha|=\theta(G)-1$; hence
$|\tilde{\alpha}|=(m+1)(\theta(G)-1)$. Using Lemma 2.2 again, the result
follows. ∎

##  6 Lexicographic product

Finally, we consider the lexicographic product of graphs. Given two graphs $G$
and $H$, their lexicographic product is the graph $Z=G\circ H$ with

$V(Z)=\\{(x,y)\;:\;x\in G,\,y\in H\\},$

in which $(x,y)$ is adjacent with $(x^{\prime},y^{\prime})$ if $x\sim
x^{\prime}$ in $G$ or $x=x^{\prime}$ and $y\sim y^{\prime}$ in $Y$. It is easy
to see that for every vertex $x\in G$, there is a copy of $Y$, say $Y_{x}$ in
$C\circ H$. A simple illustration of this product is depicted in Figure 5.

|  |  |  |  |  |
---|---|---|---|---|---|---
$G$ |  | $H$ |  |  |  | $G\circ H$
Figure 5: the lexicographic product of two graphs

Automorphism groups of the lexicographic product graphs were studied by
Hemminger [15] and Sabidussi [20]. Hemminger defined natural isomorphisms as
follows: let $Z_{1}=G_{1}\circ H_{1}$ and $Z_{2}=G_{2}\circ H_{2}$. Then a
graph isomorphism $\mu:Z_{1}\rightarrow Z_{2}$ is called _natural_ if for each
$x_{1}\in G_{1}$ there is an $x_{2}\in G_{2}$ such that
$\mu({H_{1}}_{x_{1}})={H_{2}}_{x_{2}}$; otherwise $\mu$ is called unnatural.
Moreover, he characterized all lexicographic product graphs whose automorphism
groups consist of all their natural automorphisms [15]. It is clearly more
difficult to deal with the unnatural automorphisms, hence here we only
consider the lexicographic products whose automorphisms consist only of
natural ones. In this case, the distinguishing number of the lexicographic
product of $G$ and $H$ has already been calculated in [1] as the smallest
integer $k$ such that $\Phi_{k}(H)\geq D(G)$. In the following theorem, which
is similar to Theorem 5.2, we calculate the distinguishing threshold of the
lexicographic product of such $G$ and $H$.

######  Theorem 6.1.

Let $G$ and $H$ be two graphs such that $\mathrm{Aut}(G\circ H)$ consists only
of natural automorphisms.

  * (a)

If $\mathrm{Aut}(H)\neq\\{\text{\rm id}\\}$, then $\theta(G\circ
H)=(|G|-1)\cdot|H|+\theta(H)$.

  * (b)

If $\mathrm{Aut}(H)=\\{\text{\rm id}\\}$, then $\theta\left(G\circ
H\right)=\left(\theta(G)-1\right)\cdot|H|+1$.

###### Proof.

To prove (a), let $s=(|G|-1)\cdot|H|+\theta(H)$. It is obvious that
$\theta(G\circ H)\geq s$. Assume that $c$ is an arbitrary coloring for $G\circ
H$ with $s$ colors and that $\alpha\in\mathrm{Aut}(G\circ H)$ is arbitrary. We
show that $\alpha$ cannot preserve $c$ and this proves the claim. Since
$\alpha$ is natural, we have the following two cases. If $\alpha$ maps at
least one copy of $H$ to another, then, since the number of colors are more
than $(|G|-1)\cdot|H|$, we deduce that every copy of $H$ has a color that is
not used in the other copies of $H$. Therefore, $\alpha$ cannot preserve $c$.
If, on the other hand, the restriction of $\alpha$ to each copy of $H$ is an
automorphism of that copy of $H$, then the fact that $s\geq|G|\cdot\theta(H)$
implies that $c$ uses at least $\theta(H)$ colors on each copy of $H$, which
again shows that $\alpha$ cannot preserve $c$.

To prove (b), we note that, similar to the proof of Theorem 5.2, there is a
group isomorphism $f:\mathrm{Aut}(G)\to\mathrm{Aut}(G\circ H)$. For any
$\alpha\in\mathrm{Aut}(G)$, we denote $f(\alpha)$ by $\tilde{\alpha}$.
According to Lemma 2.2, there exists an automorphism $\lambda$ such that
$\theta(G)=|\lambda|+1$. Since $\mathrm{Aut}(H)=\\{\text{\rm id}\\}$ and all
the automorphisms of $G\circ H$ are natural, we have

$\max\left\\{|\tilde{\alpha}|\;:\;\tilde{\alpha}\in\mathrm{Aut}(G\circ
H)\right\\}=|\tilde{\lambda}|.$

On the other hand, if $\sigma_{j}$ is a cycle in the cycle decomposition of
$\lambda$, then $\tilde{\sigma}_{j}$ contains $|H|$ disjoint cycles of length
$o(\sigma_{j})$. This implies that
$|\tilde{\lambda}|=|H|\cdot|\lambda|=|H|\cdot(\theta(G)-1)$ which, using Lemma
2.2, completes the proof. ∎

##  7 Conclusion and future work

Following the recent works concerning the distinguishing number and the
distinguishing threshold of graphs, we addressed the problem of determining
these parameters for some graph operations, namely vertex-sums, rooted
products, corona products and lexicographic products. The calculations of
distinguishing number consisted of some combinatorial arguments while for
computing the distinguishing threshold, we analyzed the automorphisms for
their cycle structures.

To handle the first operation, we introduced the concept of steady vertices
which turns out to have some nice properties on its own and seems to have some
interesting applications as well. As one of future research directions in this
regard, one can extend the notion of vertex-sum to $m$-vertex-sums where new
graphs are obtained by identifying an $m$-set of vertices in each graph. Then
the new concept of a steady vertex generalizes to a _steady set_. As an
auxiliary result, we showed that Theorem 3.5 can be generalized to steady
sets, as well. However generalizing Theorem 3.7 seems to be a harder problem.
Since every connected graph is an $m$-vertex-sum of some smaller graphs,
studying this problem may be a fruitful approach to obtain upper bounds for
the distinguishing number and the distinguishing threshold of arbitrary
graphs.

As another generalization, we can analogously obtain some results about _edge-
sums_ , where graphs are glued to each other by identifying one of their
edges. As an example of such calculations, we observe that the distinguishing
number of the edge-sum of $t$ cycles $C_{n}$ is equal to
$\left\lceil{\sqrt[n-2]{t}}\right\rceil$.

The ultimate outcome of the present research is that calculating
$\varphi_{k}(G)$ and $\Phi_{k}(G)$ is more valuable than we previously
thought. We showed that these indices are important in calculating
distinguishing indices of the graph operations we considered here and they
might appear in some other types of operations. Since knowing the
distinguishing threshold of a graph $G$ is an important factor in calculating
$\varphi_{k}(G)$ and $\Phi_{k}(G)$, an interesting plan for a future study is
calculating these indices for much more classes of graphs that they are known
now.

##  References

  * [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.  The Electronic Journal of Combinatorics, 3(1):$\\#$R18, 1996.
  * [3] S. Alikhani and M. H. Shekarriz.  Symmetry breaking indices for the Cartesian product of graphs.  Preprint available on arXiv: 2108.00635, 2021.
  * [4] S. Alikhani and S. Soltani.  Distinguishing number and distinguishing index of certain graphs.  Filomat, 31(14):4393–4404, 2017.
  * [5] S. Alikhani and S. Soltani.  The distinguishing number and distinguishing index of the lexicographic product of two graphs.  Discussiones Mathematicae Graph Theory, 38:853–865, 2018.
  * [6] S. Alikhani, S. Soltani, and A. J. Khalaf.  Distinguishing number and distinguishing index of join of two specific graphs.  Advances and Applications in Discrete Mathematics, 17(4):467–485, 2016.
  * [7] L. Babai.  Asymmetric trees with two prescribed degrees.  Acta Mathematica Academiae Scientiarum Hungaricae, 29(1-2):193–200, 1977.
  * [8] F. Barioli, S. Fallat, and L. Hogben.  Computation of minimal rank and path cover number for certain graphs.  Linear Algebra and its Applications, 392:289–303, 2004.
  * [9] B. Bogstad and L. Cowen.  The distinguishing number of hypercubes.  Discrete Mathematics, 283:29–35, 2004.
  * [10] K. L. Collins and A. N. Trenk.  The distinguishing chromatic number.  The Electronic Journal of Combinatorics, 13:$\\#$R16, 2006.
  * [11] R. Diestel.  Graph theory.  Graduate texts in mathematics 173. Springer, 5th edition, 2017.
  * [12] E. Estaji, W. Imrich, R. Kalinowski, M. Pilśniak, and T. Tucker.  Distinguishing Cartesian products of countable graphs.  Discussiones Mathematicae Graph Theory, 37:155–164, 2017.
  * [13] C.D. Godsil and B.D. McKay.  A new graph product and its spectrum.  Bulletin of the Australian Mathematical Society, 18(1):21–28, 1978\.
  * [14] R. Hammack, W. Imrich, and S. Klavžar.  Handbook of product graphs.  Second edition. CRC Press, 2011.
  * [15] R. Hemminger.  The group of an x-join of graphs.  Journal of Combinatorial Theory, 5:408–418, 1968.
  * [16] L. H. Huang, G. j. Chang, and H. G. Yeh.  On minimum rank and zero forcing sets of a graph.  Linear Algebra and its Applications, 432:2961–2973, 2010.
  * [17] W. Imrich, J. Jerebic, and S. Klavžar.  The distinguishing number of Cartesian products of complete graphs.  European Journal of Combinatorics, 29(4):922–929, 2008.
  * [18] W. Imrich and S. Klavžar.  Distinguishing Cartesian powers of graphs.  Journal of Graph Theory, 53:250–260, 2006.
  * [19] 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.
  * [20] G. Sabidussi.  The lexicographic product of graphs.  Duke Mathematical Journal, 28(4):573–578, 1961.
  * [21] M. H. Shekarriz, B. Ahmadi, S. A. Talebpour Fard Shirazi, and M. H. Shirdareh Haghighi.  Distinguishing threshold of graphs.  Preprint available on arXiv: 2107.14767, 2021.