# Topologically protected $\pi$-ring qubits

Michael Forrester
Advanced Materials and Devices
QinetiQ
Farnborough
UK
GU14 0LX Fedor Kusmartsev
College of Art and Science
Khalifa University
Abu Dhabi
UAE
P.O. Box 127788

###### Abstract

The $\pi$-ring qubit array is described using quasiclassical approaches that
are shown to be accurate and give clarity to the complex energy landscape of
connected vortex qubits. Using the techniques, large arrays of Josephson
junction systems can be designed, including phase shift devices. Herein,
connected arrays of loops containing $\pi$ junctions are described. These
techniques are useful for design of quantum computers based on superconducting
technologies, hybrid quantum technologies and quantum networks.

In topological quantum computation it is a design stipulation that the utmost
protection of the qubits from the effects of environmental noise should ensue.
Extraneous noise or circuitry can destroy the quantum state and drastically
affect coherence times. One way of protecting the qubits is to enclose them in
a medium of almost identical structures. Indeed, this gives a quantum error
correction capability to the systems such that the effects of local noise
become exponentially small as the size of the lattice increases [7, 6]. The
enclosure of a central plaquette is the focus of this next investigation. We
also address the inclusion of a $\pi$\- shift into each element of the array.
The superconducting $\pi$\- ring has enormous potential for sensitive field
detection, energy transfer as well as quantum computation.

Every interconnection in a superconducting island network contains a Josephson
junction. We introduce a phase shift of $\pi$ to some of the junctions.
Technologically, this can be created by linking superconducting islands
through a ferromagnetic layer of the correct thickness. Frolov and co-workers
did just that when determining the spontaneous currents in superconducting
arrays of $\pi$-junctions[4]. For example, they considered a two dimensional
lattice of Josephson junctions, as illustrated in Fig. 1 $(a)$ on the left-
hand side.

Figure 1: A system composed of superconductor-ferromagnet-superconductor
Josephson-junctions [4] with four plaquettes. The total energy is normalised
by the Josephson energy as a function of the magnetic flux in the system. The
energy is calculated using the quasiclassical method [9].

In the experiments of Frolov et al[4] their objective was to show the
emergence of spontaneous currents in square superconductor-ferromagnet-
superconductor ($SFS$) $\pi$-junction circuits. To do so they created arrays
with different levels of frustration. They showed unequivocally that the
$\pi$-junctions generated the sought after currents and explained the
spontaneous current distributions by simulating the Josephson phase dynamics.
We use a quasiclassical approach and find good comparison to their findings in
the energy-flux dependencies. For example, in Fig. 1 $(c)$ the energy as a
function of the magnetic flux per cell is shown for the case where the
plaquettes on the main diagonal are $\pi$-rings (containing odd numbers of
$\pi$-junctions) and those on the off-diagonal contain two or four
$\pi$-junctions. This has the effect of creating an antiferromagnetically
aligned system. The results mirror the array free energies found in
reference[4]. Thus, we have confidence that the quasiclassical method is
accurate and can find all the possible ground and excited states and to
resolve all the vortex states. This is in contrast to, say, Monte Carlo
methods that tend to miss many of the pertinent energy levels, and frequently
can only determine the two lowest energy states closest to the ground state
energy[9].

Figure 2: Triangular plaquettes with each leg containing a Josephson junction.
In the case of $\pi$-rings each plaquette has one side containing a
$\pi$-junction. The currents are taken to flow in a clockwise direction around
each cell and replace the phases over each junction in the harmonic
approximation.

We now demonstrate a system of four interconnected triangular plaquettes, as
shown in Fig.2. Such systems, that exploit geometrically induced frustration,
have been made from Josephson junctions[5] and superconducting rings [1]. The
Josephson junction network is often described in terms of the $XY$ model[8],
with Hamiltonian $H=-J\sum_{\left\langle
ij\right\rangle}cos\left(\theta_{i}-\theta_{j}\right)$ describing the coupling
between phases $\theta_{ij}$. Here the summation is taken over pairs of
nearest neighbours in the rings that are connected by Josephson junctions. A
harmonic approximation[9] so that the Josephson current is,
$I=I_{C}sin\left(\theta_{i}-\theta_{j}\right)\approx
I_{C}\left(\theta_{i}-\theta_{j}\right)$. It is assumed that the critical
current $I_{C}$ of each Josephson junction is the same. When the number of
Josephson junctions in a loop enables the variation in the phase to be
small[9] the harmonic approximation is applicable. That is to say, if the
number of junctions in the plaquette is not too small then the phase dropped
across each junction will be small enough that a good approximation is found.
As a result, supercurrents are emphasised over phase differences in this
analysis. These supercurrents circulate around the loops of the Josephson
array. Using flux quantisation the current distributions for any vortex
configuration is attainable. This allows the calculation of the ground state
energies as well as those of the excited states in the system. The method of
analysis closely mirrors Kirchoff’s laws for analysing currents. Kirchoff’s
current conservation law states that the sum of the currents out of any vertex
is zero. We now use these methods for the frustrated triangular lattice shown
in Fig.2. The currents are taken to flow in the clockwise sense. The self-
inductance, $L$, is calculated for each side of a plaquettes and the total
self-energy of the stack of triangular loops is a summation of these terms
multiplied by the currents in each side. The derivation of the self-inductance
is given in the supporting information. The self-inductance is written as,

$L_{polygon}=\frac{m~{}\mu_{0}}{4\pi}\left\\{\left(D-a\right)sinh^{-1}\left(\frac{D-a}{a}\right)-a~{}sinh^{-1}\left(1\right)+\sqrt{2a}-\sqrt{a^{2}+\left(D-a\right)^{2}}\right\\}$
(1)

where $D$ is the length of one of the sides of a plaquette, $a$ is the leg-
width, and $m$ is the number of legs in the polygon geometry of the $\pi$-ring
(e.g. for a triangular plaquette with $L_{\Delta}$, m=3). In Fig.2 the array
is composed of four triangular Josephson plaquettes. Each of these has a
Josephson junction in each of its three sides. The plaquettes in this system
contain the minimum number of Josephson junctions that are allowed by the
method. First of all we show the results for a system of ordinary plaquettes
in an applied magnetic field. The supercurrents are found from the following
relationships,

$\left(\begin{array}[]{cccc}3&0&0&-1\\\ 0&3&0&-1\\\ 0&0&3&-1\\\
-1&-1&-1&3\end{array}\right)\left(\begin{array}[]{cccc}I_{1}\\\ I_{2}\\\
I_{3}\\\ I_{4}\end{array}\right)=2\pi\left(\begin{array}[]{cccc}n_{1}-f\\\
n_{2}-f\\\ n_{3}-f\\\ n_{4}-f\end{array}\right)$ (2)

or in general $\mathbf{M}$ an $N_{p}\times N_{p}$

$\left(\begin{array}[]{ccccc}N_{p}&0&0&\dots&-1\\\ 0&N_{p}&0&\dots&-1\\\
0&0&N_{p}&\dots&-1\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
-1&-1&-1&\dots&N_{p}\end{array}\right)\left(\begin{array}[]{cccc}I_{1}\\\
I_{2}\\\ I_{3}\\\
I_{4}\end{array}\right)=2\pi\left(\begin{array}[]{cccc}n_{1}-f\\\ n_{2}-f\\\
n_{3}-f\\\ n_{4}-f\end{array}\right)$ (3)

Note that for plaquettes that contain $\pi$-junctions a $-1/2$ term is
included in each of the $n_{i}-f$ terms on the right hand side of Eq.(3). Here
$n_{i}$ is the number of vortices in a plaquette with $i=1,...,N_{p}$ and
$N_{p}$ is the number of plaquettes. The parameter $f$ is an applied flux
through the $i-th$ plaquette or a spontaneous flux when there exists a
$\pi$-junction. The solution of Eq.(3) for a triangular array gives,

$\begin{array}[]{cccc}I_{1}=\frac{\pi}{27}\left(21\left(n_{1}-f\right)+3\left(n_{2}-f\right)+3\left(n_{3}-f\right)+9\left(n_{4}-f\right)\right),\\\
I_{2}=\frac{\pi}{27}\left(3\left(n_{1}-f\right)+21\left(n_{2}-f\right)+3\left(n_{3}-f\right)+9\left(n_{4}-f\right)\right),\\\
I_{3}=\frac{\pi}{27}\left(9\left(n_{1}-f\right)+9\left(n_{2}-f\right)+9\left(n_{3}-f\right)+27\left(n_{4}-f\right)\right),\\\
I_{4}=\frac{\pi}{27}\left(3\left(n_{1}-f\right)+3\left(n_{2}-f\right)+21\left(n_{3}-f\right)+9\left(n_{4}-f\right)\right).\end{array}$
(4)

To calculate the energy of the system we write,

$Energy=\frac{1}{2}\left(1-\frac{2LI_{c}^{2}}{E_{J}}\right)\sum_{i=1}I_{i}^{2}$
(5)

For the stack of triangular plaquettes of Fig.2 this becomes,

$Energy=\frac{1}{2}\left(1-\frac{2LI_{c}^{2}}{E_{J}}\right)\left[4\left(I_{1}^{2}+I_{2}^{2}+I_{3}^{2}\right)+6I_{4}^{2}-4\left(I_{1}I_{4}+I_{2}I_{4}+I_{3}I_{4}\right)\right]$
(6)

In the following we write the Josephson energy equal to $\Phi_{0}I_{c}/2\pi$,
the length of a plaquette leg as $D=45\mu m$, the leg width as $2a=15\mu m$,
and the critical current as $I_{c}=1500aD[A]$. With these parameters and using
Eq.(1), the self-inductance is $L_{\Delta}=16pH$ and the critical current is
$I_{c}=0.5\mu A$. Mutual inductance within the triangular array structure is
expected to be insignificantly small. This conclusion is brought about by the
fact that the magnetic self-energy seems to be proportionately very small in
comparison to the Josephson energy (approximately $5\%$ of the size in the
cases considered here). This will remain the case unless the loops become much
greater in area. The additional energies will change the shape of the energy
curves that are plotted as a function of the applied flux (in the case of
ordinary Josephson junction plaquettes) or the spontaneous flux generated in a
$\pi$-ring. However, the vortex distribution will probably be unaffected.

Figure 3: The triangular networks exhibiting all configurations that represent
the presence or lack of a vortex in each plaquette. Dark colouring indicates a
vortex.

All the different vortex configurations for the triangular array are shown in
Fig.3 for the case of positive applied flux and $n=0$ or $1$. The dark
coloured plaquettes depict the situation in which there is a vortex present
and the unfilled ones are the empty loops. This shows the potential for logic
or memory devices in such systems. In this case there are $2^{4}$ possible
outcomes. Using this method we find the optimal configuration for the vortices
within the system and hence a design ethic for quantum bits. The energy as a
function of the flux (in units of the elementary flux quantum) for the various
vortex patterns in the pyramid is shown in Fig.4.

Figure 4: The energy distribution as a function of the applied flux for a
system of triangular geometries containing only ordinary junctions.

This plot is for the scenario whereby there are only ordinary junctions in the
system and there is an applied magnetic field. In this case the energies are
defined as a function of the orientation of the trapped flux: $n=0,\pm 1$. In
Fig.4 the energies and the corresponding absence or existence of a vortex
gives a series of degeneracies. Each parabolic curve is related to $n_{1}$,
$n_{2}$, $n_{3}$, $n_{4}$ vortices trapped by plaquettes $1-4$, respectively.
Curves marked by an $A$ represent the ground state energies, with minima at
$\Phi=0,\pm\Phi_{0}$ and $n_{1}=n_{2}=n_{3}=n_{4}=0$;
$n_{1}=n_{2}=n_{3}=n_{4}=\pm 1$. Taking the region concerning positive values
of quantum numbers, i.e. $0\leq f\leq 1$, which is exactly mirrored when
$f\leq 0$, and increasing the flux leads to the appearance of single vortex
states: i.e. curve $B$ that is related to
$\left\\{n_{1},n_{2},n_{3},n_{4}\right\\}=\left\\{0,1,0,0\right\\}$ or
$\left\\{1,0,0,0\right\\}$ or $\left\\{0,0,1,0\right\\}$. The minimum energy
of the parabola associated with these vortex configurations occurs at
$f\approx 0.2$. The parabolic curve for a single vortex existing in plaquette
$3$ (the central one) with no trapped fluxes in the outer three plaquettes,
i.e. $\left\\{0,1,0,0\right\\}$, is denoted in Fig.4 as $C$. At $f\approx 0.4$
the minimum of this condition exists. At $f\approx 0.6$ the ground state for
the three outer plaquettes having vortex states is seen, i.e. curve $D$ with
$\left\\{1,1,1,0\right\\}$. When the magnetic flux reaches $f\approx 0.8$ and
when the trapping of the flux results in the scenario of
$\left\\{n_{1},n_{2},n_{3},n_{4}\right\\}=\left\\{1,0,1,1\right\\}$ or
$\left\\{0,1,1,1\right\\}$ or $\left\\{1,1,0,1\right\\}$, the minimum of curve
$E$ emerges. Again, when $f\approx 0.8$ an excited state occurs for the
arrangement of vortices $\left\\{1,0,0,1\right\\}$, $\left\\{0,1,0,1\right\\}$
or $\left\\{0,0,1,1\right\\}$. Whenever two vortices exist in this manner in
the pyramid system a higher energy state comes about through the formation of
an energy repulsion between the vortices. A dimer is formed. Another excited
two vortex state exists at curve $G$, $\left\\{1,0,1,0\right\\}$,
$\left\\{1,1,0,0\right\\}$, or $\left\\{0,1,1,0\right\\}$ with a minimum
energy at $f\approx 0.6$. Introducing a $\pi$-junction to each plaquette has
the effect of moving the parabolic curves of Fig.4 by half a flux quantum.
This is shown in Fig.5.

Figure 5: The energies for the triangular Josephson junction triangular array
as a function of flux. A $\pi$-shift is developed due to the introduction of
an odd number of $\pi$-junctions in each plaquette.

This case, with $\pi$-junctions included, does not need to have an external
flux introduced to the system as it can naturally generate spontaneous flux -
this is very important because one can then eradicate a lot of extraneous
control circuitry [3]. The $\pi$-rings are therefore ideal candidates for
making superconducting metamaterials [2] as well as quantum information
devices. In this discussion we will continue to develop the idea of having a
central plaquette that is surrounded by exact replicas as nearest neighbours
that offer topological protection. Figure (6) demonstrates a central square
plaquette adjoined with four identical plaquettes on each of its vertices. The
energies are again calculated using the quasi-classical method.

Figure 6: The energies associated with five square plaquettes arranged in a
spin star when each contains an odd number of $\pi$-junctions.

These arrangements of Josephson junctions form the foundations for creating
large-scale arrays with a basis for creating a layout for quantum computation.
One popular design, first proposed for a two junction ring[10], will
incorporate a ferromagnetic material as the interlayer between the
superconducting islands for the $\pi$-junctions along with normal Josephson
junctions with insulating barriers. The ferromagnetic layers can be metallic
or, novelly, an insulator[Kawabata2010]. The ferromagnetic insulators are
proposed for creating $\pi$-junction devices because they avoid the problem of
strong dissipation, that is present for ferromagnetic metal systems, due to
low energy quaiparticle excitations[Kawabata2010]. Remarkably, in
superconductor/ferromagnetic insulator/superconductor structures the ground
state changes between the $0$ and $\pi$ states as the ferro-insulator
increases by a single atomic layer. The existence of a $\pi$-shift is a
function of the number of layers: for an even number there are positive
critical currents, whereas for an odd number they are negative. Thus, there
are a range of possibilities for creating $S/F/S$ structures, from high
$T_{c}$ superconductors separated by atomic layers of, for example,
$La_{2}BaCuO_{5}$, to more conventional interlayers of ferromagnetic metals
that give a proximity induced $\pi$-transition. The added benefit of using the
$\pi$-states is that the multilevel energy system is spontaneously generated
and consequently protected from the decoherence induced by the fluctuation of
an applied magnetic field. However, one may require to use external
electromagnetic fields to manipulate the system, so again the issue of
protecting the qubit states arises. Thus, building the spin star kind of array
can result in systems that function to do so.

At this point it is time to also point out that schemes do exist with
completely different architectures to those proposed for standard quantum
computation. Quantum logic gates form the foundation for one methodology. This
approach, whilst enormously promising, would seem to be many years from
creating large scale quantum computing. Currently, a Canadian company called
D-wave are marketing a quantum computer designed around a different concept
using quantum annealing. However, there is a debate going on as to whether
quantum annealing offers any speed up on classical computers. Quantum
annealing searches for the lowest energy configuration of the system [Boixo
2014] and so the techniques we have described here are equally relevant for
qubit architectures based on quantum gating, annealing [Boixo 2014] or
adiabatic quantum computing [Deng 2013]. The D-wave machines are very much
prototypes for the concept and it is therefore prudent to keep investigating
innovative new techniques and methods of analysis to avoid the problem of
noise in the system.

Another very promising form of quantum computation using superconducting
systems is that of the topologically protected system[7, 6], of which the
spin-star is a subset. Josephson junction arrays imitate dimers, as we saw for
the pyramid structure, when composed of triangular or kagome networks.A
Josephson junction network with protected ground state degeneracies is one of
the most promising long term solutions to the issues surrounding decoherence.
Also, the vortices in the system may be propagated through the topological
sectors by a slow, adiabatic, change of the flux towards a half integer value.
In this way many of the principles guiding the design of functional Josephson
arrays for quantum computing can be amalgamated to produce an optimally
effective solution - topological degeneracy of ground states in a protected
subspace, like that proposed by [Kitaev 2003 ] with adiabatic evolution or
quantum gates. Bose and Hutton investigated a central spin that interacted
with a set of peripheral spins at low temperature [Bose/Hutton 2004]. That
system is directly analogous to the one we are designing here, except instead
of spins we take the quantum numbers associated with the trapped fluxes as the
pertinent states. The central vortex will entangle with the other vortices at
low temperature with a dependence on the total number of vortices in the
system.

## References

  * [1] D. Davidovic̀, S. Kumar, D. H. Reich, J. Siegel, S. B. Field, R. C. Tiberio, R. Hey, and K. Ploog.  Correlations and disorder in arrays of magnetically coupled superconducting rings.  Phys. Rev. Lett., 76(5):815–818, 1996.
  * [2] M. Forrester, K. Kurten, and F. Kusmartsev.  Fractal metamaterials composed of electrically isolated $\pi$-rings.  Sci. Lett. J., 4:133, 2015.
  * [3] M. Forrester and F. Kusmartsev.  Whispering galleries and the control of artificial atoms.  Scientific reports, 6:25084, 2016.
  * [4] S. M. Frolov, M. J. A. Stoutimore, T. A. Crane, D. J. Van Harlingen, V. A. Oboznov, V. V. Ryazanov, A. Ruosi, C. Granata, and M. Russo.  Imaging spontaneous currents in superconducting arrays of $\pi$ -junctions.  Nature Physics, 4:32–36, 2008.
  * [5] H. Hilgenkamp, Ariando, H. J. H. Smilde, D. H. A. Blank, G. Rijnders, H. Rogalla, J. R. Kirtley, and C. C. Tsuei.  Ordering and manipulation of the magnetic moments in large-scale superconducting $\pi$-loop arrays.  Nature, 422:50–53, 2003.
  * [6] L. B. Ioffe and M. V. Feigel’man.  Realization of topologically protected quantum bits in a josephson junction array.  Phys. Usp., 46:759–764, 2003.
  * [7] L. B. Ioffe, M. V. Feigel’man, A. Ioselevich, D. Ivanov, M. Troyer, and G. Blatter.  Topologically protected quantum bits using josephson junction arrays.  Nature, 415:503–506, 2002.
  * [8] M. R. Kolahchi and J. P. Straley.  Ground state of the uniformly frustrated two-dimensional $xy$ model near $f=1/2$.  Phys. Rev. B., 43:7651–7654, 1991.
  * [9] F. V. Kusmartsev, D.M. Faruque, and D. I. Khomskii.  Quasiclassical method for a josephson network in a magnetic field.  Physics Letters A, 249:541–554, 1998.
  * [10] T. Yamashita, K. Tanikawa, S. Takahashi, and S. Maekawa.  Superconducting $\pi$ qubit with a ferromagnetic josephson junction.  Phys. Rev. Lett., 95:097001, 2005.


#  Perfect State Transfer on semi-Cayley graphs over abelian groups

Majid Arezoomand a 111E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
a University of Larestan, Lar, 74317-16137, Iran

###### Abstract

In this paper, we consider the problem on the existence of perfect state
transfer (PST for short) on semi-Cayley graphs over abelian groups (which are
not necessarily regular), i.e on the graphs having semiregular and abelian
subgroups of automorphisms with two orbits of equal size. We stablish a
characterization of semi-Cayley graphs over abelian groups having PST. As a
result, we give a characterization of Cayley graphs over groups with an
abelian subgroup of index $2$ having PST, which improves the earlier results
on Cayley graphs over abelian groups, dihedral groups and dicyclic group and
determines Cayley graphs over generalized dihedral groups and generalized
dicyclic groups having PST.

Keywords: Perfect state transfer, Semi-Cayley graph, Eigenvalue of a graph
Mathematics Subject Classification: 05C25, 81P45, 15A18.

##  1 Introduction

Let $\Gamma$ be a simple undirected graph with adjacency matrix $A$. The
continuous-time quantum walk on $\Gamma$ is defined through the time-dependent
unitary matrix

$\displaystyle H(t)=\exp(-{\bf i}tA)=\sum_{k=0}^{\infty}\frac{(-{\bf
i})^{k}t^{k}A^{k}}{k!},~{}~{}~{}0<t\in\mathbb{R},~{}{\bf i}=\sqrt{-1}.$

This concept first introduced by Farhi and Gutman by a motivation of the
Schrödinger equation. They used it as a paradigm to design efficient quantum
algorithms [9].

The significance of the study of quantum state transfer lies in its
applications to the theory of Quantum Information and Computation. In fact,
one of the cruical ingredients in most of quantum information processing
protocols is the transfer of a quantum state from one location to another
location. Quantum spin network is an example of physical systems that can
serve as a quantum channel. By considering the networks as graphs, in
algebraic graph theory, one of the main questions is to find a
characterization of graphs having perfect state transfer. We say that a graph
$\Gamma$ has a perfect state transfer (PST for short) from the vertex $u$ to
the vertex $v$ at time $t$ if the $(u,v)$-entry of $H(t)$, denoted by
$H_{u,v}(t)$, has absolute value $1$. If $|H_{u,u}(t)|=1$ then we say that
$\Gamma$ is periodic at $u$ with period $t$. $\Gamma$ is called periodic if it
is periodic at all vertices with period $t$.

Recently, the problem of characterization of graphs having PST has been one of
the interesting topics in algebraic graph theory. For a survey on this topic
and its related question, up to 2011, we refer the reader to [10, 11, 12].
Godsil has showed that if perfect state transfer occurs in a graph, then the
square of its spectral radius is either an integer or lies in a quadratic
extension of the rationales [12]. Moreover, existence of PST has been obtained
for some particular classes of graphs, for example, distance-regular graphs
[7, 8], Hadamard diagonalizable graphs [15] and complete bipartite graphs
[17]. Also some authors studied the PST problem of Cayley graphs due to their
nice algebraic structures. A characterization of Cayley graphs over abelian
group, dihedral groups with conjugate-closed Cayley set, dihedral groups with
non-conjugate-closed Cayley set, dicyclic groups and also over semidihedral
groups are given in [18, 6, 5, 3, 16], respectively. Despite many results on
PST on graphs, there are no known constructions of PST on non-abelian Cayley
graphs in literature.

The purpose of this paper is two-fold: First we present an explicit general
method to find the eigenvalues and eigenvectors of the semi-Cayley graphs over
abelian groups which facilitates the computations of PST. Many families of
well-known graphs are examples of semi-Cayley graphs over abelian groups, such
as bicirculants (including I-graphs, the generalized Petersen graphs, rose
window graphs, Tabačjn graphs, $n$-gonal $n$-cone graphs), $n$-sunlet graphs,
and the join graph of two Cayley graphs over the same group, also all Cayley
graphs over groups having a subgroup of index $2$. So we provide a way to
characterize a large family of graphs having PST. Secondly, a vital step for
making further progress on existence of PST on Cayley graphs over non-abelian
groups. Since any Cayley graph over a group $G$ having subgroup $H$ of index
$2$ is a semi-Cayley graph over $H$, the main results of [18, 6, 5, 3, 16] are
direct consequences of our results. Also as a result, we investigate the
existence of PST on Cayley graphs over generalized dihedral groups and
generalized dicyclic groups.

The rest of the current work is organized as follows. In Section 2, we present
some comments and notations used in the next sections. In Section 3, we give
exact formula for the eigenvalues and eigenvectors of semi-Cayley graphs over
abelian groups. Finally,the existence of PST on semi-Cayley graphs over
abelian groups is explored in Section 4 and as a result we improve some
earlier results. Also, we characterize all Cayley graphs over generalized
dihedral groups and generalized dicyclic groups having PST.

##  2 Preliminaries and notations

Here we recall some of the standard facts and notation used in this paper. Our
notation for representations and characters of finite groups is due to the
notation introduced in [14]. Throughout this paper, graphs are finite, simple
and undirected, and also groups are finite.

###  2.1 Spectrum of a graph and PST

Let $\Gamma$ be an undirected graph with adjacency matrix $A$ and
$H(t)=\exp(-{\bf i}tA)$. The eigenvalues of $A$ are called (adjacency)
eigenvalues of $\Gamma$. $\Gamma$ is called integral if all of its eigenvalues
are integers. Let $\Gamma$ has $m$ vertices and
$\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{m}$ be the eigenvalues of
$\Gamma$, $v_{i}$ is a column eigenvector of $\lambda_{i}$ and
$\\{v_{1},\ldots,v_{m}\\}$ is an orthonormal basis of $\mathbb{C}^{m}$. Then,
since $A$ is a real symmetric matrix, by the Spectral Decomposition Theorem
[19, Theorem 3.4],

$H(t)=\sum_{i=1}^{m}\exp(-{\bf i}t\lambda_{i})E_{i},$

where $E_{i}=v_{i}.v_{i}^{*}$, where $v_{i}^{*}$ is the conjugate transpose of
$v_{i}$. So $\Gamma$ has a PST from the vertex $u$ to the vertex $v$ if and
only if the the absolute value of the $(u,v)$-entry of
$\sum_{i=1}^{m}\exp(-{\bf i}t\lambda_{i})E_{i}$ is equal to $1$.

###  2.2 Cayley graphs and semi-Cayley graphs

Given a group $G$ and an inverse-closed subset of $G$, the Cayley graph of $G$
with respect to the Cayley set $S$, denoted by ${\rm Cay}(G,S)$, is a graph
with vertex set $G$ and edge-set $\\{\\{g,sg\\}\mid s\in S\\}$. Clearly ${\rm
Cay}(G,S)$ is a vertex-transitive $|S|$-regular graph.

As a generalization of Cayley graphs, see [1, page 2], semi-Cayley graphs are
introduced. Let $G$ be a finite group, $R,L$ and $S$ be subsets of $G$ such
that $R$ and $L$ are inverse-closed subsets not containing the identity
element of $G$. The semi-Cayley graph over $G$ with respect to $R$, $L$ and
$S$, denoted by ${\rm SC}(G,R,L,S)$ is an undirected graph with vertex set
$\\{(g,0),(g,1)\mid g\in G\\}$ and edge set consists of three sets:

$\displaystyle\\{\\{(x,0),(y,0)\\}\mid yx^{-1}\in R\\}\ \ \ (\textrm{right
edges}),$ $\displaystyle\\{\\{(x,1),(y,1)\\}\mid yx^{-1}\in L\\}\ \ \
(\textrm{left edges}),$ $\displaystyle\\{\\{(x,0),(y,1)\\}\mid yx^{-1}\in
S\\}\ \ \ (\textrm{spoke edges}).$

Clearly ${\rm SC}(G,R,L,S)$ is a regular graph if and only if $|R|=|L|$. By
the following result, every Cayley graph over a group having a subgroup of
index $2$ is a semi-Cayley graph. Note that the converse is not true, since as
an example the Petersen graph is a semi-Cayley graph over the cyclic group
$\mathbb{Z}_{5}$ and it not a Cayley graph. We will use this fact frequently
without referring it.

######  Lemma 2.1.

(see [1, Lemma 8]) Let $\Gamma={\rm Cay}(G,T)$, and $H$ be a subgroup of $G$
of index $2$ with left transversal $\\{1,x\\}$. Then $\Gamma\cong{\rm
SC}(H,R,L,S)$, where $R=H\cap T$, $L=H\cap xTx^{-1}$ and $S=H\cap xT$.

###  2.3 Irreducible characters of finite abelian groups

In this paper, we need irreducible characters of finite abelian groups. For
the definitions and basic facts about representations and characters of finite
groups, not defined here, we refer the reader to [14]. Let $G$ be an abelian
group of order $n$. It is well-known that every finite abelian group is a
direct product of cyclic groups. Let $\mathbb{Z}_{r}$ be a cyclic group of
order $r$. Then we may assume that $G=\langle g_{1}\rangle\times\langle
g_{2}\rangle\times\ldots\times\langle g_{k}\rangle$ where $k\geq 1$ and
$n=n_{1}n_{2}\ldots n_{k}$ and $\langle g_{l}\rangle\cong\mathbb{Z}_{n_{l}}$.
Let ${\rm Irr}(G)$ be the set of all inequivalent complex irreducible
characters of $G$. Then, by [14, Theorem 9.8], ${\rm
Irr}(G)=\\{\chi_{j_{1},\ldots,j_{k}}\mid 0\leq j_{l}\leq
n_{l},l=1,\ldots,k\\}$, where

$\chi_{j_{1},\ldots,j_{k}}:G\rightarrow\mathbb{C},~{}~{}~{}(g_{1}^{i_{1}},\ldots,g_{k}^{i_{k}})\mapsto\exp(\frac{2\pi{\bf
i}j_{1}i_{1}}{n_{1}})\ldots\exp(\frac{2\pi{\bf i}j_{k}i_{k}}{n_{k}}).$

The character $\chi_{0,\ldots,0}$ is the trivial character and in the rest of
paper, we denote it by $\chi_{1}$. It is clear that for every $g\in G$ and
$\chi\in{\rm Irr}(G)$, we have $|\chi(g)|=1$. For a character of $G$ and a
subset $X$ of $G$, we denote $\sum_{x\in X}\chi(x)$ with $\chi(X)$ and if
$X=\emptyset$ then we put $\chi(X)=0$.

##  3 Spectra of semi-Cayley graphs over abelian groups

Let $\Gamma={\rm SC}(G,R,L,S)$ be a semi-Cayley graph over an abelian group
$G$. Let $G=\\{g_{1},\ldots,g_{n}\\}$ and ${\rm
Irr}(G)=\\{\chi_{1}=1,\ldots,\chi_{n}\\}$ be the set of all inequivalent
irreducible characters of $G$. For $1\leq i\leq n$, we define the matrix

$\displaystyle A_{i}=\begin{bmatrix}\chi_{i}(R)&\chi_{i}(S)\\\
\overline{\chi_{i}(S)}&\chi_{i}(L)\end{bmatrix},$

where $\overline{\chi_{i}(S)}$ is the complex conjugate of $\chi_{i}(S)$. Note
that since $R$ and $L$ are inverse-closed, $\chi_{i}(R)$ and $\chi_{i}(L)$ are
real numbers by [14, Proposition 13.9]. Then eigenvalues of $A_{i}$ are

$\displaystyle\lambda_{i}^{+}=\frac{1}{2}\big{(}\chi_{i}(R)+\chi_{i}(L)+\sqrt{(\chi_{i}(R)-\chi_{i}(L))^{2}+4|\chi_{i}(S)|^{2}}\big{)},$

and

$\displaystyle\lambda_{i}^{-}=\frac{1}{2}\big{(}\chi_{i}(R)+\chi_{i}(L)-\sqrt{(\chi_{i}(R)-\chi_{i}(L))^{2}+4|\chi_{i}(S)|^{2}}\big{)}.$

Let $u_{i}^{+}=(a_{i}^{+},b_{i}^{+})$ and $u_{i}^{-}=(a_{i}^{-},b_{i}^{-})$ be
an eigenvector of $A_{i}$ corresponding to $\lambda_{i}^{+}$ and
$\lambda_{i}^{-}$, respectively. Then

$\displaystyle
b_{i}^{+}\chi_{i}(S)=\frac{-x_{i}+\sqrt{x_{i}^{2}+4|\chi_{i}(S)|^{2}}}{2}a_{i}^{+},~{}~{}~{}a_{i}^{+}\overline{\chi_{i}(S)}=\frac{x_{i}+\sqrt{x_{i}^{2}+4|\chi_{i}(S)|^{2}}}{2}b_{i}^{+},$
(1)

and

$\displaystyle
b_{i}^{-}\chi_{i}(S)=\frac{-x_{i}-\sqrt{x_{i}^{2}+4|\chi_{i}(S)|^{2}}}{2}a_{i}^{-},~{}~{}~{}a_{i}^{-}\overline{\chi_{i}(S)}=\frac{x_{i}-\sqrt{x_{i}^{2}+4|\chi_{i}(S)|^{2}}}{2}b_{i}^{-}$
(2)

where $x_{i}=\chi_{i}(R)-\chi_{i}(L)\in\mathbb{R}$. If $\chi_{i}(S)=0$, then
we may assume that $\lambda_{i}^{+}=\chi_{i}(R)$,
$\lambda_{i}^{-}=\chi_{i}(L)$, $(a_{i}^{+},b_{i}^{+})=(1,0)$ and
$(a_{i}^{-},b_{i}^{-})=(0,1)$. Let
$c_{i}^{+}=\frac{|a_{i}^{+}|^{2}}{|a_{i}^{+}|^{2}+|b_{i}^{+}|^{2}}$,
$c_{i}^{-}=\frac{|a_{i}^{-}|^{2}}{|a_{i}^{-}|^{2}+|b_{i}^{-}|^{2}}$,
$d_{i}^{+}=\frac{|b_{i}^{+}|^{2}}{|a_{i}^{+}|^{2}+|b_{i}^{+}|^{2}}$,
$d_{i}^{-}=\frac{|b_{i}^{-}|^{2}}{|a_{i}^{-}|^{2}+|b_{i}^{-}|^{2}}$,
$e_{i}^{+}=\frac{a_{i}^{+}\overline{b_{i}^{+}}}{|a_{i}^{+}|^{2}+|b_{i}^{+}|^{2}}$
and
$e_{i}^{-}=\frac{a_{i}^{-}\overline{b_{i}^{-}}}{|a_{i}^{-}|^{2}+|b_{i}^{-}|^{2}}$.
If $\chi_{i}(S)\neq 0$, then

$\displaystyle
c_{i}^{+}=\frac{|x_{i}+\sqrt{x_{i}^{2}+4|\chi_{i}(S)|^{2}}|^{2}}{|x_{i}+\sqrt{x_{i}^{2}+4|\chi_{i}(S)|^{2}}|^{2}+4|\chi_{i}(S)|^{2}},$
$\displaystyle
c_{i}^{-}=\frac{|x_{i}-\sqrt{x_{i}^{2}+4|\chi_{i}(S)|^{2}}|^{2}}{|x_{i}-\sqrt{x_{i}^{2}+4|\chi_{i}(S)|^{2}}|^{2}+4|\chi_{i}(S)|^{2}},$
$\displaystyle
d_{i}^{+}=\frac{4|\chi_{i}(S)|^{2}}{|x_{i}+\sqrt{x_{i}^{2}+4|\chi_{i}(S)|^{2}}|^{2}+4|\chi_{i}(S)|^{2}},$
$\displaystyle
d_{i}^{-}=\frac{4|\chi_{i}(S)|^{2}}{|x_{i}-\sqrt{x_{i}^{2}+4|\chi_{i}(S)|^{2}}|^{2}+4|\chi_{i}(S)|^{2}},$
$\displaystyle
e_{i}^{+}=2\chi_{i}(S)\frac{x_{i}+\sqrt{x_{i}^{2}+4|\chi_{i}(S)|^{2}}}{|x_{i}+\sqrt{x_{i}^{2}+4|\chi_{i}(S)|^{2}}|^{2}+4|\chi_{i}(S)|^{2}},$
$\displaystyle
e_{i}^{-}=-2\chi_{i}(S)\frac{x_{i}+\sqrt{x_{i}^{2}+4|\chi_{i}(S)|^{2}}}{|x_{i}+\sqrt{x_{i}^{2}+4|\chi_{i}(S)|^{2}}|^{2}+4|\chi_{i}(S)|^{2}},.$

Furthermore, by [1, Lemma 11],

$v_{i}^{+}=\frac{1}{\sqrt{n(|a_{i}^{+}|^{2}+|b_{i}^{+}|^{2})}}(a_{i}^{+}\chi_{i}(g_{1}^{-1}),\ldots,a_{i}^{+}\chi_{i}(g_{n}^{-1}),b_{i}^{+}\chi_{i}(g_{1}^{-1}),\ldots,b_{i}^{+}\chi_{i}(g_{n}^{-1}))^{T}$

and

$v_{i}^{-}=\frac{1}{\sqrt{n(|a_{i}^{-}|^{2}+|b_{i}^{-}|^{2})}}(a_{i}^{-}\chi_{i}(g_{1}^{-1}),\ldots,a_{i}^{-}\chi_{i}(g_{n}^{-1}),b_{i}^{-}\chi_{i}(g_{1}^{-1}),\ldots,b_{i}^{-}\chi_{i}(g_{n}^{-1}))^{T}$

, where $x^{T}$ is the transpose of vector $x$, are eigenvectors of $\Gamma$
corresponding to $\lambda_{i}^{+}$ and $\lambda_{i}^{-}$, respectively, and
$\\{v_{i}^{+},v_{i}^{-}\mid 1\leq i\leq n\\}$ is an orthonormal basis of
$\mathbb{C}^{2n}$. Let $E_{i}^{+}=v_{i}^{+}.(v_{i}^{+})^{*}$ and
$E_{i}^{-}=v_{i}^{-}.(v_{i}^{-})^{*}$. Then we have

$\displaystyle
E_{i}^{+}=\frac{1}{n(|a_{i}^{+}|^{2}+|b_{i}^{+}|^{2})}\begin{bmatrix}|a_{i}^{+}|^{2}B&a_{i}^{+}\overline{b_{i}^{+}}B\\\
b_{i}^{+}\overline{a_{i}^{+}}B&|b_{i}^{+}|^{2}B\end{bmatrix},~{}~{}~{}~{}E_{i}^{-}=\frac{1}{n(|a_{i}^{-}|^{2}+|b_{i}^{-}|^{2})}\begin{bmatrix}|a_{i}^{-}|^{2}B&a_{i}^{-}\overline{b_{i}^{-}}B\\\
b_{i}^{-}\overline{a_{i}^{-}}B&|b_{i}^{-}|^{2}B\end{bmatrix},$

where $B=[\chi_{i}(g_{r}^{-1}g_{s})]_{1\leq r,s\leq n}$. We keep these
notations throughout the paper.

##  4 PST on semi-Cayley graphs over abelian groups

Let us first give some relations between PST on Cayley graphs and semi-Cayley
graphs.

######  Lemma 4.1.

Let $\Gamma={\rm SC}(G,R,L,\emptyset)$. Then $\Gamma$ has a PST from $(g,r)$
to $(h,s)$ if and only if $r=s=0$ and ${\rm Cay}(G,R)$ has a PST from $g$ to
$h$, or $r=s=1$ and ${\rm Cay}(G,L)$ has a PST from $g$ to $h$.

Proof. Let $A$, $B$ and $C$ be the adjacency matrices of $\Gamma$, ${\rm
Cay}(G,R)$ and ${\rm Cay}(G,L)$, respectively. Then $A=\begin{bmatrix}B&0\\\
0&C\end{bmatrix}$, which implies that $H_{A}(t)=\begin{bmatrix}H_{B}(t)&0\\\
0&H_{C}(t)\end{bmatrix}$. Now the result is straightforward.
$\hfill\blacksquare$

The proof of the following lemma is similar to [4, Theorem 1]. We give it for
completeness.

######  Lemma 4.2.

Let $X={\rm Cay}(G,R)$ and $\Gamma={\rm SC}(G,R,R,S)$, where $G$ is an abelian
group. Let $A$, $B$ and $C$ be the adjacency matrices of $\Gamma$, $X$ and
${\rm Cay}(G,S)$ (may be directed, or having loops), respectively. Then

$H_{A}(t)=\begin{bmatrix}H_{B}(t)D_{1}&CD_{2}\\\
C^{T}D_{2}&H_{B}(t)D_{1}\end{bmatrix},$

where $D_{1}=\sum_{k=0}^{\infty}\frac{(-{\bf
i}t)^{2k}}{(2k)!}(CC^{T})^{k}=\cos(t\sqrt{CC^{T}})$ and
$D_{2}=\sum_{k=0}^{\infty}\frac{(-{\bf i}t)^{2k+1}}{(2k+1)!}(CC^{T})^{k}=-{\bf
i}(CC^{T})^{\frac{-1}{2}}\sin(t\sqrt{CC^{T}})$ where the second equality for
$D_{2}$ holds if $\det(C)\neq 0$. Furthermore, if $X$ has a PST from $g$ to
$h$ at time $t$, then

  * (1)

$\Gamma$ has a PST from $(g,0)$ to $(h,0)$ and from $(g,1)$ to $(h,1)$ at time
$t$, whenever $t\in\mathbb{Z}\pi$ and $CC^{T}=I$.

  * (2)

$\Gamma$ has a PST from $(g,0)$ to $(h,1)$ at time $t$, whenever
$t\in(2\mathbb{Z}+1)\frac{\pi}{2}$ and $S=\\{1\\}$.

Proof. Suppose that $G=\\{g_{1},g_{2},\ldots,g_{n}\\}$ and consider the
ordering

$(g_{1},0),\ldots,(g_{n},0),(g_{1},1),\ldots,(g_{n},1)$

for the vertices of $\Gamma$. Then $A=I_{2}\otimes B+(P\otimes C+Q\otimes
C^{T})$, where $I_{2}$ is the $2\times 2$ identity matrix,
$P=\begin{bmatrix}0&1\\\ 0&0\end{bmatrix}$ and $Q=\begin{bmatrix}0&0\\\
1&0\end{bmatrix}$. Since $G$ is abelian, $CC^{T}=C^{T}C$, $BC=CB$ and
$BC^{T}=C^{T}B$. Also we have $P^{2}=Q^{2}=0_{2}$ and $PQ+QP=I_{2}$, where
$0_{2}$ is the $2\times 2$ all $0$ matrix. Let $D=P\otimes C+Q\otimes C^{T}$.
Then

$(I_{2}\otimes
B)D=P\otimes(BC)+Q\otimes(BC^{T})=P\otimes(CB)+Q\otimes(C^{T}B)=D(I_{2}\otimes
B),$

and so $\exp(-{\bf i}tA)=\exp(-{\bf i}t(I_{2}\otimes B))\exp(-{\bf
i}tD)=(I_{2}\otimes\exp(-{\bf i}tB))\exp(-{\bf i}tD)$. On the other hand,

$D^{2k}=I_{2}\otimes(CC^{T})^{k},~{}~{}D^{2k+1}=P\otimes
C(CC^{T})^{k}+Q\otimes C^{T}(CC^{T})^{k},~{}~{}\forall~{}k\geq 0.$

This implies that

$H_{A}(t)=\exp(-{\bf i}tA)=\begin{bmatrix}\exp(-{\bf i}tB)D_{1}&CD_{2}\\\
C^{T}D_{2}&\exp(-{\bf
i}tB)D_{1}\end{bmatrix}=\begin{bmatrix}H_{B}(t)D_{1}&CD_{2}\\\
C^{T}D_{2}&H_{B}(t)D_{1}\end{bmatrix},$

where $D_{1}=\sum_{k=0}^{\infty}\frac{(-{\bf
i}t)^{2k}}{(2k)!}(CC^{T})^{k}=\cos(t\sqrt{CC^{T}})$ and
$D_{2}=\sum_{k=0}^{\infty}\frac{(-{\bf i}t)^{2k+1}}{(2k+1)!}(CC^{T})^{k}=-{\bf
i}(CC^{T})^{\frac{-1}{2}}\sin(t\sqrt{CC^{T}})$ where the second equality for
$D_{2}$ holds if $\det(C)\neq 0$. $\hfill\blacksquare$

In the rest of paper, we study the PST of semi-Cayley graphs in general using
spectra of these graphs. Let $\Gamma={\rm SC}(G,R,L,S)$ be a semi-Cayley graph
over an abelian group $G$, $A$ be its adjacency matrix and $H(t)=\exp(-{\bf
i}tA)$. By the notations of the previous section and the Spectral
Decomposition Theorem, we have

$A=\lambda_{1}^{+}E_{1}^{+}+\lambda_{1}^{-}E_{1}^{-}+\ldots+\lambda_{n}^{+}E_{n}^{+}+\lambda_{n}^{-}E_{n}^{-},$

and therefore we have the decomposition of the transfer matrix as follows:

$H(t)=\exp(-{\bf i}\lambda_{1}^{+}t)E_{1}^{+}+\exp(-{\bf
i}\lambda_{1}^{-}t)E_{1}^{-}+\ldots+\exp(-{\bf
i}\lambda_{n}^{+}t)E_{n}^{+}+\exp(-{\bf i}\lambda_{n}^{-}t)E_{n}^{-}.$

Let $u=(g,r)$ and $v=(h,s)$ be two vertices of $\Gamma$, where
$r,s\in\\{0,1\\}$. Then

$\displaystyle
H_{u,v}(t)=\left\\{\begin{array}[]{ll}\frac{1}{n}\sum_{i=1}^{n}\Big{(}c_{i}^{+}\exp(-{\bf
i}\lambda_{i}^{+}t)+c_{i}^{-}\exp(-{\bf
i}\lambda_{i}^{-}t)\Big{)}\chi_{i}(g^{-1}h)&r=s=0\\\
\frac{1}{n}\sum_{i=1}^{n}\Big{(}d_{i}^{+}\exp(-{\bf
i}\lambda_{i}^{+}t)+d_{i}^{-}\exp(-{\bf
i}\lambda_{i}^{-}t)\Big{)}\chi_{i}(g^{-1}h)&r=s=1\\\
\frac{1}{n}\sum_{i=1}^{n}\Big{(}e_{i}^{+}\exp(-{\bf
i}\lambda_{i}^{+}t)+e_{i}^{-}\exp(-{\bf
i}\lambda_{i}^{-}t)\Big{)}\chi_{i}(g^{-1}h)&r=0,s=1\\\
\frac{1}{n}\sum_{i=1}^{n}\Big{(}\overline{e_{i}^{+}}\exp(-{\bf
i}\lambda_{i}^{+}t)+\overline{e_{i}^{-}}\exp(-{\bf
i}\lambda_{i}^{-}t)\Big{)}\chi_{i}(g^{-1}h)&r=1,s=0\end{array}\right.$ (7)

######  Lemma 4.3.

Keeping the above notations, we have

  * (i)

if $\chi_{i}(S)=0$ then $c_{i}^{+}=d_{i}^{-}=1$,
$c_{i}^{-}=d_{i}^{+}=e_{i}^{+}=e_{i}^{-}=0$ and if $\chi_{i}(S)\neq 0$ then
$e_{i}^{+}+e_{i}^{-}=0$, and $0<c_{i}^{+},c_{i}^{-},d_{i}^{+},d_{i}^{-}<1$.
Furthermore, for each $i$, we have $c_{i}^{+}+c_{i}^{-}=1$,
$0<d_{i}^{+}+d_{i}^{-}\leq 1$, $|e_{i}^{+}|=|e_{i}^{-}|\leq\frac{1}{2}$ and so
$|e_{i}^{+}|+|e_{i}^{-}|\leq 1$.

  * (ii)

Then for all $i$ with $\chi_{i}(S)\neq 0$, we have $e_{i}^{+}\neq e_{i}^{-}$
and

$\displaystyle c_{i}^{+}=c_{i}^{-}\Leftrightarrow
d_{i}^{+}=d_{i}^{-}\Leftrightarrow x_{i}=0$

  * (iii)

$|H_{u,v}(t)|\leq 1$ for all $u,v$.

Proof. By a tedious computation, one can proof $(i)$ and $(ii)$. Since $G$ is
abelian, for each $g\in G$ and $\chi\in{\rm Irr}(G)$ we have $|\chi(g)|=1$. So
the last part follows from the first part and equality (7).
$\hfill\blacksquare$

Let $z_{1},\ldots,z_{k}\in\mathbb{C}$. Then, it is easy to see that
$|z_{1}+\ldots+z_{k}|=|z_{1}|+\ldots+|z_{k}|$ if and only if $z_{j}$’s have
the same argument. We use this fact in the following lemma.

######  Lemma 4.4.

Let $G$ be a finite abelian group of order $n$, ${\rm
Irr}(G)=\\{\chi_{1},\ldots,\chi_{n}\\}$, where $\chi_{1}$ is the trivial
character of $G$, $\Gamma={\rm SC}(G,R,L,S)$ and
$X=\\{i\mid\chi_{i}(S)=0,1\leq i\leq n\\}$. Let $u=(g,r)$, $v=(h,s)$ be two
vertices and $a=g^{-1}h$. Then $\Gamma$ has a PST from $u$ to $v$ at time $t$
if and only if one of the following holds

  * (1)

$r=s=0$ and

$\displaystyle\chi_{i}(a)$ $\displaystyle=$ $\displaystyle\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{i}^{+})t)~{}~{}~{}\forall i=1,\ldots,n,$
$\displaystyle\chi_{j}(a)$ $\displaystyle=$ $\displaystyle\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{-})t)~{}~{}~{}\forall j\notin X,$

  * (2)

$r=s=1$ and

$\displaystyle\chi_{i}(a)$ $\displaystyle=$ $\displaystyle\exp(-{\bf
i}(\lambda_{1}^{-}-\lambda_{i}^{-})t)~{}~{}~{}\forall i=1,\ldots,n,$
$\displaystyle\chi_{j}(a)$ $\displaystyle=$ $\displaystyle\exp(-{\bf
i}(\lambda_{1}^{-}-\lambda_{j}^{+})t)~{}~{}~{}\forall j\notin X,$

  * (3)

$r=0,s=1$, $X=\emptyset$ and for all $j=1,\ldots,n$

$\displaystyle\chi_{j}(a)$ $\displaystyle=$
$\displaystyle\frac{|\chi_{j}(S)|}{\chi_{j}(S)}\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t),$ $\displaystyle\exp(-{\bf
i}\lambda_{j}^{+}t)$ $\displaystyle=$ $\displaystyle-\exp(-{\bf
i}\lambda_{j}^{-}t),$

and $R=L$,

  * (4)

$r=1,s=0$, $X=\emptyset$ and for all $j=1,\ldots,n$

$\displaystyle\chi_{j}(a)$ $\displaystyle=$
$\displaystyle\frac{|\chi_{j}(S)|}{\overline{\chi_{j}(S)}}\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t),$ $\displaystyle\exp(-{\bf
i}\lambda_{j}^{+})t$ $\displaystyle=$ $\displaystyle-\exp(-{\bf
i}\lambda_{j}^{-}t)$

and $R=L$.

Proof. By Lemma 4.3, $|H_{u,v}(t)|\leq 1$ for all $u,v$. Let $\Gamma$ has a
PST from $u$ to $v$. Then $|H_{u,v}(t)|=1$. Now the argument of all terms of
the summation given in (7) are the same number. First suppose that $r=s=0$.
Then

$\displaystyle\exp(-{\bf i}\lambda_{i}^{+}t)\chi_{i}(a)=\exp(-{\bf
i}\lambda_{1}^{+}t)=\exp(-{\bf i}\lambda_{j}^{-}t)\chi_{j}(a),~{}\forall
i=1,\ldots,n,~{}\forall j\notin X,$

and therefore

$\displaystyle\chi_{i}(a)$ $\displaystyle=$ $\displaystyle\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{i}^{+})t)~{}~{}~{}i=1,\ldots,n,$
$\displaystyle\chi_{j}(a)$ $\displaystyle=$ $\displaystyle\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{-})t)~{}~{}~{}j\notin X.$

Similarly, one can proof the result for the case $r=s=1$.

Now let $r=0$ and $s=1$. Then $H_{u,v}(t)=\frac{1}{n}\sum_{j\notin
X}\Big{(}e_{j}^{+}\exp(-{\bf i}\lambda_{j}^{+}t)+e_{j}^{-}\exp(-{\bf
i}\lambda_{j}^{-}t)\Big{)}\chi_{j}(g^{-1}h)$. Since
$|e_{j}^{+}|+|e_{j}^{-}|\leq 1$, we have
$1=|H_{u,v}(t)|\leq\frac{1}{n}(n-|X|)$, which means that $X=\emptyset$, i.e
for each $j=1,\ldots,n$, $\chi_{j}(S)\neq 0$. Furthermore,
$e_{j}^{-}=-e_{j}^{+}$, and so

$H_{u,v}(t)=\frac{1}{n}\sum_{j=1}^{n}e_{j}^{+}\Big{(}\exp(-{\bf
i}\lambda_{j}^{+}t)-\exp(-{\bf i}\lambda_{j}^{-}t)\Big{)}\chi_{j}(g^{-1}h).$

For each $j$, let $\theta_{j}^{+}$ be the argument of $e_{j}^{+}$. Then
$\exp({\bf i}\theta_{j}^{+})=\frac{\chi_{j}(S)}{|\chi_{j}(S)|}$. Again, since
$|H_{u,v}(t)|=1$, the argument of all terms of $H_{u,v}(t)$ are the same
number. Hence

$\arg(e_{j}^{+}\exp(-{\bf
i}\lambda_{j}^{+}t)\chi_{j}(g^{-1}h))=\arg(-e_{j}^{+}\exp(-{\bf
i}\lambda_{j}^{-}t)\chi_{j}(g^{-1}h))=\arg(\exp(-{\bf i}\lambda_{1}^{+}t)),$

which implies that

$e_{j}^{+}\Big{(}\exp(-{\bf i}\lambda_{j}^{+}t)-\exp(-{\bf
i}\lambda_{j}^{-}t)\Big{)}\chi_{j}(g^{-1}h)=0,~{}~{}~{}\chi_{j}(g^{-1}h)=\frac{|\chi_{j}(S)|}{\chi_{j}(S)}\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})).$

We have $\chi_{j}(g^{-1}h)\neq 0$ and also $e_{j}^{+}\neq 0$ since
$\chi_{j}(S)\neq 0$. Thus the first equality implies that $\exp(-{\bf
i}\lambda_{j}^{+}t)=-\exp(-{\bf i}\lambda_{j}^{-}t)$. Hence

$H_{u,v}(t)=\frac{1}{n}\sum_{j=1}^{n}2e_{j}^{+}\exp(-{\bf
i}\lambda_{j}^{+}t)\chi_{j}(g^{-1}h)=\frac{1}{n}\sum_{j=1}^{n}2e_{j}^{+}\frac{|\chi_{j}(S)|}{\chi_{j}(S)}.$

Since $|2e_{j}^{+}\frac{|\chi_{j}(S)|}{\chi_{j}(S)}|\leq 1$ and
$|H_{u,v}(t)|=1$, for all $j=1,\ldots,n$, we have
$e_{j}^{+}=\frac{|\chi_{j}(S)|}{2\chi_{j}(S)}$, which implies that $x_{j}=0$.
Thus we have proved that $\chi_{j}(R)=\chi_{j}(L)$ for all $j=1,\ldots,n$.
Now, by the column orthogonality relations of characters [14, p. 161], for all
$g\in G$ we have

$\displaystyle\sum_{i=1}^{n}\chi_{i}(g^{-1})\chi_{i}(R)=\sum_{i=1}^{n}\sum_{x\in
R}\chi_{i}(g^{-1})\chi_{i}(x)=\sum_{x\in
R}\sum_{i=1}^{n}\chi_{i}(g^{-1})\chi_{i}(x)=|G|\sum_{x\in R}\delta_{xg},$

and similarly $\sum_{i=1}^{n}\chi_{i}(g^{-1})\chi_{i}(L)=|G|\sum_{y\in
L}\delta_{yg}$, where $\delta$ is the characteristic function. Therefore,
$\sum_{x\in R}\delta_{xg}=\sum_{y\in L}\delta_{yg}$ for all $g\in G$. This
implies that $R=L$.

To prove the last part, it is enough to note that we have to consider the
complex conjugates of $e_{j}^{+}$ and $e_{j}^{-}$ is the summation. The
converse direction is straightforward. This completes the proof.
$\hfill\blacksquare$

######  Remark 1.

Since $1\notin X$ if and only if $S\neq\emptyset$, by Lemma 4.4 if
$S\neq\emptyset$ and $\Gamma$ has a PST at time $t$ between two pairs
$u=(g,r),v=(h,s)$ and
$u^{\prime}=(g^{\prime},r^{\prime}),v^{\prime}=(h^{\prime},s^{\prime})$, then
$r=s$ if and only if $r^{\prime}=s^{\prime}$.

######  Corollary 4.5.

Let $\Gamma={\rm SC}(G,R,L,S)$ be a semi-Cayley graph over an abelian group
$G$ and $\Gamma$ has a PST between two vertices $(g,r)$ and $(h,s)$, with
$r\neq s$. Then $R=L$ and $\Gamma$ is a Cayley graph over a group isomorphic
to $G\rtimes\mathbb{Z}_{2}$.

Proof. By Lemma 4.4, we have $R=L$. Since $G$ is abelian, the map
$\tau:G\rightarrow G$, by the rule $\tau(g)=g^{-1}$ is an automorphism of $G$.
Then [20, Lemma 3.2] implies that $\Gamma$ is a Cayley graph over a group
isomorphic to $G\rtimes\mathbb{Z}_{2}$. $\hfill\blacksquare$

The following result, characterizes Cayley graphs over finite groups with an
abelian groups of index $2$ having PST.

######  Corollary 4.6.

Let $\Gamma={\rm Cay}(G,T)$ be an undirected Cayley graph, where $G$ has an
abelian subgroup $H$ of index $2$, $G=H\cup xH$, $T=T_{1}\cup xT_{2}$, where
$T_{1},T_{2}\subset H$ (if $T_{2}=\emptyset$ then we put $xT_{2}=\emptyset$),
${\rm Irr}(H)=\\{\chi_{1},\ldots,\chi_{n}\\}$ and
$X=\\{i\mid\chi_{i}(T_{2})=0\\}$. Then eigenvalues of $\Gamma$ are

$\lambda_{i}^{+}=\frac{\chi_{i}(T_{1})+\chi_{i}(xT_{1}x^{-1})+\sqrt{(\chi_{i}(T_{1})-\chi_{i}(xT_{1}x^{-1}))^{2}+4|\chi_{i}(x^{2}T_{2})|}}{2},~{}~{}i=1,\ldots,n$

and

$\lambda_{i}^{-}=\frac{\chi_{i}(T_{1})+\chi_{i}(xT_{1}x^{-1})-\sqrt{(\chi_{i}(T_{1})-\chi_{i}(xT_{1}x^{-1}))^{2}+4|\chi_{i}(x^{2}T_{2})|}}{2},~{}~{}i=1,\ldots,n.$

Furthermore, $\Gamma$ has a PST between two vertices $g_{1}$ and $g_{2}$ at
time $t$ if and only if one of the following holds

  * (1)

$g_{1},g_{2}\in H$, and

$\displaystyle\chi_{i}(a)$ $\displaystyle=$ $\displaystyle\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{i}^{+})t)~{}~{}~{}\forall i=1,\ldots,n,$
$\displaystyle\chi_{j}(a)$ $\displaystyle=$ $\displaystyle\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{-})t)~{}~{}~{}\forall j\notin X,$

where $a=g_{1}^{-1}g_{2}$.

  * (2)

$x^{-1}g_{1},x^{-1}g_{2}\in H$, and

$\displaystyle\chi_{i}(a)$ $\displaystyle=$ $\displaystyle\exp(-{\bf
i}(\lambda_{1}^{-}-\lambda_{i}^{-})t)~{}~{}~{}\forall i=1,\ldots,n,$
$\displaystyle\chi_{j}(a)$ $\displaystyle=$ $\displaystyle\exp(-{\bf
i}(\lambda_{1}^{-}-\lambda_{j}^{+})t)~{}~{}~{}\forall j\notin X,$

where $a=g_{1}^{-1}g_{2}$.

  * (3)

$g_{1}\in H$, $x^{-1}g_{2}\in H$, and for all $j=1,\ldots,n$,
$\chi_{j}(x^{2}T_{2})\neq 0$ and

$\displaystyle\chi_{j}(a)$ $\displaystyle=$
$\displaystyle\frac{|\chi_{j}(x^{2}T_{2})|}{\chi_{j}(x^{2}T_{2})}\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t),$ $\displaystyle\exp(-{\bf
i}(\lambda_{j}^{+})t)$ $\displaystyle=$ $\displaystyle-\exp(-{\bf
i}\lambda_{j}^{-}t),$

and $T_{1}x=xT_{1}$, where $a=(xg_{1})^{-1}g_{2}$.

  * (4)

$x^{-1}g_{1}\in H$, $g_{2}\in H$ and for all $j=1,\ldots,n$,
$\chi_{j}(x^{2}T_{2})\neq 0$ and

$\displaystyle\chi_{j}(a)$ $\displaystyle=$
$\displaystyle\frac{|\chi_{j}(x^{2}T_{2})|}{\overline{\chi_{j}(x^{2}T_{2})}}\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t),$ $\displaystyle\exp(-{\bf
i}(\lambda_{j}^{+})t)$ $\displaystyle=$ $\displaystyle-\exp(-{\bf
i}\lambda_{j}^{-}t),$

and $T_{1}x=xT_{1}$, where $a=(x^{-1}g_{1})^{-1}g_{2}$.

Proof. By [1, Lemma 8], we may assume that $G=H\cup xH$, $\Gamma={\rm
SC}(H,R,L,S)$ and we can identify $(h,0)$ and $(h,1)$ with $h$ and $xh$,
respectively, where $R=H\cap T=T_{1}$, $L=H\cap xTx^{-1}=xT_{1}x^{-1}$ and
$S=H\cap xT=x^{2}T_{2}$. Since $T=T^{-1}$ and $T_{1}\cap xT_{2}=\emptyset$, we
see that $T_{1}^{-1}=T_{1}$ and $T_{2}^{-1}=T_{2}$. Now the result is a direct
consequence of Lemma 4.4. $\hfill\blacksquare$

As the following result shows, if a semi-Cayley graph ${\rm SC}(G,R,L,S)$,
with $S=S^{-1}$, over an abelian group $G$ of order $n$ has a PST between
distinct vertices then $n$ is even. In particular, if a Cayley graph over an
abelian group of order $2n$ , or over the dihedral group of order $2n$ has a
PST then $n$ is even. This proves [18, Theorem 3.5] and also [5, Theorem 8]
follows from this and the last part of Theorem 1.

######  Corollary 4.7.

Let $\Gamma={\rm SC}(G,R,L,S)$, $\Gamma$ has a PST between two distinct
vertices $(g,r)$ and $(h,s)$ and put $a=g^{-1}h$. If $r=s$ then $a$ has order
$2$, and if $r\neq s$ then $a$ has order $2$ if and only if $S=S^{-1}$. In
particular, if $G$ has odd order then $\Gamma$ has no PST between two distinct
vertices $(g,r)$ and $(h,r)$, and moreover if $S=S^{-1}$ then $G$ has no PST
between any two distinct vertices.

Proof. Let $a=g^{-1}h$ has order $m$. Then $m\neq 1$, since $a\neq 1$. Then
for each $i$, $\chi_{i}(a)$ is an $m$-th root of unity, since $G$ is abelian.
Thus we may assume that for each $i$, $\chi_{i}(a)=\exp(-{\bf
i}\frac{2\pi}{m}k_{a,i})$, where $k_{a,i}\in\mathbb{Z}$. Moreover, we may
assume that $(m,k_{a,i})=1$. Let $\chi$ be the complex conjugate of
$\chi_{i}$. Then $\chi=\chi_{j}$ for some $j$. Then
$\lambda_{j}^{+}=\lambda_{i}^{+}$ since $R$ and $L$ are inverse-closed.
Furthermore, $k_{a,j}=-k_{a,i}$. Then, Lemma 4.4 implies that if $r=s=0$ then
$\frac{k_{a,i}}{m}-(\lambda_{1}^{+}-\lambda_{i}^{+})T\in\mathbb{Z}$ and
$-\frac{k_{a,i}}{m}-(\lambda_{1}^{+}-\lambda_{i}^{+})T\in\mathbb{Z}$ for all
$i=1,\ldots,n$, where $T=\frac{t}{2\pi}$. So for each $i$, we have
$2\frac{k_{a,i}}{m}\in\mathbb{Z}$. Therefore $m=2$ since $(k_{a,i},m)=1$.
Similarly, one can prove the result for the case $r=s=1$.

Now suppose that $r\neq s$. If $S=S^{-1}$ then $\overline{\chi(S)}=\chi(S)$
for all $\chi\in{\rm Irr}(G)$, which means that $\chi(S)$ is a real number for
all $\chi\in{\rm Irr}(G)$. Now, by the same notations and applying the same
proof of the first part, Lemma 4.4 implies that for each $j=1,\ldots,n$, we
have $2\frac{k_{a,j}}{m}\in\mathbb{Z}$, where $(k_{a,j},m)=1$. This means that
$m=2$. Conversely, suppose that $m=2$. Then for all $j$, $\chi_{j}(a)=1$ or
$-1$. If $r=0$ and $s=1$ then Lemma 4.4,
$\frac{\chi_{j}(S)}{|\chi_{j}(S)|}=\pm\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t)$ and also by considering the conjugate
of $\chi_{j}$, we have
$\frac{\overline{\chi_{j}(S)}}{|\chi_{j}(S)|}=\pm\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t)$, which implies that
$\chi_{j}(S)=\overline{\chi_{j}(S)}=\chi_{j}(S^{-1})$ for all $j=1,\ldots,n$.
Again, by the same argument using the column orthogonality relations given in
the proof of Lemma 4.4, $S=S^{-1}$. This completes the proof.
$\hfill\blacksquare$

Now we are ready to give a characterization of ${\rm SC}(G,R,L,S)$ having PST,
where $G$ is abelian and $R=L$. For this purpose, we need notation of the
$2$-adic exponential valuation of rational numbers which is a mapping defined
by

$\displaystyle\begin{split}&\psi_{2}:\mathbb{Q}\rightarrow\mathbb{Z}\cup\\{\infty\\},\\\
&\psi_{2}(0)=\infty,\\\
&\psi_{2}(2^{l}\frac{a}{b})=l,~{}~{}~{}~{}where~{}a,b,l\in\mathbb{Z}~{}and~{}2\not|ab.\\\
\end{split}$

We assume that $\infty+\infty=\infty+l=\infty$ and $\infty>l$ for any
$l\in\mathbb{Z}$. Then $\psi_{2}$ has the following properties. For
$\beta,\beta^{\prime}\in\mathbb{Q}$,

  * (1)

$\psi_{2}(\beta\beta^{\prime})=\psi_{2}(\beta)+\psi_{2}(\beta^{\prime}),$

  * (2)

$\psi_{2}(\beta+\beta^{\prime})\geq{\rm
min}(\psi_{2}(\beta),\psi_{2}(\beta^{\prime}))$ and the equality holds if
$\psi_{2}(\beta)\neq\psi_{2}(\beta^{\prime}).$

######  Theorem 1.

Let $G$ be a finite abelian group of order $n$, ${\rm
Irr}(G)=\\{\chi_{1},\ldots,\chi_{n}\\}$, where $\chi_{1}$ is the trivial
character of $G$, and $\Gamma={\rm SC}(G,R,R,S)$. Let $u=(g,r)$ and $v=(g,r)$
are vertices of $\Gamma$ and $a=g^{-1}h$. If $r=s$ then $\Gamma$ has a PST
between two distinct vertices $u$ and $v$ if and only if the following
conditions hold

  * (i)

$a$ has order $2$,

  * (ii)

$\Gamma$ is integral, and for each $i$, $\chi_{i}(R)$ and $|\chi_{i}(S)|$ are
integers.

  * (iii)

$\nu_{2}(|R|+|S|-\lambda_{i}^{+})=\nu_{2}(|R|+|S|-\lambda_{i}^{-})$ is the
same integer, say $k$, for all $i$ that $\chi_{i}(g_{x}^{-1}g_{y})=-1$ and for
all $i$ with $\chi_{i}(g_{x}^{-1}g_{y})=1$,
$\nu_{2}(|R|+|S|-\lambda_{i}^{+})>k$ and $\nu_{2}(|R|+|S|-\lambda_{i}^{-})>k$.

Also $\Gamma$ is periodic if and only if $\Gamma$ is integral. Furthermore,
the minimum period of the vertices is $\frac{2\pi}{M}$, where
$M=\gcd\\{\lambda-\lambda_{1}^{+}\mid\lambda\in{\rm
Spec}(\Gamma)\setminus\\{\lambda_{1}^{+}\\}\\}$.

Proof. Let $r=s$. Since $R=L$, we have
$\lambda_{i}^{+}=\chi_{i}(R)+|\chi_{i}(S)|$ and
$\lambda_{i}^{-}=\chi_{i}(R)-|\chi_{i}(S)|$. Let $X=\\{i\mid\chi_{i}(S)=0\\}$.
If $j\in X$ then $\lambda_{j}^{+}=\lambda_{j}^{-}$. Then by Lemma 4.4,
$\Gamma$ has a PST between vertices $u$ and $v$ if and only if for all $i$ we
have $\exp(-{\bf i}\lambda_{i}^{+}t)\chi_{i}(a)=\exp(-{\bf
i}\lambda_{i}^{-}t)\chi_{i}(a)$. Let $T=\frac{t}{2\pi}$. Then we have
$(\lambda_{i}^{+}-\lambda_{i}^{-})T=2|\chi_{i}(S)|T\in\mathbb{Z}$ for all $i$.
If we put $i=1$ in the above relation, then $2|S|T\in\mathbb{Z}$ which means
that $T\in\mathbb{Q}$. Thus $|\chi_{i}(S)|\in\mathbb{Q}$ for all $i$.
Therefore $|\chi_{i}(S)|\in\mathbb{Z}$ for all $i$, since they are eigenvalues
of ${\rm SC}(G,\emptyset,\emptyset,S)$.

By the same argument of the proof of Corollary 4.7, for all $i$ we have

$\frac{k_{a,i}}{m}-(\lambda_{1}^{+}-\lambda_{i}^{+})T,\frac{k_{a,i}}{m}-(\lambda_{1}^{+}-\lambda_{i}^{-})T\in\mathbb{Z},$

where $a$ has order $m$ and $k_{a,i}$ is an integer. Since
$T,\frac{k_{a,i}}{m}\in\mathbb{Q}$, we have
$\lambda_{1}^{+}-\lambda_{i}^{+}\in\mathbb{Q}$ and
$\lambda_{1}^{+}-\lambda_{i}^{-}\in\mathbb{Q}$. So
$\lambda_{i}^{+},\lambda_{i}^{-}\in\mathbb{Q}$. Therefore $\Gamma$ is an
integral graph, since $\lambda_{i}^{+}$ and $\lambda_{i}^{-}$ are algebraic
integers. Hence for each $i$, $\chi_{i}(R)\in\mathbb{Q}$. Thus
$\chi_{i}(R)\in\mathbb{Z}$ for all $i$, since $\chi_{i}(R)$, $i=1,\ldots,n$
are the eigenvalues of Cayley graph ${\rm Cay}(G,R)$.

Again by the proof of Corollary 4.7, if $u$ and $v$ are distinct then $m=2$
and so $\chi_{i}(a)=1$ or $-1$ for all $i$. First assume that
$\chi_{i}(a)=-1$. Then
$(\lambda_{1}^{+}-\lambda_{i}^{+})T,(\lambda_{1}^{+}-\lambda_{i}^{-})T\in\mathbb{Z}+\frac{1}{2}$.
So
$\nu_{2}(\lambda_{1}^{+}-\lambda_{i}^{+})+\nu_{2}(T)=\nu_{2}((\lambda_{1}^{+}-\lambda_{i}^{+})T)=-1$
and
$\nu_{2}(\lambda_{1}^{+}-\lambda_{i}^{-})+\nu_{2}(T)=\nu_{2}((\lambda_{1}^{+}-\lambda_{i}^{-})T)=-1$.
Thus
$\nu_{2}(\lambda_{1}^{+}-\lambda_{i}^{+})=\nu_{2}(\lambda_{1}^{+}-\lambda_{i}^{-})=-1-\nu_{2}(T)=k$.
Now assume that $\chi_{i}(a)=1$. Then
$(\lambda_{1}^{+}-\lambda_{i}^{+})T,(\lambda_{1}^{+}-\lambda_{i}^{-})T\in\mathbb{Z}$
and by similar argument $\nu(|R|+|S|-\lambda_{i}^{+})=k+l_{1}$ and
$\nu(|R|+|S|-\lambda_{i}^{-})=k+l_{2}$ for some $l_{1},l_{2}\geq 1$. This
proves the first part. The second part is a direct consequence of the proof of
the first part. $\hfill\blacksquare$

######  Theorem 2.

Let $\Gamma={\rm SC}(G,R,L,S)$, and $u=(g,r),v=(h,s)$, where $r\neq s$ be two
distinct vertices of $\Gamma$. Then $\Gamma$ has a PST between $u$ and $v$ at
time $t$ if and only if the following conditions hold

  * (i)

$R=L$,

  * (ii)

$\chi_{j}(S)\neq 0$ for each $j$,

  * (iii)

if $r=0,s=1$ then
$\chi_{j}(g^{-1}h)=\frac{|\chi_{j}(S)|}{\chi_{j}(S)}\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t)$, and if $r=1,s=0$ then
$\chi_{j}(g^{-1}h)=\frac{|\chi_{j}(S)|}{\overline{\chi_{j}(S)}}\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t)$, where in both cases $\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t)=\pm 1$.

  * (iv)

$\chi_{j}(R),|\chi_{j}(S)|\in\mathbb{Z}$ for each $j$, in particular $\Gamma$
is integral,

  * (v)

$v_{2}(|S|)=v_{2}(|\chi_{j}(S)|)$ for all $j$.

Proof. Suppose that $\Gamma$ has a PST between $u$ and $v$ at time $t$ and
$T=\frac{t}{2\pi}$. Then $R=L$, for each $j$ we have $\chi_{j}(S)\neq 0$ and
$\exp(-{\bf i}\lambda_{j}^{+}t)=-\exp(-{\bf i}\lambda_{j}^{-}t)$ by Lemma 4.4.
The last equality implies that
$(\lambda_{j}^{+}-\lambda_{j}^{-})T-\frac{1}{2}\in\mathbb{Z}$. Hence
$2|\chi_{j}(S)|T=(\lambda_{j}^{+}-\lambda_{j}^{-})T\in\mathbb{Q}$, for all
$j$. Putting $j=1$, we get $T\in\mathbb{Q}$ and so
$\lambda_{j}^{+}-\lambda_{j}^{-}\in\mathbb{Q}$ for all $j$. Hence
$|\chi_{j}(S)|\in\mathbb{Q}$ for all $j$. Since the eigenvalues of ${\rm
SC}(G,\emptyset,\emptyset,S)$ are $\pm|\chi_{j}(S)|$, we conclude that
$|\chi_{j}(S)|\in\mathbb{Z}$ for all $j$. Furthermore,
$2|\chi_{j}(S)|T-\frac{1}{2}\in\mathbb{Z}$ imples that $4|\chi_{j}(S)|T$ is an
odd number and so $0=v_{2}(4|\chi_{j}(S)|T)=2+v_{2}(|\chi_{j}(S)|)+v_{2}(T)$
for all $j$. Therefore $v_{2}(|S|)=v_{2}(|\chi_{j}(S)|)=-2-v_{2}(T)$ for all
$j$.

On the other hand, again by Lemma 4.4, if $r=0,s=1$ or $r=1,s=0$ then for each
$j$ we have $\chi_{j}(a)=\frac{|\chi_{j}(S)|}{\chi_{j}(S)}\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t)$ or
$\chi_{j}(a)=\frac{|\chi_{j}(S)|}{\overline{\chi_{j}(S)}}\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t)$, respectively. Since the complex
conjugate of any irreducible character of $G$ is an irreducible character of
$G$ and the corresponding eigenvalues of an irreducible character and its
complex conjugate are the same, since $R$ is inverse-closed, we conclude that
in both cases $\exp(-{\bf i}(\lambda_{1}^{+}-\lambda_{j}^{+})t)$ is a real
number, which means that it is $1$ or $-1$. Hence
$(\lambda_{1}^{+}-\lambda_{j}^{+})T\in\frac{1}{2}\mathbb{Z}\subset\mathbb{Q}$.
Since $T\in\mathbb{Q}$ and $\lambda_{1}^{+}=|R|+|S|\in\mathbb{Z}$, we have
$\lambda_{j}^{+}\in Q$. This means that $\Gamma$ is integral and
$\chi_{j}(R)\in\mathbb{Z}$ for all $j$. The converse direction is clear by
Lemma 4.4. $\hfill\blacksquare$

######  Remark 2.

By Theorem 1 and Corollary 4.7, one can exactly determine the existence of a
PST between vertices of an undirected Cayley graph ${\rm Cay}(G,T)$, whenever
$G$ has an abelian sugroup of index $2$ and $H\cap T=H\cap xTx^{-1}$, where
$\\{1,x\\}$ is a left transversal to $H$ in $G$. In particular, since if $G$
is an abelian group of even order, a dihedral group, a dicyclic group or a
semidihedral group, then it satisfies the above conditions, one can reprove
the main results of [3], [5], [6], and [18]. For example, let $\Gamma={\rm
Cay}(G,T)$, where $G$ is an abelian group of order $2n$. Then there exists a
subgroup $H\leq G$, which is abelian and of index $2$. Let $G=H\cup xH$ and
$T=T_{1}\cup xT_{2}$, where $T_{1},T_{2}\subseteq H$. Then
$xT_{1}x^{-1}=T_{1}$ and so $\Gamma={\rm SC}(H,T_{1},T_{1},x^{2}T_{2})$. Let
${\rm Irr}(H)=\\{\chi_{1}=1,\ldots,\chi_{n}\\}$. Then by Theorem 1, if $1\neq
g_{1}^{-1}g_{2}\in H$ then $\Gamma$ has a PST between $g_{1}$ and $g_{2}$ if
and only if the following conditions hold

  * (i)

the order of $g_{1}^{-1}g_{2}$ is two,

  * (ii)

$\Gamma$ is integral, and for each $i$, $\chi_{i}(T_{1})$ and
$|\chi_{i}(T_{2})|$ are integers,

  * (iii)

$\nu_{2}(|T|-\lambda_{i}^{+})=\nu_{2}(|T|-\lambda_{i}^{-})$ is the same
integer, say $k$, for all $i$ that $\chi_{i}(g_{1}^{-1}g_{2})=-1$ and for all
$i$ with $\chi_{i}(g_{1}^{-1}g_{2})=1$, $\nu_{2}(|T|-\lambda_{i}^{+})>k$ and
$\nu_{2}(|R|+|S|-\lambda_{i}^{-})>k$,

where $\lambda_{i}^{+}=\chi_{i}(T_{1})+|\chi_{i}(T_{2})|$ and
$\lambda_{i}^{-}=\chi_{i}(T_{1})-|\chi_{i}(T_{2})|$, $i=1,\ldots,n$.

Also, if $g_{1}^{-1}g_{2}\notin H$, then $\Gamma$ has a PST between $g_{1}$
and $g_{2}$ at time $t$ if and only if the following conditions hold

  * (i)

$\chi_{j}(T_{2})\neq 0$ for each $j$,

  * (ii)

if $g_{1}\in H$ and $g_{2}\notin H$ then
$\chi_{j}(g_{1}^{-1}g_{2})=\frac{|\chi_{j}(T_{2})|}{\chi_{j}(x^{2}T_{2})}\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t)$, and if $g_{1}\notin H$ and $g_{2}\in
H$ then
$\chi_{j}(g_{1}^{-1}g_{2})=\frac{|\chi_{j}(T_{2})|}{\overline{\chi_{j}(x^{2}T_{2})}}\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t)$, where in the both cases $\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t)=\pm 1$.

  * (ii)

$\chi_{j}(T_{1}),|\chi_{j}(T_{2})|\in\mathbb{Z}$ for each $j$, in particular
$\Gamma$ is integral,

  * (vi)

$v_{2}(|T_{2}|)=v_{2}(|\chi_{j}(T)|)$ for all $j$.

Also $\Gamma$ is periodic if and only if $\Gamma$ is integral. Furthermore,
the minimum period of the vertices is $\frac{2\pi}{M}$, where
$M=\gcd\\{\lambda-\lambda_{1}^{+}\mid\lambda\in{\rm
Spec}(\Gamma)\setminus\\{\lambda_{1}^{+}\\}\\}$. This proves that [18, Theorem
2.4], the main theorem of [18], is a direct consequence of Theorems 1 and 2.

Let us recall generalized dihedral and generalized dicyclic groups as follows:
Given an abelian group $A$, the generalized dihedral group $Dih(A,x)=\langle
A,x\rangle$ is a group generated by $A$ and an element $x$ such that $x\notin
A$, $x^{2}=1$ and $xax=a^{-1}$ for all $a\in A$. It is easy to see that $A$ is
a normal subgroup of $Dih(A)$ of index $2$. Clearly the dihedral group
$D_{2n}=\langle a,b\rangle\mid a^{n}=b^{2}=(ab)^{2}=1\rangle$ of order $2n$,
is $Dih(\langle a\rangle,b)$. Now let $A$ be an abelian group of even order
and of exponent greater than $2$, and let $y$ be an involution of $A$. The
generalized dicyclic group $Dic(A,y,x)$ is the group $\langle A,x\mid
x^{2}=y,x^{-1}ax=a^{-1},~{}\forall a\in A\rangle$. When $A$ is cyclic,
$Dic(A,y,x)$ is called a dicyclic (or generalized quaternion) group.

The following result improves [5, Theorem 8 and Theorem 11] and [3, Theorem
4.2].

######  Corollary 4.8.

Let $A$ be an abelian group, ${\rm Irr}(A)=\\{1=\chi_{1},\ldots,\chi_{n}\\}$,
$G=Dih(A,x)$ or $G=Dic(A,y,x)$, and $\Gamma={\rm Cay}(G,T)$, where
$T=T_{1}\cup xT_{2}$ for some $T_{1},T_{2}\subseteq A$. if $1\neq
g_{1}^{-1}g_{2}\in A$ then $\Gamma$ has a PST between $g_{1}$ and $g_{2}$ if
and only if the following conditions hold

  * (i)

the order of $g_{1}^{-1}g_{2}$ is two,

  * (ii)

$\Gamma$ is integral, and for each $i$, $\chi_{i}(T_{1})$ and
$|\chi_{i}(T_{2})|$ are integers,

  * (iii)

$\nu_{2}(|T|-\lambda_{i}^{+})=\nu_{2}(|T|-\lambda_{i}^{-})$ is the same
integer, say $k$, for all $i$ that $\chi_{i}(g_{1}^{-1}g_{2})=-1$ and for all
$i$ with $\chi_{i}(g_{1}^{-1}g_{2})=1$, $\nu_{2}(|T|-\lambda_{i}^{+})>k$ and
$\nu_{2}(|R|+|S|-\lambda_{i}^{-})>k$,

where $\lambda_{i}^{+}=\chi_{i}(T_{1})+|\chi_{i}(T_{2})|$ and
$\lambda_{i}^{-}=\chi_{i}(T_{1})-|\chi_{i}(T_{2})|$, $i=1,\ldots,n$.

Also, if $g_{1}^{-1}g_{2}\notin A$, then $\Gamma$ has a PST between $g_{1}$
and $g_{2}$ at time $t$ if and only if the following conditions hold

  * (i)

$\chi_{j}(T_{2})\neq 0$ for each $j$,

  * (ii)

if $g_{1}\in A$ and $g_{2}\notin A$ then
$\chi_{j}(g_{1}^{-1}g_{2})=\frac{|\chi_{j}(T_{2})|}{\chi_{j}(T_{2})}\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t)$, and if $g_{1}\notin A$ and $g_{2}\in
A$ then
$\chi_{j}(g_{1}^{-1}g_{2})=\frac{|\chi_{j}(T_{2})|}{\overline{\chi_{j}(T_{2})}}\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t)$, where in the both cases $\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{j}^{+})t)=\pm 1$.

  * (ii)

$\chi_{j}(T_{1}),|\chi_{j}(T_{2})|\in\mathbb{Z}$ for each $j$, in particular
$\Gamma$ is integral,

  * (vi)

$v_{2}(|T_{2}|)=v_{2}(|\chi_{j}(T)|)$ for all $j$.

Also $\Gamma$ is periodic if and only if $\Gamma$ is integral. Furthermore,
the minimum period of the vertices is $\frac{2\pi}{M}$, where
$M=\gcd\\{\lambda-\lambda_{1}^{+}\mid\lambda\in{\rm
Spec}(\Gamma)\setminus\\{\lambda_{1}^{+}\\}\\}$.

Proof. Since $T_{1}=A\cap T=A\cap xTx^{-1}$ and $T_{2}=A\cap xT$, we have
$\Gamma={\rm SC}(A,T_{1},T_{1},T_{2})$. Now the result follows from Theorems 1
and 2 immediately. $\hfill\blacksquare$

Since ${\rm SC}(G,R,L,G)$ is the join graph of ${\rm Cay}(G,R)$ and ${\rm
Cay}(G,L)$, the following result gives a characterization of the join of two
Cayley graphs over the same abelian group.

######  Corollary 4.9.

Let $\Gamma={\rm SC}(G,R,L,G)$, where $G$ is an abelian group of order $n$,
and ${\rm Irr}(G)=\\{\chi_{1},\ldots,\chi_{n}\\}$. Then $\Gamma$ has a PST
between vertices $u=(g,r)$ and $v=(h,s)$ at time $t$ if and only if one of the
following holds:

  * (1)

$g=h,r=s=0$, $(\lambda_{1}^{+}-\chi_{i}(R))t\in 2\pi\mathbb{Z}$ for all $i$
and $t\sqrt{(|R|-|L|)^{2}+4n^{2}}\in\pi\mathbb{Z}$.

  * (2)

$g=h,r=s=1$, $(\lambda_{1}^{-}-\chi_{i}(L))t\in 2\pi\mathbb{Z}$ for all $i$
and $t\sqrt{(|R|-|L|)^{2}+4n^{2}}\in\pi\mathbb{Z}$.

  * (3)

$g\neq h,r=s=0$, $\sum_{i=1}^{n}\exp({\bf i}\lambda_{i}^{+}t)=0$ and
$t\sqrt{(|R|-|L|)^{2}+4n^{2}}\in\pi\mathbb{Z}$.

  * (4)

$g\neq h,r=s=1$, $\sum_{i=1}^{n}\exp({\bf i}\lambda_{i}^{-}t)=0$ and
$t\sqrt{(|R|-|L|)^{2}+4n^{2}}\in\pi\mathbb{Z}$,

where $\lambda_{1}^{+}=\frac{|R|+|L|+|\sqrt{(|R|-|L|)^{2}+4n^{2}}}{2}$,
$\lambda_{1}^{-}=\frac{|R|+|L|-|\sqrt{(|R|-|L|)^{2}+4n^{2}}}{2}$ ,
$\lambda_{i}^{+}=\chi_{i}(R)$ and $\lambda_{i}^{-}=\chi_{i}(L)$,
$i=2,\ldots,n$ are eigenavlues of $\Gamma$.

Proof. We have $X=\\{i\mid\chi_{i}(S)=0\\}=\\{2,\ldots,n\\}$ since $\chi(G)=0$
for all $1\neq\chi\in{\rm Irr}(G)$. This menas that for all $i\neq 1$, we may
assume that $\lambda_{i}^{+}=\chi_{i}(R)$ and $\lambda_{i}^{-}=\chi_{i}(L)$.
Then, by Lemma 4.4 and Theorem 2, $\Gamma$ has a PST from $u=(g,r)$ to
$v=(h,s)$ if and only if $r=s=0$, $\chi_{i}(a)=\exp(-{\bf
i}(\lambda_{1}^{+}-\lambda_{i}^{+})t)$ for all $i$ and
$t\sqrt{(|R|-|L|)^{2}+4n^{2}}\in\pi\mathbb{Z}$ or $r=s=1$,
$\chi_{i}(a)=\exp(-{\bf i}(\lambda_{1}^{-}-\lambda_{i}^{-})t)$ for all $i$ and
$t\sqrt{(|R|-|L|)^{2}+4n^{2}}\in\pi\mathbb{Z}$ where $a=g^{-1}h$. Putting
$a=1$, we get the first and second parts. Now let $a\neq 1$. Then by the
column orthogonality relations [14, Theorem 16.4], we have
$\sum_{i=1}^{n}\chi_{i}(a)=0$, which proves the last two parts.
$\hfill\blacksquare$

Now we give some examples as an application of our results as follows:

######  Example 4.10.

Let $n\geq 3$ and $\Gamma$ be the $n$-sunlet graph, a graph that its vertices
is obtained by attaching $n$ pendant edges to the $n$-cycle. Then $\Gamma={\rm
SC}(G,R,L,S)$, where $G=\langle a\rangle\cong\mathbb{Z}_{n}$,
$R=\\{a,a^{-1}\\}$, $L=\emptyset$ and $S=\\{1\\}$. If $n$ is odd, then
$\Gamma$ has no PST by Corollary 4.7. If $n=2m$ is even, by considering the
character $\chi_{m}:G\rightarrow\mathbb{C}$ by the rule
$\chi_{m}(a^{k})=(-1)^{k}$, Lemma 4.4 implies that $\Gamma$ has no PST and is
not periodic.

######  Example 4.11.

Let $n\geq 3$ and $\Gamma$ be the $n$-gonal $n$-cone, the join of an $n$-cycle
with the empty graph with $n$ vertices. Then $\Gamma={\rm SC}(G,R,L,S)$, where
$G=\langle a\rangle\cong\mathbb{Z}_{n}$, $R=\\{a,a^{-1}\\}$, $L=\emptyset$ and
$S=G$. Then, by Corllary 4.9, $\lambda_{1}^{+}=1+\sqrt{1+n^{2}}$,
$\lambda_{1}^{-}=1-\sqrt{1+n^{2}}$, and for all $i\neq 1$, we have
$\lambda_{i}^{+}=2Re(\chi_{i}(a))=2\cos(\frac{2\pi i}{n})$ and
$\lambda_{i}^{-}=0$. If $n$ is odd, then $\Gamma$ has no PST by Corollary 4.7.
Let $n=2m$. Consider the irreducible character
$\chi_{m}:G\rightarrow\mathbb{C}$ with the rule $\chi_{m}(a^{k})=(-1)^{k}$ and
let $\Gamma$ has a PST from $(g,r)$ to $(h,s)$. Then Corollary 4.9 implies
that $g=h,r=s=0$ or $g=h,r=s=1$ occurs if $\sqrt{1+n^{2}}\in\mathbb{Q}$, which
is impossible. If $g\neq h$ and $r=s=1$ then we must have $\exp({\bf
i}t)=1-n-(-{\bf i})^{k}$ for some integer $k$, which is again impossible.
Also, if $g\neq h$ and $r=s=0$ then we must have $({\bf i})^{k}\exp({\bf
i}t)+\sum_{i=1}^{n-1}\exp(2{\bf i}\cos(\frac{2\pi i}{n}))=0$, for some integer
$k$.

######  Example 4.12.

Let $\Gamma={\rm Cay}(G,T)$, where $G=Dih(A,x)$ or $G=Dic(A,y,x)$ and $T=xA$.
Then, by the notations of Corollary 4.8, we have $T_{1}=\emptyset$, $T_{2}=A$,
$\lambda_{1}^{+}=|A|$, $\lambda_{1}^{-}=-|A|$, and for all $i\neq 1$,
$\lambda_{i}^{+}=\lambda_{i}^{-}=0$. Then $\Gamma$ is periodic with minimum
period $\frac{2\pi}{|A|}$ and has no PST between distinct vertices, by
Corollary 4.8.

######  Example 4.13.

Let $\Gamma={\rm Cay}(G,T)$, where $G=Dih(A,x)$ or $G=Dic(A,y,x)$ and
$T=xA\cup\\{a\in A\mid o(a)=2\\}$. Then, by the notations of Corollary 4.8,
$T_{1}=\\{a\in A\mid o(a)=2\\}$, $T_{2}=A$, $\lambda_{1}^{+}=|T_{1}|+|A|=|T|$,
$\lambda_{1}^{-}=|T_{1}|-|A|$, and for each $i\neq 1$,
$\lambda_{i}^{+}=\lambda_{i}^{-}=\sum_{a\in A,o(a)=2}\chi_{i}(a)$. Again,
$\Gamma$ is integral and so it is periodic with minimum period
$\frac{2\pi}{M}$, where $M=\gcd(|T_{1}|-|A|-|T|,\sum_{a\in
A,o(a)=2}\chi_{2}(a)-|T|,\ldots,\sum_{a\in A,o(a)=2}\chi_{n}(a)-|T|)$, and
$n=|A|$. Also by a tedious computation, we see that $\Gamma$ has no PST.

##  5 Concluding remarks

The perfect state transfer (PST) in quantum walks, where the underlying graphs
are semi-Cayley graphs over abelian groups were studied. We derive the
spectral decomposition of any semi-Cayley graph over an abelian group $G$ in
terms of the irreducible characters of $G$. Since every Cayley graph over a
group $G$ having an abelian subgroup $H$ is a semi-Cayley graph over $H$, our
method for investigating of PST can be applied to any Cayley graph over a
finite group having an abelian subgroup of index $2$. One can apply our method
to the quasi-abelian semi-Cayley graphs.

Acknowledgements The author would like to thank Tao Feng (faculty member of
Department of Mathematics, Beijing Jiaotong University). In fact one day after
sumbitting the first version of my paper to Arxiv.org, Tago Feng informed me
that there is a mistake in my paper and the equality
$|e_{i}^{+}|+|e_{i}^{-}|\leq\frac{1}{2}$ is not correct. This caused me to
revise the article and fix the problem in Theorem 2. Also note that in the
previous version on arXiv.org (2202.03062v2) I forgot to add the
acknowledgement.

## References

  * [1] M. Arezoomand and B. Taeri, On the characteristic polynomial of $n$-Cayley digraphs, Electron. J. Combin., 20(3) (2013), # P57.
  * [2] M. Arezoomand and B. Taeri, A classification of finite groups with integral bi-Cayley graphs, Trans. Combin.,4(4) (2015) 55-61.
  * [3] M. Arezoomand, F. Shafiei and Modjtaba Ghorbani, Perfect state transfer on Cayley graphs over the dicyclic group, Linear Algebra Appl., 639 (2022) 116-134.
  * [4] R.J. Angeles-Canul, R. Norton, M. Opperman, C. Paribello, M. Russell, C. Tamon, Perfect state transfer, integral circulants and join of graphs, Quantum Computation and Information 10 (2010) 325–342. arXiv:0907.2148.
  * [5] X. Cao, B. Chen and S. Ling, Perfect state transfer on Cayley graphs over the dihedral groups: the non-normal case, Electron. J. Combin., 27 (2020) no.2 P2.28.
  * [6] X. Cao, and K. Feng, Perfect state transfer on Cayley graphs over dihedral groups, Linear and Multilinear Algebra, https://doi.org/10.1080/03081087.2019.1599805.
  * [7] G. Coutinho et al., Perfect state transfer on distance-regular graphs and association schemes, Linear Algebra Appl. 478 (2015) 108–130.
  * [8] G. Coutinho, Quantum state transfer in graphs [PhD dissertation]. University of Waterloo, 2014.
  * [9] E. Farhi, S. Gutmann, Quantum computation and decision trees, Phys. Rev. A 58 (3) (1998) 915–928.
  * [10] C. Godsil, Periodic graphs, Electron. J. Combin. 18 (2011) no. 1 Paper 23, 15 pp.
  * [11] C. Godsil, State transfer on graphs, Discrete Math. 312 (2012) no. 1 129–147.
  * [12] C. Godsil, When can perfect state transfer occur?, Electron. J. Linear Algebra 23 (2012) 877–890.
  * [13] J. Huang and S. Li, Integral and distance integral Cayley graphs over generalized dihedral groups, J. Algebraic Combin., https://doi.org/10.1007/s10801-020-00948-1.
  * [14] G. James and M. Liebeck, Representations and characters of groups, Cambridge University Press, Second Edition, 2001.
  * [15] N. Johnston, et al., Perfect quantum state transfer using Hadamard diagonalizable graphs, Linear Algebra Appl. 531 (2017) 375–398.
  * [16] G. Luo, X. Cao, D. Wang and X. Wu, Perfect quantum state transfer on Cayleygraphs over semi-dihedral groups, Linear and Multilinear Algebra, https://doi.org/10.1080/03081087.2021.1954585.
  * [17] M. Štefaňák, S. Skoupý, Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs, Quantum Inf. Process. 16 (2017) no. 3 Paper No. 72, 14 pp.
  * [18] Y.Y. Tan, K. Feng, X. Cao, Perfect state transfer on abelian Cayley graphs, Linear Algebra Appl., (2019), https://doi.org/10.1016/j.laa.2018.11.011
  * [19] F. Zhang, Matrix Theory, Basic Results and Techniques, Second Edition, Springer, 2011.
  * [20] J. X Zhou and Y. Q. Feng, cubic bi-Cayley graphs over abelian groups, European J. Combin. 36 (2014) 679-793.


# A universal right tail upper bound for supercritical Galton-Watson processes
with bounded offspring

John Fernley111Alfréd Rényi Institute of Mathematics, Budapest, Hungary.
email<EMAIL_ADDRESS>Emmanuel Jacob222École Normale Supérieure de Lyon,
France. email<EMAIL_ADDRESS>
###### Abstract

We consider a supercritical Galton-Watson process $Z_{n}$ whose offspring
distribution has mean $m>1$ and is bounded by some $d\in\\{2,3,\ldots\\}$. As
well-known, the associated martingale $W_{n}=Z_{n}/m^{n}$ converges a.s. to
some nonnegative random variable $W_{\infty}$. We provide a universal upper
bound for the right tail of $W_{\infty}$ and $W_{n}$, which is uniform in $n$
and in all offspring distributions with given $m$ and $d$, namely:

$\operatorname{\mathbb{P}}(W_{n}\geq x)\leq
c_{1}\exp\left\\{-c_{2}\frac{m-1}{m}\frac{x}{d}\right\\},\quad\forall
n\in\mathbb{N}\cup\\{+\infty\\},\forall x\geq 0,$

for some explicit constants $c_{1},c_{2}>0$. For a given offspring
distribution, our upper bound decays exponentially as $x\to\infty$, which is
actually suboptimal, but our bound is _universal_ : it provides a single
_effective_ expression, which is _nonasymptotic_ – it does not require $x$
large – and valid simultaneously for all supercritical bounded offspring
distributions.

##  1 Introduction

Consider a Galton-Watson process $(Z_{n})_{n\geq 0}$ with $Z_{0}=1$ where the
offspring distribution has expectation $m=\operatorname{\mathbb{E}}[Z_{1}]>1$
and $d=\sup\\{k\in\mathbb{N},\operatorname{\mathbb{P}}(Z_{1}=k)>0\\}<+\infty$.
In other words, the GW process is supercritical with bounded offspring
distribution. By definition,

$Z_{n+1}=\sum_{k=1}^{Z_{n}}\xi_{n,i},$

where $(\xi_{n,i})$ is a collection of independent identically distributed
random variables with the same distribution as $Z_{1}$. The martingale
$W_{n}=Z_{n}/m^{n}$ converges almost surely and in $L^{2}$ to some random
variable $W_{\infty}\geq 0$, see for example [AN72]. The seminal work of
Harris [Har48] shows that $W_{\infty}$ has finite exponential moments and
provides the following estimates for the generating function:

$\varphi(x):=\log\operatorname{\mathbb{E}}e^{xW_{\infty}}=x^{\gamma}C(x)+O(1)\quad\text{
as }x\to\infty,$

where $C$ is a positive multiplicatively periodic function (in particular it
is bounded above and below in $(0,+\infty)$), $\gamma$ is defined by
$m^{\gamma}=d$ or $\gamma=\ln d/\ln m$, and $O(1)$ is the standard Landau
notation. Harris’ work is based on the Poincaré functional equation satisfied
by $\varphi$, namely $\varphi(mx)=f(\varphi(x))$ where $f$ is the generating
function of $Z_{1}$. Biggins and Bingham [BB93] could use this result to
provide asymptotic estimates for the tail of $W_{n}$ for both cases
$n<+\infty$ or $n=+\infty$. This was later refined by Fleischmann and Wachtel
in [FW09], who were mainly studying the left tail of $W_{\infty}$, but also
expressed for the right tail the following asymptotics (see Remark 3 in their
paper):

$\operatorname{\mathbb{P}}(W_{\infty}>x)=(1+o(1))x^{\frac{-\gamma}{2(\gamma-1)}}C_{1}(x)e^{-C_{2}(x)x^{\frac{\gamma}{\gamma-1}}},$
(1)

where $C_{1}$ and $C_{2}$ are again positive multiplicatively periodic
functions. In 2013, Denisov, Korshunov, and Wachtel [WDK13] provide similar
results when the offspring distribution is no more bounded but on the contrary
heavy tailed, relying on probabilistic techniques for sums of i.i.d. random
variables rather than on the Poincaré functional equation. Their article is
also a good reference for an overview on the topic.

In this note, we seek for a more effective upper bound for the tail of
$W_{n}$. We seek for a bound that would be _nonasymptotic_ , available for
both $n$ finite or infinite, and above all _uniform_ over the possible choices
of the offspring distribution, or at least only depending on $m$ and $d$. To
motivate this, observe that the optimal strategy leading to large values of
$W_{\infty}$ often stems in just asking the first generations to have maximal
degree (see [FW09]). For example, if you assume
$\eta=\operatorname{\mathbb{P}}(Z_{1}=d)>0$, you have $W_{k}=x=d^{k}/m^{k}$
with probability

$\eta^{1+d+\ldots+d^{k-1}}=\eta^{\Theta(d^{k-1})}=\eta^{\Theta\left({x^{\gamma/(\gamma-1)}}d^{-1}\right)},$

which already somehow resembles the asymptotics given in (1). The maximal
value of $\eta$ being of course $m/d$, we obtain a uniform upper bound for the
event that $W_{k}$ equals its maximal possible value $d^{k}/m^{k}$. It is
natural to ask whether we can obtain a similar uniform upper bound for the
event $\\{W_{\infty}>x\\}$, possibly an upper bound that would feature the
term $\exp(-cx^{\gamma/(\gamma-1)}d^{-1})$, or be as close as possible to (1).

We didn’t find any such result in the literature. In this note, we thus
provide, up to our knowledge, a first result in that direction.

######  Theorem 1.1.

There are universal constants $c_{1},c_{2}>0$ such that for any $m>1$, any
$d\in\\{2,3,\ldots\\}$ and any offspring distibution on $\\{0,\ldots,d\\}$
with mean $m$, for all $n\in\mathbb{N}\cup\\{+\infty\\}$ and $x\geq 0$, we
have

$\operatorname{\mathbb{P}}(W_{n}\geq x)\leq
c_{1}\exp\left\\{-c_{2}\frac{m-1}{m}\frac{x}{d}\right\\}.$ (2)

######  Remark 1.2.

Our original motivation for proving Theorem 1.1 lies in the study of the
contact process on power-law trees in [FJ23]. In that work the other existing
upper bounds were not really useful, and it required a more effective upper
bound like (2).

######  Remark 1.3.

We didn’t seek for optimal constants, but in our proof we can take
$c_{2}=(\log 3-1)/40$. Less importantly, we can take $c_{1}=2$, or $c_{1}=1$
if we discard small values of $x$.

##  2 Proof of Theorem 1.1

Heuristically, we obtain the upper bound by arguing that in order to have
$\\{W_{n}>xd\\}$, we need to have simultaneous occurrence of $\Theta(x)$
unlikely events. The first such event we consider is that the martingale
$W_{n}$ hits $[ad,+\infty)$, with $a\geq 1$ to be fixed later. If this
happens, reveal the offspring of the individuals in breadth-first order, until
the first time when you can witness that the martingale will reach a value
greater than $ad$. At this time, you just explored the offspring, bounded by
$d$, of some individual of generation $n\geq 0$, and you must have revealed
inbetween $adm^{n+1}$ and $adm^{n+1}+d$ individuals at generation $n+1$. There
are also some individuals of generation $n$ with still unrevealed offspring
(and in particular, once we reveal them, $Z_{n+1}$ might end up being larger
than $adm^{n+1}+d$), but there are at most $adm^{n}$ of them, as $W_{n}$ was
bounded by $ad$.

Call all these “still-to-explore” individuals the children of the root, in a
new multitype branching tree $T$, where the types of the vertices are just the
generation in the original branching process. At this stage, $T$ contains only
the root, of type 0, and its children of type $n$ or $n+1$. Repeat now the
procedure from each child as follows: for a child of type $n$ ask whether,
counting only its descendants, you can observe at some time $k\geq n$ more
than $adm^{k}$ individuals, and if this happens associate as before the at
most $adm^{k}+d$ children of type $k$ and the at most $adm^{k-1}$ children of
type $k-1$.

Suppose this procedure constructed a finite tree $T$ with $|i_{T}|$ internal
nodes and a set of leaves $\ell_{T}$. Conditionally on this tree $T$, we then
have

$Z_{n}\leq|i_{T}|adm^{n}+\sum_{j\in\ell_{T},k_{j}\leq
n}\tilde{Z}_{n}^{(j,k_{j})},$ (3)

where $\tilde{Z}^{(j,k_{j})}$ is the offspring of the vertex $j$ of type
$k_{j}$ at time $n\geq k_{j}$. For given $j$ with type $k_{j}\leq n$, the
process $\big{(}\tilde{Z}_{l}^{(j,k_{j})}\big{)}_{l\geq k_{j}}$ is of course
the branching process, initiated at time $l=k_{j}$ with
$\tilde{Z}_{k_{j}}^{(j,k_{j})}=1$, and conditioned on $\Big{\\{}\forall l\geq
k_{j},\tilde{Z}_{l}^{(j,k_{j})}\leq adm^{l}\Big{\\}}$. Its value at time $n$
is stochastically dominated by $Z_{n-k_{j}}\wedge adm^{n}$, and of course the
offsprings of the different leaves $j\in\ell_{T}$ are independent.

The next two lemmas allow to bound the size of $T$, and then the size of
$Z_{n}$.

######  Lemma 2.1.

Set $a=\frac{8m}{m-1}$. Then, for any positive integer $r$, the probability
that $T$ contains at least $r$ internal nodes is at most $e^{-(\log 3-1)r}$.

######  Lemma 2.2.

With $a=\frac{8m}{m-1}$, if you condition on $T$ containing less than $r$
internal nodes, then the probability of $\\{W_{n}>5adr\\}$ is bounded by
$e^{-\frac{2}{3}r}$.

With these two lemmas at hand, we obtain for any positive integer $r$ the
inequality

$\operatorname{\mathbb{P}}(W_{n}>5adr)\leq e^{-(\log
3-1)r}+e^{-\frac{2}{3}r},$

which translates into Theorem 1.1 when taking $x$ nonnegative real number.

###### Proof of Lemma 2.1.

Recall that the martingale $W_{n}=Z_{n}/m^{n}$ converges almost surely and in
$L^{2}$ to $W_{\infty}$ with $\operatorname{\mathbb{E}}[W_{\infty}]=1$ and
$\operatorname{Var}W_{\infty}=\frac{\operatorname{Var}Z_{1}}{m(m-1)}$.
Stopping the submartingale $W_{n}^{2}$ at the first time it hits
$[x,+\infty)$, we then obtain a bound for the tail distribution of
$\sup_{l}W_{l}$ as

$\displaystyle\operatorname{\mathbb{P}}(\sup_{l}W_{l}\geq x)$
$\displaystyle\leq
x^{-2}\operatorname{\mathbb{E}}[W_{\infty}^{2}\mathbbm{1}_{\\{\sup W_{l}\geq
x\\}}]\leq\left(1+\frac{\operatorname{Var}Z_{1}}{m(m-1)}\right)x^{-2}$
$\displaystyle\leq\left(1+\frac{d}{(m-1)}\right)x^{-2},$

where in the last inequality we use
$\operatorname{Var}Z_{1}\leq\operatorname{\mathbb{E}}[Z_{1}]d=md$.

Thus, a vertex of $T$ of type $n$ is an internal node with probability

$p_{n}:=\operatorname{\mathbb{P}}\left(\sup_{l}W_{l}\geq
adm^{n}\right)\leq\frac{1}{a^{2}m^{2n}d^{2n}}+\frac{1}{a^{2}m^{2n}d(m-1)}.$

For any $n$, we have

$adm^{n}p_{n}\leq\frac{1}{a}\left(\frac{1}{d}+\frac{1}{m-1}\right)\leq\frac{m}{a(m-1)}\leq\frac{1}{8},$

as well as $p_{n}\leq p_{0}\leq 1/16$. We now look at the subtree of internal
nodes of $T$. Note that if an internal node has in $T$ (at most) $adm^{n+1}+d$
children of type $n+1$ and $adm^{n}$ of type $n$, amongst these children, the
number of internal nodes is bounded by

$\displaystyle\hskip
14.22636pt\operatorname{Bin}(adm^{n+1}+d,p_{n+1})\oplus\operatorname{Bin}(adm^{n},p_{n})$
$\displaystyle\preceq\
\operatorname{Pois}(2adm^{n+1}\frac{p_{n+1}}{1-p_{n+1}})\oplus\operatorname{Pois}(adm^{n}\frac{p_{n}}{1-p_{n}})$
$\displaystyle\preceq\
\operatorname{Pois}\left(\frac{3}{8}.\frac{16}{15}\right)=\operatorname{Pois}\left(\frac{1}{3}\right),$

where $\operatorname{Bin}(n,p)$ and $\operatorname{Pois}(\lambda)$ stand here
for random variables with binomial (respectively Poisson) distribution,
$\oplus$ means we sum independent random variables, and $\preceq$ stands for
stochastic domination. The probability that the root is an internal node is
also bounded by the probability that a $\operatorname{Pois}(1/3)$ is positive.
Thus in order to have at least $r$ internal nodes, you need to have a
$\operatorname{Pois}(mr)$ larger than $r$ where $m=1/3$, which we bound by the
usual Chernoff bound

$\operatorname{\mathbb{P}}(\operatorname{Pois}(mr)\geq r)\leq
e^{-mr}(em)^{r}\leq(em)^{r}=e^{-(\log 3-1)r}.$

∎

###### Proof of Lemma 2.2.

We work conditionally on $T$ and deduce from (3) the inequality

$W_{n}\leq|i_{T}|ad+\sum_{j\in\ell_{T},k_{j}\leq n}\tilde{W}_{n}^{(j,k_{j})},$
(4)

where $\tilde{W}_{n}^{(j,k_{j})}:=m^{-n}\tilde{Z}_{n}^{(j,k_{j})}$ is
stochastically dominated by $m^{-k_{j}}W_{n-k_{j}}\wedge ad$, and hence

$\displaystyle\operatorname{\mathbb{E}}[\tilde{W}_{n}^{j,k_{j}}]$
$\displaystyle\leq m^{-k_{j}},$
$\displaystyle\operatorname{Var}\tilde{W}_{n}^{j,k_{j}}$ $\displaystyle\leq
m^{-2k_{j}}\operatorname{\mathbb{E}}[W_{\infty}^{2}]\leq
m^{-2k_{j}}\left(1+\frac{d}{m-1}\right)\leq
m^{-k_{j}}\left(1+\frac{d}{m-1}\right).$

Summing over the leaves of $T$, we obtain

$\sum_{j\in\ell_{T}}\operatorname{\mathbb{E}}[\tilde{W}_{n}^{j,k_{j}}]\leq\sum_{j\in\ell_{T}}m^{-k_{j}}\leq
3ad|i_{T}|,$

using that the sum of the $m^{-k_{j}}$ over the leaves which are the children
of a given internal node, is necessarily bounded by $3ad$. Similarly,

$\sum_{j\in\ell_{T}}\operatorname{Var}\tilde{W}_{n}^{j,k_{j}}\leq\left(1+\frac{d}{m-1}\right)3ad|i_{T}|\leq\frac{m}{m-1}3ad^{2}|i_{T}|=\frac{3}{8}a^{2}d^{2}|i_{T}|.$

Now we have $\operatorname{\mathbb{E}}\left[W_{n}\ \big{|}\ T\right]\leq
4ad|i_{T}|$, and Bernstein’s inequality states

$\displaystyle\operatorname{\mathbb{P}}\left(W_{n}\geq 4ad|i_{T}|+adx\
\Big{|}\,T\right)$
$\displaystyle\leq\exp\left(-\frac{\frac{1}{2}\left(adx\right)^{2}}{\sum\operatorname{Var}\tilde{W}_{n}^{j,k_{j}}+\frac{1}{3}(ad)(adx)}\right)$
$\displaystyle\leq\exp\left(-\frac{x}{\frac{3}{4}\frac{|i_{T}|}{x}+\frac{2}{3}}\right),$

and hence

$\operatorname{\mathbb{P}}\left(W_{n}\geq 5adx\ \Big{|}\,|i_{T}|\leq
x\right)\leq e^{-\frac{12}{17}x}\leq e^{-\frac{2}{3}x}.$

∎

## References

  * [AN72] Athreya, K. B. and Ney, P. E.: Branching processes. _Die Grundlehren der mathematischen Wissenschaften, Band 196_. Springer Berlin Heidelberg, 1972.
  * [BB93] Biggins, J.D. and Bingham, N.H.: Large deviations in the supercritical branching process. _Advances in Applied Probability_ , 25(4):757–772, 1993.
  * [FJ23] Fernley, J. and Jacob, E: Targeted immunisation thresholds for the contact process on power-law trees. _To appear on arXiv._
  * [FW09] Fleischmann, K. and Wachtel, V.: On the left tail asymptotics for the limit law of supercritical Galton–Watson processes in the Böttcher case. _Annales de l’Institut Henri Poincaré, Probabilités et Statistiques_ , 45(1):201 – 225, 2009.
  * [Har48] Harris, T. E.: Branching Processes._The Annals of Mathematical Statistics_ , 19(4):474 – 494, 1948.
  * [WDK13] Wachtel, V.I., Denisov, D. E. and Korshunov, D. A.: Tail asymptotics for the supercritical galton-watson process in the heavy-tailed case. _Proceedings of the Steklov Institute of Mathematics_ , 282:273–297, 2013.