# Maximal diameter of integral circulant graphs

Milan Bašić<EMAIL_ADDRESS>Aleksandar Ilić<EMAIL_ADDRESS>Aleksandar Stamenković<EMAIL_ADDRESS>Faculty of Sciences and Mathematics,
University of Niš, Serbia  Facebook Inc, Menlo Park, California,USA

###### Abstract

Integral circulant graphs are proposed as models for quantum spin networks
that permit a quantum phenomenon called perfect state transfer. Specifically,
it is important to know how far information can potentially be transferred
between nodes of the quantum networks modelled by integral circulant graphs
and this task is related to calculating the maximal diameter of a graph. The
integral circulant graph $\mathrm{ICG}_{n}(D)$ has the vertex set
$Z_{n}=\\{0,1,2,\ldots,n-1\\}$ and vertices $a$ and $b$ are adjacent if
$\gcd(a-b,n)\in D$, where $D\subseteq\\{d:d\mid n,\ 1\leq d<n\\}$. Motivated
by the result on the upper bound of the diameter of $\mathrm{ICG}_{n}(D)$
given in [N. Saxena, S. Severini, I. Shparlinski, Parameters of integral
circulant graphs and periodic quantum dynamics, International Journal of
Quantum Information 5 (2007), 417–430], according to which $2|D|+1$ represents
one such bound, in this paper we prove that the maximal value of the diameter
of the integral circulant graph $\mathrm{ICG}_{n}(D)$ of a given order $n$
with its prime factorization $p_{1}^{\alpha_{1}}\cdots p_{k}^{\alpha_{k}}$, is
equal to $r(n)$ or $r(n)+1$, where $r(n)=k+|\\{i\ |\alpha_{i}>1,\ 1\leq i\leq
k\\}|$, depending on whether $n\not\in 4{\mathbb{N}}+2$ or not, respectively.
Furthermore, we show that, for a given order $n$, a divisor set $D$ with
$|D|\leq k$ can always be found such that this bound is attained. Finally, we
calculate the maximal diameter in the class of integral circulant graphs of a
given order $n$ and cardinality of the divisor set $t\leq k$ and characterize
all extremal graphs. We actually show that the maximal diameter can have the
values $2t$, $2t+1$, $r(n)$ and $r(n)+1$ depending on the values of $t$ and
$n$. This way we further improve the upper bound of Saxena, Severini and
Shparlinski and we also characterize all graphs whose diameters are equal to
$2|D|+1$, thus generalizing a result in the above mentioned paper.

###### keywords:

Integral circulant graphs , Diameter , Chinese Remainder Theorem , Quantum
networks

###### MSC:

05C12 , 11A07 , 81P45

††journal: Information and Computation

##  1 Introduction

Circulant graphs are Cayley graphs over a cyclic group. A graph is called
integral if all the eigenvalues of its adjacency matrix are integers. In other
words, the corresponding adjacency matrix of a circulant graph is the
circulant matrix (a special kind of a Toeplitz matrix where each row vector is
rotated one element to the right relative to the preceding row vector).
Integral graphs are extensively studied in the literature and there has been a
vast research on some types of classes of graphs with integral spectrum. The
interest for circulant graphs in graph theory and applications has grown
during the last two decades. They appear in coding theory, telecommunication
network, VLSI design, parallel and distributed computing (see [9] and
references therein).

Integral circulant graphs have found important applications in molecular
chemistry for modeling energy-like quantities such as the heat of formation of
a hydrocarbon [10, 12, 15, 17]. Recently there has been a vast research on the
interconnection schemes based on circulant topology – circulant graphs
represent an important class of interconnection networks in parallel and
distributed computing (see [9]). Recursive circulants are proposed as an
interconnection structure for multicomputer networks [14]. While retaining the
attractive properties of hypercubes such as node-symmetry, recursive
structure, connectivity etc., these graphs achieve noticeable improvements in
diameter.

As circulants possess many interesting properties (such as vertex transitivity
called mirror symmetry), they are applied in quantum information transmission
and proposed as models for quantum spin networks that permit the quantum
phenomenon called perfect state transfer [1, 2, 16]. In the quantum
communication scenario, the important feature of this kind of quantum graphs
(especially those with integral spectrum) is the ability of faithfully
transferring quantum states without modifying the network topology. More
precisely, these networks consist of $n$ qubits where some pairs of qubits are
coupled via XY-interaction and are described by an undirected graph $G$ on a
vertex set $V(G)=\\{1,2,\ldots,n\\}$, where there is an edge between vertices
$i$ and $j$ if $i$-th and $j$-th qubit are coupled. Formally, to each vertex
$i\in V$ , one can associate a Hilbert space ${\cal H}_{i}\simeq C^{2}$, so
that the Hilbert space associated with $G$ is given by ${\cal
H}_{G}=\bigotimes_{i\in V(G)}{\cal H}_{i}=(C^{2})^{\otimes n}.$ In [6] a
simple XY coupling is considered such that the dynamics of the system is
governed by the XY Hamiltonian

$H_{G}=\frac{1}{2}\sum_{(i,j)\in
E}\sigma_{i}^{x}\sigma_{j}^{x}+\sigma_{i}^{y}\sigma_{j}^{y},$

where the symbols $\sigma_{i}^{x}$ , $\sigma_{i}^{y}$ and $\sigma_{i}^{z}$ i
denote the Pauli matrices acting on the Hilbert space ${\cal H}_{i}$. Since
the operator of total $z$ component of the spin
$\sigma^{z}_{tot}=\sum_{i=1}^{n}\sigma_{i}^{z}$ commutes with $H_{G}$, the
Hilbert space $\cal H_{G}$ is then decomposed into invariant subspaces, each
of which is a distinct eigenspace of the operator $\sigma^{z}_{tot}$. For the
purpose of quantum state transfer, it suffices to restrict our attention to
the single excitation subspace ${\cal S}_{G}$, which is the $n$-dimensional
eigenspace of $\sigma^{z}_{tot}$, corresponding to the eigenvalue $1-n/2$ .
The restriction of the Hamiltonian $H_{G}$ to the subspace $\mathcal{S}_{G}$
is an $n\times n$ matrix identical to the adjacency matrix $A_{G}$ of the
graph $G$ and hence the time evolution operator can be written in the form
$F(t)=\exp(\i A_{G}t)$. Perfect state transfer between different vertices
(qubits) $i$ and $j$ ($1\leq i,j\leq n$) is obtained in time $\tau$, if
$|F(\tau)_{ij}|=e_{i}^{T}F(t)\ e_{j}=1$, where
$e_{i}=(0,\ldots,0,1_{i},0,\ldots,0)$ is the standard basis in
${{\mathbb{R}}}^{n}$ (if $|F(\tau)_{ii}|=1$, we say the graph is periodic at
vertex $i$). Using the spectral decomposition of $A_{G}$ we represent the
perfect state transfer in terms its eigenvalues $\lambda_{k}$ and eigenvectors
$u_{k}$, $1\leq k\leq n$, as
$e_{i}^{T}(\sum_{k=1}^{n}e^{-i\lambda_{k}t}u_{k}u_{k}^{T})\ e_{j}=1$. In [16]
was shown that a quantum network whose hamiltonian is identical to the
adjacency matrix of a circulant graph is periodic if and only if all
eigenvalues of the graph are integers (that is, the graph is integral).
Therefore, circulant graphs having perfect state transfer must be integral
circulant graphs.

In this way we see that both combinatorial theory and the theory of graph
spectra (spectral theory of its adjacency matrix) are relevant for the
problems that we consider in quantum computing, but also in the fields such as
multiprocessor interconnection networks or complex networks. Therefore,
various spectral and combinatorial properties of integral circulant graphs
were recently investigated especially having in mind the study of certain
parameters useful for modeling a good quantum (or in general complex) network
that allows periodic dynamics. It was observed that integral circulant graphs
represent very reliable networks, meaning that the vertex connectivity of
these graphs is equal to the degree of their regularity. Moreover, for even
orders they are bipartite [16] – note that many of the proposed networks
mainly derived from the hypercube structure by twisting some pairs of edges
(twisted cube, crossed cub, multiply twisted cube, Möbius cube, generalized
twisted cube) are nonbipartite. Other important network metrics of integral
circulant graphs are analyzed as well, such as the degree, chromatic number,
the clique number, the size of the automorphism group, the size of the longest
cycle, the number of induced cycles of prescribed order ([3, 4, 5, 7, 11,
13]).

In this paper we continue the study of properties of circulant networks
relevant for the purposes of information transfer. Specifically, it would be
interesting to know how far information can potentially be transferred between
nodes of the networks modeled by the graph. So, it is important to know the
maximum length of all shortest paths between any pair of nodes. Moreover, for
a fixed number of nodes in the network, a larger diameter potentially implies
a larger maximum distance between nodes for which (perfect) transfer is
possible (communication distance). Therefore, for a given order of a circulant
graph the basic question is to find the circulant graph which maximizes the
diameter. The sharp upper bound of the diameter of a graph of a given order is
important for estimating the degradation of performance of the network
obtained by deleting a set of a certain number of vertices.

Throughout the paper we let $\mathrm{ICG}_{n}(D)$ be an arbitrary integral
circulant graph of order $n$ and set of divisors $D$. In [16], the following
sharp bounds on the diameter of integral circulant graphs are obtained

###### Theorem 1.1

Let $t$ be the size of the smallest set of additive generators of $Z_{n}$
contained in $D$. Then

$t\leq diam(\mathrm{ICG}_{n}(D))\leq 2t+1.$

$\square$

Direct consequences of the previous assertion are the following bounds

$\displaystyle 2\leq diam(\mathrm{ICG}_{n}(D))\leq 2|D|+1.$ (1)

One of the main results in this paper shows the maximal diameter of integral
circulant graphs of a given order $n$ to be equal to $r(n)+1$, if $n\not\in
4{\mathbb{N}}+2$, and $r(n)$, if $n\in 4{\mathbb{N}}+2$, where

$r(n)=k+|\\{i\ |\alpha_{i}>1,\ 1\leq i\leq k\\}|$

for $n=p_{1}^{\alpha_{1}}\cdots p_{k}^{\alpha_{k}}$. From these results we
immediately conclude that the upper bound from (1) is never attainable for
$|D|>k$ (as $|D|$ grows, the difference between the upper bound from (1) and
the actual diameter of the graph grows as well). Furthermore, since
$diam(\mathrm{ICG}_{n}(D))\leq r(n)+1\leq 2k+1$ and the fact that the average
order of $k$ is $\ln\ln n$ ([8, p. 355]) we conclude that
$diam(\mathrm{ICG}_{n}(D))=O(\ln\ln n)$.

In Section 2 we prove that the bounds $r(n)$ and $r(n)+1$ are attainable for
integral circulant graphs $\mathrm{ICG}_{n}(D)$ such that $|D|\leq k$. This
fact helps us to prove that the maximal diameter of all integral circulant
graphs $\mathrm{ICG}_{n}(D)$ of a given order $n$ and the cardinality of the
divisor set $D$ equal to $k$, is $r(n)$ (Lemma 3.1). This result directly
implies that the diameters of graphs in this class of graphs are less or equal
to $2k$, whence we conclude that the bound (1) is not attainable either.
Moreover, in Theorem 3.2 we find all $\mathrm{ICG}_{n}(D)$, $|D|=k$ whose
diameter is equal to $r(n)$. In Theorems 3.4 and 3.6 we consider integral
circulant graphs $\mathrm{ICG}_{n}(D)$ such that there exists a prime $p_{i}$
not dividing any $d\in D$ and calculate that maximal diameter of this class of
graphs is equal to $r(n)$. After characterizing all extremal graphs, we also
determine all $\mathrm{ICG}_{n}(D)$ such that there exists a prime $p_{i}$ not
dividing any $d\in D$ whose diameter is equal to $2|D|+1$. This class of
graphs generalizes the example given in Theorem 5 from [16]. Finally, using
Theorem 3.8 we determine the maximal diameter of integral circulant graphs
$\mathrm{ICG}_{n}(D)$ of a given order $n$ and cardinality $t\leq k$ of the
divisor set, and characterize all extremal graphs. We actually show that the
maximal diameter can have the values $2t$, $2t+1$, $r(n)$ and $r(n)+1$
depending on the values of $t$ and $n$, as given by the equation (25). The
paper is concluded with a partial result about the maximal diameter of
integral circulant graphs having perfect state transfer. We also give some
comments considering lower bounds of diameters of integral circulant graphs.

##  2 Preliminaries

In this section we introduce some basic notations and definitions.

A circulant graph $G(n;S)$ is a graph on vertices
${\mathbb{Z}}_{n}=\\{0,1,\ldots,n-1\\}$ such that vertices $i$ and $j$ are
adjacent if and only if $i-j\equiv s\pmod{n}$ for some $s\in S$. The set $S$
is called the symbol set of graph $G(n;S)$. As we will consider undirected
graphs without loops, we assume that $S=n-S=\\{n-s\ |\ s\in S\\}$ and
$0\not\in S$. Note that the degree of the graph $G(n;S)$ is $|S|$.

A graph is integral if all its eigenvalues are integers. A circulant graph
$G(n;S)$ is integral if and only if

$S=\bigcup_{d\in D}G_{n}(d),$

for some set of divisors $D\subseteq D_{n}$ [18]. Here $G_{n}(d)=\\{k\ :\
\gcd(k,n)=d,\ 1\leq k\leq n-1\\}$, and $D_{n}$ is the set of all divisors of
$n$, different from $n$.

Therefore an integral circulant graph (in further text $\mathrm{ICG}$)
$G(n;S)$ is defined by its order $n$ and the set of divisors $D$. An integral
circulant graph with $n$ vertices, defined by the set of divisors $D\subseteq
D_{n}$ will be denoted by $\mathrm{ICG}_{n}(D)$. The term ‘integral circulant
graph’ was first introduced in the work of So, where the characterization of
the class of circulant graphs with integral spectra was given. The class of
integral circulant graphs is also known as ‘gcd-graphs’ and arises as a
generalization of unitary Cayley graphs [3, 13].

From the above characterization of integral circulant graphs we have that the
degree of an integral circulant graph is $\deg\mathrm{ICG}_{n}(D)=\sum_{d\in
D}\varphi(n/d).$ Here $\varphi(n)$ denotes the Euler-phi function [8]. If
$D=\\{d_{1},\ldots,d_{t}\\}$, it can be seen that $\mathrm{ICG}_{n}(D)$ is
connected if and only if $\gcd(d_{1},\ldots,d_{t})=1$, given that $G(n;s)$ is
connected if and only if $\gcd(n,S)=1$.

Recall that the greatest distance between any pair of vertices in a graph is
graph diameter. The distance $d(u,v)$ between two vertices $u$ and $v$ of a
graph is the minimum length of the paths connecting them.

Throughout this paper we let that the order of $\mathrm{ICG}_{n}(D)$ has the
following prime factorization $n=p_{1}^{\alpha_{1}}\cdots p_{k}^{\alpha_{k}}$.
Also, for a given prime number $p$ and an integer $n$, denote by $S_{p}(n)$
the maximal number $\alpha$ such that $p^{\alpha}\mid n$. If $S_{p}(n)=1$ we
write $p\|n$.

##  3 Main results

Let $G=\mathrm{ICG}_{n}(D)$ be a connected graph with maximal diameter in the
class of all integral circulant graphs of order $n$, and
$D=\\{d_{1},d_{2},\ldots,d_{t}\\}$.

Let $D^{\prime}$ be an arbitrary subset of $D$, such that $\gcd(\\{d\ |\ d\in
D^{\prime}\\})=1$. The graph $\mathrm{ICG}_{n}(D^{\prime})$ is connected and
clearly a subgraph of $\mathrm{ICG}_{n}(D)$, so it follows that

$diam(\mathrm{ICG}_{n}(D))\leq diam(\mathrm{ICG}_{n}(D^{\prime})).$

Since $\mathrm{ICG}_{n}(D)$ has maximal diameter, we have
$diam(\mathrm{ICG}_{n}(D^{\prime}))=$
$diam(\mathrm{ICG}_{n}(D))$. Therefore, we will find maximal diameter among
all $\mathrm{ICG}_{n}(D)$ such that for every subset of divisors
$D^{\prime}\subset D$ it holds that $\gcd(\\{d\ |\ d\in D^{\prime}\\})>1$ (the
graphs $\mathrm{ICG}_{n}(D^{\prime})$ are unconnected). Furthermore, from the
last assumption it follows that
$gcd(d_{1},\ldots,d_{s-1},d_{s+1},\ldots,d_{t})>1$ for every $1\leq s\leq t$
and from the connectedness of $\mathrm{ICG}_{n}(D)$ we have
$\gcd(d_{1},d_{2},\ldots,d_{t})=1$. Thus, we conclude that for each $s$ there
exists a prime divisor $p_{i_{s}}$ of $n$ such that $p_{i_{s}}\nmid d_{s}$ and
$p_{i_{s}}\mid d_{j}$ for all $1\leq j\neq s\leq t$.

Therefore, we may define a bijective mapping

$f:\\{d_{1},\ldots,d_{t}\\}\rightarrow\\{p_{i_{1}},\ldots,p_{i_{t}}\\},$

since $d_{s_{1}}\neq d_{s_{2}}$ implies $p_{i_{s_{1}}}\neq p_{i_{s_{2}}}$.
Finally, we conclude that for every divisor $d_{s}$, $1\leq s\leq t$, it holds
that

$\displaystyle p_{i_{s}}$ $\displaystyle\nmid$ $\displaystyle d_{s}$ (2)
$\displaystyle p_{i_{1}},\ldots,p_{i_{s-1}},p_{i_{s+1}},\ldots,p_{i_{t}}$
$\displaystyle\mid$ $\displaystyle d_{s}.$ (3)

So, in the rest of the paper we will assume that the divisors of the integral
circulant graph $\mathrm{ICG}_{n}(D)$ have the property described above,
unless it is stated otherwise.

In the following example we show how to narrow the search for the maximal
diameter among all integral circulant graphs with order $n=12$ and divisor set
$D^{\prime}$ that has the properties (2) and (3). It is easy to see that we
have only two such examples $D^{\prime}=\\{2,3\\}$ and $D^{\prime}=\\{3,4\\}$
and the diameters of the graphs $\mathrm{ICG}_{12}(\\{2,3\\})$ and
$\mathrm{ICG}_{12}(\\{3,4\\})$ are $2$ and $3$, respectively. However, the
diameter of the graph $\mathrm{ICG}_{12}(\\{3,4,6\\})$, as an example of a
graph not having the properties (2) and (3), does not exceed the diameters of
the previous two graphs (Fig. 1).

Figure 1: Integral circulant graphs $\mathrm{ICG}_{12}(\\{3,4\\})$ on the left
and $\mathrm{ICG}_{12}(\\{3,4,6\\})$ on the right whose diameters are equal to
$3$ and $2$, respectively

Recall that two vertices $a$ and $b$ of
$\mathrm{ICG}_{n}(d_{1},d_{2},\ldots,d_{t})$ are adjacent if and only if
$\gcd(a-b,n)=d_{i}$ for some $1\leq i\leq t$. Given that the graph
$\mathrm{ICG}_{n}(D)$ is vertex-transitive, we are going to focus on the
vertex $0$ and construct shortest paths from the vertex $0$ to any other
vertex $0\leq l=|a-b|\leq n-1$.

If we manage to find a solution $x=(x_{1},x_{2},\ldots,x_{q})$ to the
following system of equations

$x_{1}+x_{2}+\cdots+x_{q}\equiv l\pmod{n}$

and

$\gcd(x_{i},n)=d_{h(i)}$

for $1\leq i\leq q$ and some function $h:\\{1,\ldots
q\\}\mapsto\\{1,\ldots,t\\}$, then we can construct the path from $0$ to $l$
of length $q$ passing through the vertices

$0,x_{1},x_{1}+x_{2},\ldots,x_{1}+x_{2}+\cdots+x_{q}.$

We are going to look for solutions of the above system of congruence equations
and greatest common divisor equalities, in the following representation

$\displaystyle d_{1}y_{1}+d_{2}y_{2}+\cdots+d_{t}y_{t}\equiv l\pmod{n}$ (4)

with the constraints

$\displaystyle\gcd(d_{j}y_{j},n)=d_{j}\qquad\mbox{for}\qquad 1\leq j\leq t,$
(5)

where each summand $d_{j}y_{j}$ corresponds to one or more $x_{i}$’s. Notice
that some of the $y_{j}$, $1\leq j\leq t$, can be equal to zero and in that
case we do not consider the constraint (5).

In the following lemma we prove that the upper bound of the diameter of
$\mathrm{ICG}_{n}(d_{1},d_{2},\ldots,d_{t})$, for $t=k$, is equal to $k+|\\{i\
|\alpha_{i}>1,\ 1\leq i\leq k\\}|$ and we denote this value by $r(n)$.

###### Lemma 3.1

The diameter of the integral circulant graph
$\mathrm{ICG}_{n}(d_{1},d_{2},\ldots,d_{k})$, where the set of divisors
$D=\\{d_{1},d_{2},\ldots,d_{k}\\}$ satisfies the properties (2) and (3), is
less or equal to $r(n)$.

Proof.  Since the order of the divisors in $D$ is arbitrary and $D$ satisfies
(2) and (3), we may suppose with out loss of generality that $i_{s}=s$, for
$1\leq s\leq k$. We are going to use the representation (4) for $t=k$, which
requires solving the following system

$d_{1}y_{1}+d_{2}y_{2}+\cdots+d_{k}y_{k}\equiv l\pmod{p_{j}^{\alpha_{j}}}\quad
1\leq j\leq k,\\\ $ (6)

with the constraints

$\displaystyle\gcd(d_{j}y_{j},n)=d_{j}\qquad\mbox{for}\qquad 1\leq j\leq k.$

The last equation is equivalent to

$\displaystyle\gcd(y_{j},\frac{n}{d_{j}})=1\qquad\Leftrightarrow\qquad\
p_{i}\nmid y_{j},\ \mbox{if}\ S_{p_{i}}(d_{j})<\alpha_{i},1\leq i\leq k.$ (7)

From (2) we have $S_{p_{j}}(d_{j})=0<\alpha_{j}$ and it directly holds that
$p_{j}\nmid y_{j}$.

Furthermore, as $\gcd(d_{j},p_{j}^{\alpha_{j}})=1$ it follows

$y_{j}\equiv(l-p_{j}t)\cdot d_{j}^{-1}\pmod{p_{j}^{\alpha_{j}}},$

where by $p_{j}t$ we denote
$d_{1}y_{1}+\cdots+d_{j-1}y_{j-1}+d_{j+1}y_{j+1}+\cdots+d_{k}y_{k}$. Note that
the only constraint is that $y_{j}$ cannot be divisible by $p_{j}$ as we
already discuss above.

If $p_{j}$ does not divide $l$, we can directly compute $y_{j}$ which is not
divisible by $p_{j}$. Assume now that $p_{j}$ divides $l$.

For $\alpha_{j}=1$, as $p_{j}\mid l$ we have

$y_{j}\equiv(l-p_{j}t)\cdot d_{j}^{-1}\equiv 0\pmod{p_{j}^{\alpha_{j}}}$

and we can decide not to include the summand $d_{j}y_{j}$ in the above
summation (otherwise, we obtain a contradiction with the constraint
$p_{j}\nmid y_{j}$). This basically means that we are going to put $y_{j}=0$
(ignore that summand) and in this case we do not consider the constraint
$\gcd(d_{j}y_{j},n)=d_{j}$.

For $\alpha_{j}>1$, assume that

$y_{j}\equiv(l-p_{j}t)\cdot d_{j}^{-1}\equiv p_{j}^{\beta_{j}}\cdot
s\pmod{p_{j}^{\alpha_{j}}},$ (8)

where $p_{j}\nmid s$. For $\beta_{j}=\alpha_{j}$, we can similarly drop the
summand $d_{j}y_{j}$ from the summation.

If $\beta_{j}<\alpha_{j}$, then $y_{j}=0$ obviously is not a solution of the
congruence equation. The trick now is to split $y_{j}$ into two summands
$y_{j}^{\prime}+y_{j}^{\prime\prime}$ which are both coprime with $p_{j}$ and
the sum is equal to $p_{j}^{\beta_{j}}\cdot s$ modulo $p_{j}^{\alpha_{j}}$.
This can be easily done by taking $y_{j}^{\prime}=1$ and
$y_{j}^{\prime\prime}=p_{j}^{\beta_{j}}\cdot s-1$. Therefore, we split the
summand $d_{j}y_{j}$ into two summands that satisfy all the conditions

$d_{j}\cdot 1+d_{j}\cdot(p_{j}^{\beta_{i}}\cdot s-1).$

This means that for the prime factors with $\alpha_{j}>1$ we need two edges in
order to construct a path from $0$ to $l$ when $p_{j}^{\beta_{j}}\|l-p_{j}t$,
$\beta_{j}<\alpha_{j}$.

Finally, we conclude that if we want to construct a path from $0$ to $l$, for
an arbitrary $l$, we need at most one edge that corresponds the modulo
$p_{j}$, if $\alpha_{j}=1$, and at most two edges that correspond the modulo
$p_{j}$, if $\alpha_{j}>1$, for every $1\leq j\leq k$. This means that
$diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{k}))\leq r(n)$.

$\square$

In the following theorem we show that the maximal diameter of
$\mathrm{ICG}_{n}(d_{1},d_{2},\ldots,d_{t})$, for $t=k$, is equal to $r(n)$
and characterize all extremal graphs.

###### Theorem 3.2

The maximal diameter of the integral circulant graph
$\mathrm{ICG}_{n}(d_{1},d_{2},\ldots,d_{k})$, where the set of divisors
$D=\\{d_{1},d_{2},\ldots,d_{k}\\}$ satisfies the properties (2) and (3), is
equal to $r(n)$. The equality holds in two following cases

  * i)

if $\alpha_{j}>1$ then $S_{p_{j}}(d_{i})>1$, for $1\leq i\neq j\leq k$

  * ii)

if $n\in 4{\mathbb{N}}+2$ and $d_{1}\in 2{\mathbb{N}}+1$ then there exists
exactly one $2\leq j\leq k$ such that $p_{j}\|d_{1}$, $S_{p_{j}}(d_{i})>1$,
for $2\leq i\leq k$ and other prime factors $p_{l}$ ($1\leq l\neq j\leq k$)
satisfy $S_{p_{l}}(d_{i})>1$, if $\alpha_{l}>1$, for $1\leq i\neq l\leq k$.

Proof.

Since the diameter of $\mathrm{ICG}_{n}(d_{1},d_{2},\ldots,d_{k})$ is less or
equal to $r(n)$, where the set of divisors $D=\\{d_{1},d_{2},\ldots,d_{k}\\}$
satisfies the properties (2) and (3), according to Lemma 3.1, in the first
part of the proof we analyze when the graph has diameter less than $r(n)$.
From (8) we conclude that this is the case when the condition $l-p_{j}t\equiv
0\pmod{p_{j}^{\alpha_{j}}}$ is satisfied, for $\alpha_{j}>1$ and $p_{j}\mid
l$.

Observe that the sum $p_{j}t$ can be rewritten in the following form

$\displaystyle
p_{j}(t_{1}+\cdots+t_{u_{j}})+p_{j}^{2}(t_{u_{j}+1}+\cdots+t_{k-1}),$ (9)

where $u_{j}=|\\{d_{i}\ |\ i\in\\{1,\ldots,j-1,j+1,\ldots,k\\},\
p_{j}\|d_{i},\ d_{i}y_{i}=p_{j}t_{i}\\}|$ and $p_{j}\nmid
t_{1},\ldots,t_{u_{j}}$. From (7) we conclude that this form is indeed always
possible since it holds that $p_{j}\nmid y_{1},\ldots,y_{u_{j}}$ as
$1=S_{p_{j}}(d_{i})<\alpha_{j}$, $1\leq i\leq u_{j}$. Furthermore, since we
take into consideration the values $d_{i}y_{i}$ modulo $p_{j}^{\alpha_{j}}$,
we can assume, with out loss of generality, that
$S_{p_{j}}(p_{j}^{2}t_{i})<\alpha_{j}$ for $u_{j}+1\leq i\leq k$, where
$d_{i}y_{i}=p_{j}^{2}t_{i}$. In that case, according to (7) it must be that
$p_{j}\nmid y_{i}$, for all $1\leq i\leq k$.

Assume first that $u_{j}\geq 2$. We see that $l-p_{j}t\equiv
0\pmod{p_{j}^{\alpha_{j}}}$ if and only if

$\displaystyle
t_{1}+\cdots+t_{u_{j}}+p_{j}(t_{u_{j}+1}+\cdots+t_{k-1})\equiv\frac{l}{p_{j}}\pmod{p_{j}^{\alpha_{j}-1}}.$
(10)

Furthermore, since $p_{j}\nmid t_{1}$ we see that $t_{1}$ must satisfy the
following system $t_{1}\equiv\frac{l}{p_{j}}-t_{2}-\cdots-
t_{u_{j}}-p_{j}(t_{u_{j}+1}+\cdots+t_{k-1})\pmod{p_{j}^{\alpha_{j}-1}}$ and
$t_{1}\not\equiv p_{j}s_{1}\pmod{p_{j}^{\alpha_{j}-1}}$, for some $0\leq
s_{1}<p_{j}^{\alpha_{j}-2}$. Again, since $p_{j}\nmid t_{2}$ too, we obtain
that $t_{2}\not\equiv\\{\frac{l}{p_{j}}-t_{3}-\cdots-
t_{u_{j}}-p_{j}(t_{u_{j}+1}+\cdots+t_{k-1})-p_{j}s_{1},p_{j}s_{2}\\}\pmod{p_{j}^{\alpha_{j}-1}}$,
for some $0\leq s_{2}<p_{j}^{\alpha_{j}-2}$. Therefore, if $p_{j}>2$ we can
find the value $t_{2}$ modulo $p_{j}^{\alpha_{j}-1}$ which is a solution of
the system if we take arbitrary values $t_{3},\ldots,t_{k-1}$ modulo
$p_{j}^{\alpha_{j}-1}$ (the value $t_{1}$ modulo $p_{j}^{\alpha_{j}-1}$ can be
obviously computed thereafter using the values $t_{2},\ldots,t_{k-1}$). If
$p_{j}=2$ and $\frac{l}{p_{j}}-t_{3}-\cdots-t_{u_{j}}\in 2{\mathbb{N}}+1$, we
can not find an odd $t_{2}$ which would be a solution of the system. For such
$l$, in the same way we can prove that the system
$d_{1}(y_{1}^{(1)}+y_{1}^{(2)})+d_{2}y_{2}+\cdots+d_{j-1}y_{j-1}+d_{j+1}y_{j+1}+\cdots+d_{k}y_{k}\equiv
l\pmod{p_{j}^{\alpha_{j}}}$, $p_{j}\nmid
y_{1}^{(1)},y_{1}^{(2)},y_{2},\ldots,y_{k}$, has a solution by reducing it to
the form
$t^{1}_{1}+t^{2}_{1}+t_{2}+\cdots+t_{u_{j}}+p_{j}(t_{u_{j}+1}+\cdots+t_{k-1})\equiv\frac{l}{p_{j}}\pmod{p_{j}^{\alpha_{j}-1}}$.
So, in this case we need at most two edges for the parts of the path from $0$
to $l$ corresponding to the moduli $p_{1}$ and $p_{j}$, since $l-p_{j}t\equiv
0\pmod{p_{j}^{\alpha_{j}}}$ and $y_{j}=0$. Finally, we conclude that the
diameter of this graph can not reach the value $r(n)$, since
$r(p_{1}^{\alpha_{1}})+r(p_{j}^{\alpha_{j}})>2$.

Now, let $u_{j}=1$. If $p_{j}>2$, similarly to the previous case by examining
the system
$d_{1}(y_{1}^{(1)}+y_{1}^{(2)})+d_{2}y_{2}+\cdots+d_{j-1}y_{j-1}+d_{j+1}y_{j+1}+\cdots+d_{k}y_{k}\equiv
l\pmod{p_{j}^{\alpha_{j}}}$ (which corresponds to the equation
$t^{1}_{1}+t^{2}_{1}+p_{j}(t_{2}+\cdots+t_{k-1})\equiv\frac{l}{p_{j}}\pmod{p_{j}^{\alpha_{j}-1}}$)
and $p_{j}\nmid y_{1}^{(1)},y_{1}^{(2)},y_{2},\ldots,y_{k}$, we see that we
can find $t^{1}_{1},t^{2}_{1},t_{2},\ldots,t_{k-1}$ such that $l-p_{j}t\equiv
0\pmod{p_{j}^{\alpha_{j}}}$ and therefore we can set $y_{j}=0$. Furthermore,
as $p_{1}\mid d_{2},\ldots,d_{k}$ it holds that
$d_{1}(y_{1}^{(1)}+y_{1}^{(2)})\equiv l\pmod{p_{1}}$ and if both
$y_{1}^{(1)},y_{1}^{(2)}\neq 0$ then we conclude that for $p_{1}=2$ and $l\in
2{\mathbb{N}}+1$ the parity of left and right hand sides of the equation is
violated ($p_{1}\nmid y_{1}^{(1)},y_{1}^{(2)}$). So, in this case we need one
extra edge and therefore at most three edges for the parts of the diameter
path corresponding to moduli $p_{1}$ and $p_{j}$. Finally, we conclude that
maximal diameter of this graph can be attained if the value
$r(p_{1}^{\alpha_{1}})+r(p_{j}^{\alpha_{j}})$ is equal to $3$ and this is the
case if only if $\alpha_{1}=1$. If $p_{j}=2$, we have already proved that for
$\frac{l}{p_{j}}\in 2{\mathbb{N}}$ the system
$t^{1}_{1}+t^{2}_{1}+p_{j}(t_{2}+\cdots+t_{k-1})\equiv\frac{l}{p_{j}}\pmod{p_{j}^{\alpha_{j}-1}}$,
$p_{j}\nmid t^{1}_{1},t^{2}_{1}$ has a solution (case $u_{j}=2$) and therefore
$l-p_{j}t\equiv 0\pmod{p_{j}^{\alpha_{j}}}$ ($y_{j}=0$). Considering the
modulus $p_{1}$, we can find $y_{1}^{(1)},y_{1}^{(2)}$ not divisible by
$p_{1}$ and $y_{1}^{(1)}+y_{1}^{(2)}=(l-p_{1}t^{\prime})d_{1}^{-1}$, where
$p_{1}t^{\prime}=d_{2}y_{2}+\ldots+d_{j-1}y_{j-1}+d_{j+1}y_{j+1}+\cdots+d_{k}y_{k}$
as $p_{1}>2$. In this case we need at most two edges for the parts of the path
from $0$ to $l$ corresponding to the moduli $p_{1}$ and $p_{j}$ (the diameter
of this graph can not reach the value $r(n)$). If $\frac{l}{p_{j}}\in
2{\mathbb{N}}+1$, assume that $p_{1}\nmid l$, then by examining the system
$d_{1}y_{1}+d_{2}y_{2}+\cdots+d_{j-1}y_{j-1}+d_{j+1}y_{j+1}+\cdots+d_{k}y_{k}\equiv
l\pmod{p_{j}^{\alpha_{j}}}$ (which corresponds to the equation
$t_{1}+p_{j}(t_{2}+\cdots+t_{k-1})\equiv\frac{l}{p_{j}}\pmod{p_{j}^{\alpha_{j}-1}}$)
and $p_{j}\nmid y_{1},y_{2},\ldots,y_{k}$, we see that $t_{1}\in
2{\mathbb{N}}+1$ satisfies the following system
$t_{1}\equiv\frac{l}{p_{j}}-p_{j}(t_{u_{j}+1}+\cdots+t_{k-1})\pmod{p_{j}^{\alpha_{j}-1}}$
and $t_{1}\not\equiv p_{j}s\pmod{p_{j}^{\alpha_{j}-1}}$, for some $0\leq
s<p_{j}^{\alpha_{j}-2}$. Moreover,
$y_{1}\equiv(l-p_{1}t^{\prime})d_{1}^{-1}\pmod{p_{1}^{\alpha_{1}}}$ is a
solution of the congruence equation modulo $p_{1}$ and in this case we need
one edge for the parts of the path from $0$ to $l$ corresponding to the moduli
$p_{1}$ and $p_{j}$ (the diameter of this graph can not reach the value
$r(n)$). Finally, if $\frac{l}{p_{j}}\in 2{\mathbb{N}}+1$ and $p_{1}\mid l$,
the following system can be similarly solved
$d_{2}y_{2}+\cdots+d_{j}(y_{j}^{1}+y_{j}^{2})+\cdots+d_{k}y_{k}\equiv
l\pmod{p_{j}^{\alpha_{j}}}$, $p_{j}\nmid y_{j}^{1},y_{j}^{2}$.

We have proved that if $u_{i}=1$, $n\in 2{\mathbb{N}}$ and $l,d_{1}\in
2{\mathbb{N}}+1$, we can find a solution of the congruence system
$d_{1}(y_{1}^{(1)}+y_{1}^{(2)}+y_{1}^{(3)})+d_{2}y_{2}+\cdots+d_{j-1}y_{j-1}+d_{j+1}y_{j+1}+\cdots+d_{k}y_{k}\equiv
l\pmod{p_{i}^{\alpha_{j}}}$, $p_{i}\nmid
y_{1}^{(1)},y_{1}^{(2)},y_{1}^{(3)},y_{2},\ldots,y_{k}$. Notice, that if
$u_{j}=1$ and $p_{j}\|d_{1}$ we can find a solution of the congruence system
$d_{1}(y_{1}^{(1)}+y_{1}^{(2)}+y_{1}^{(3)})+d_{2}y_{2}+\cdots+d_{j-1}y_{j-1}+d_{j+1}y_{j+1}+\cdots+d_{k}y_{k}\equiv
l\pmod{p_{j}^{\alpha_{j}}}$, $p_{j}\nmid
y_{1}^{(1)},y_{1}^{(2)},y_{1}^{(3)},y_{2},\ldots,y_{k}$. This implies that we
can set $y_{j}=0$ and conclude that we need three edges for the parts of the
path corresponding to the moduli $p_{1}$, $p_{i}$ and $p_{j}$ and this path
can not attain the value $r(n)$. The same conclusion holds for more than two
prime divisors.

From the discussion above we conclude that the diameter path can attain the
value $r(n)$, if $S_{p_{j}}(d_{i})>1$ for $\alpha_{j}>1$ and
$i\in\\{1,\ldots,j-1,j+1,\ldots,k\\}$ (the case $u_{j}=0$). In yet another
case the value $r(n)$ of the diameter can be attained if
$S_{p_{j}}(d_{1})=1<S_{p_{j}}(d_{i})$, $2\leq i\leq k$, and $p_{j},d_{1}\in
2{\mathbb{N}}+1$, for $n\in 4{\mathbb{N}}+2$ (the case $u_{j}=1$). Now, we
prove that there exists a vertex $l_{0}$ where the distance from $0$ to
$l_{0}$ is equal to $r(n)$ in both of the mentioned cases.

In the first case, we derive $l_{0}$ from the system of congruence equations
composed by choosing exactly one of the following equation, for each $1\leq
j\leq k$ (which exists due to the Chinese remainder theorem)

$\displaystyle l_{0}\equiv-1\pmod{p_{j}}\qquad\mbox{ if }\alpha_{j}=1$
$\displaystyle l_{0}\equiv p_{j}\pmod{p_{j}^{\alpha_{j}}}\qquad\mbox{ if
}\alpha_{j}>1.$

For all $1\leq j\leq k$ such that $\alpha_{j}=1$, we need at least one summand
$d_{j}y_{j}$ in the representation (6) of $l_{0}$ since $l_{0}\not\equiv
0\pmod{p_{j}^{\alpha_{j}}}$ and all other $d_{i}$ are divisible by
$p_{j}^{\alpha_{j}}$ for $i\neq j$. On the other hand, for all $1\leq j\leq k$
such that $\alpha_{j}>1$ we cannot have exactly one such summand as otherwise
we would have $d_{j}y_{j}\equiv l_{0}-p_{j}^{2}t^{\prime}\equiv
p_{j}s\pmod{p_{j}^{\alpha_{j}}}$ and $p_{j}\nmid s$, which would be a
contradiction as $p_{j}\nmid d_{j}y_{j}$, where
$p_{j}^{2}t^{\prime}=d_{1}y_{1}+\cdots+d_{j-1}y_{j-1}+d_{j+1}y_{j+1}+\cdots+d_{k}y_{k}$.
Therefore, we need at least two summands for $\alpha_{j}>1$.

In the second case, we derive $l_{0}$ from the following system of congruence
equations

$\displaystyle l_{0}\equiv-1\pmod{p_{i}}\qquad\mbox{ if }\alpha_{i}=1$
$\displaystyle l_{0}\equiv p_{j}^{2}\pmod{p_{j}^{\alpha_{j}}}\qquad\mbox{ if
}S_{p_{j}}(d_{1})=1<S_{p_{j}}(d_{l}),\ 2\leq l\leq k$ $\displaystyle
l_{0}\equiv p_{i}\pmod{p_{i}^{\alpha_{i}}}\qquad\mbox{ if }\alpha_{i}>1,\
i\neq j.$

It remains to prove that we need two edges by considering the modulus
$p_{j}^{\alpha_{j}}$, for $p_{j},d_{1}\in 2{\mathbb{N}}+1$ and
$S_{p_{j}}(d_{1})=1<S_{p_{j}}(d_{l}),\ 2\leq l\leq k$. Indeed, we cannot have
exactly one such summand as otherwise we would have $d_{j}y_{j}\equiv
l_{0}-p_{j}t\equiv p_{j}s\pmod{p_{j}^{\alpha_{j}}}$ and $p_{j}\nmid s$, which
is a contradiction due to $p_{j}\nmid d_{j}y_{j}$.

This proves that the diameter of $\mathrm{ICG}_{n}(D)$ in these cases is
greater or equal to $r(n)$ and therefore $diam(\mathrm{ICG}_{n}(D))=r(n)$,
which completes the proof of the theorem. $\square$

We provide several examples to illustrate how Theorem 3.2 is applied to
determine whether the diameter of $\mathrm{ICG}_{n}(D)$ such that $|D|=k$
attains $r(n)$.

  * $i)$

If $n=2^{2}\cdot 3^{3}\cdot 5$ and $D=\\{3^{2}\cdot 5,2^{2}\cdot 5,2^{2}\cdot
3^{3}\\}$ then $diam(\mathrm{ICG}_{n}(D))=5$, according to the first part of
Theorem 3.2 and therefore the diameter of the graph attains $r(n)$.

We will also compute the diameter of $\mathrm{ICG}_{n}(d_{1},d_{2},d_{3})$ for
$n=2^{2}\cdot 3^{3}\cdot 5$, $d_{1}=3^{2}\cdot 5$, $d_{2}=2^{2}\cdot 5$ and
$d_{3}=2^{2}\cdot 3^{3}$ to illustrate the methods from the proof of Theorem
3.2. Indeed, for any $0\leq l\leq n-1$ we will try to solve the equation in
the following form $d_{1}y_{1}+d_{2}y_{2}+d_{3}y_{3}\equiv l\pmod{n}$, with
the constraints $\gcd(d_{j}y_{j},n)=d_{j}$, for $1\leq j\leq 3$. This is
equivalent with the following system

$\displaystyle y_{1}$ $\displaystyle\equiv$
$\displaystyle(l-d_{2}y_{2}-d_{3}y_{3})\cdot d_{1}^{-1}\pmod{2^{2}}$
$\displaystyle y_{2}$ $\displaystyle\equiv$
$\displaystyle(l-d_{1}y_{1}-d_{3}y_{3})\cdot d_{2}^{-1}\pmod{3^{3}}$
$\displaystyle y_{3}$ $\displaystyle\equiv$
$\displaystyle(l-d_{1}y_{1}-d_{2}y_{2})\cdot d_{3}^{-1}\pmod{5},$

where $2\nmid y_{1}$, $3\nmid y_{2}$ and $5\nmid y_{3}$. If $2\nmid l$ then we
can directly compute $y_{1}$. Similarly if $3\nmid l$ or $5\nmid l$, we can
directly compute $y_{2}$ or $y_{3}$, respectively. In particular, if $2\nmid
l$, $3\nmid l$ and $5\nmid l$ we conclude that the distance between $0$ and
$l$ is equal to $3$.

If $2^{2}\mid l-d_{2}y_{2}-d_{3}y_{3}$ or $3^{3}\mid l-d_{1}y_{1}-d_{3}y_{3}$
or $5\mid l-d_{1}y_{1}-d_{2}y_{2}$ then we obtain that a solution of the
corresponding equation is $y_{1}=0$ or $y_{2}=0$ or $y_{3}=0$, respectively.
On the other hand, if $3^{2}\|l-d_{1}y_{1}-d_{3}y_{3}$ or
$3\|l-d_{1}y_{1}-d_{3}y_{3}$ we can not find $y_{2}$ satisfying the above
congruence equation such that $3\nmid y_{2}$. However, for such $l$ there
exist $y_{2}^{\prime}$ and $y_{2}^{\prime\prime}$ such that
$y_{2}^{\prime}+y_{2}^{\prime\prime}\equiv(l-d_{1}y_{1}-d_{3}y_{3})\cdot
d_{2}^{-1}\pmod{3^{3}}$ and $3\nmid y_{2}^{\prime},y_{2}^{\prime\prime}$. This
means that we need two edges in order to construct a path from $0$ to $l$ when
$3^{2}\|l-d_{1}y_{1}-d_{3}y_{3}$ or $3\|l-d_{1}y_{1}-d_{3}y_{3}$ corresponding
to the modulus $3^{3}$. Similarly, if we take $2\|l-d_{2}y_{2}-d_{3}y_{3}$ in
order to construct a path from $0$ to $l$ we need two edges corresponding to
the modulus $2^{2}$. Finally, the distance between any two vertices is less or
equal to $5$. According to the above discussion we can choose $l$ such that

$\displaystyle l$ $\displaystyle\equiv$ $\displaystyle-1\pmod{5}$
$\displaystyle l$ $\displaystyle\equiv$ $\displaystyle 3\pmod{3^{3}}$
$\displaystyle l$ $\displaystyle\equiv$ $\displaystyle 2\pmod{2^{2}},$

and calculate that $l=354$ using the Chinese Remainder Theorem. Therefore, we
conclude that the distance between $0$ and $l$ is equal to $5$.

  * $ii)$

If $n=2\cdot 3^{3}\cdot 5^{3}$ and $D=\\{3\cdot 5^{2},2\cdot 5^{3},2\cdot
3^{2}\\}$ then $diam(\mathrm{ICG}_{n}(D))=5$, due to the part $ii)$ of Theorem
3.2 as there exists exactly one $p_{j}=3\mid d_{1}$ such that
$S_{p_{j}}(d_{1})=1<S_{p_{j}}(d_{3})$ and $d_{1}\in 2{\mathbb{N}}+1$, for
$n\in 4{\mathbb{N}}+2$ and the diameter of the graph is equal to $r(n)=5$.

  * $iii)$

If $n=2^{2}\cdot 3^{2}\cdot 5\cdot 7$ and $D=\\{3\cdot 5\cdot 7,2^{2}\cdot
5\cdot 7,2^{2}\cdot 3^{2}\cdot 7,2^{2}\cdot 3^{2}\cdot 5\\}$ then
$diam(\mathrm{ICG}_{n}(D))=5$ (less than $r(n)$), as $n\in 4{\mathbb{N}}$ even
though the other conditions from the part $ii)$ of Theorem 3.2 are satisfied.
On the other hand, since $S_{p_{2}}(n)>1$, for $p_{2}=3$, and
$S_{p_{2}}(d_{1})=1$, we conclude that first part of the theorem is not
satisfied.

  * $iv)$

If $n=2^{2}\cdot 3\cdot 5\cdot 7$ and $D=\\{3\cdot 5\cdot 7,2\cdot 5\cdot
7,2^{2}\cdot 3\cdot 7,2^{2}\cdot 3\cdot 5\\}$ then
$diam(\mathrm{ICG}_{n}(D))=4$ (less than $r(n)$), as all conditions from the
part $i)$ of Theorem 3.2 are satisfied except $S_{p_{1}}(d_{2})>1$ for
$p_{1}=2$ and $d_{2}=2\cdot 5\cdot 7$.

  * $v)$

If $n=2\cdot 3^{2}\cdot 5^{2}\cdot 7^{2}$ and $D=\\{3\cdot 5\cdot 7,2\cdot
5^{2}\cdot 7^{2},2\cdot 3^{2}\cdot 7^{2},2\cdot 3^{2}\cdot 5^{2}\\}$ then
$diam(\mathrm{ICG}_{n}(D))=5$ (less than $r(n)$), as the condition from the
part $ii)$ of Theorem 3.2 is satisfied for more than one divisor (in this for
three divisors $p_{j}\in\\{3,5,7\\}$).

We also directly conclude that in the class of all integral circulant graphs
with a given order $n$ and $k-$element divisor set $D$ we can not find an
example for which $diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{k}))=2k+1$, since
$diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{k}))\leq r(n)\leq 2k$. So, in this case
the upper bound from (1) is not attainable.

###### Lemma 3.3

Let $d$ be an arbitrary divisor of $n$. For any $l$ divisible by $d$ there
exist $y_{1}$ and $y_{2}$ such that

$\displaystyle d(y_{1}+y_{2})\equiv l\pmod{n},\mbox{ if }\frac{n}{d}\in
2{\mathbb{N}}+1$ $\displaystyle d(y_{1}+y_{2}+1)\equiv l\pmod{n},\mbox{ if
}\frac{n}{d}\in 2{\mathbb{N}}$

and $\gcd(dy_{i},n)=d$, $1\leq i\leq 2$.

Proof.  We find a representation of $l$ in the following form
$dy_{1}+dy_{2}\equiv l\pmod{n}$ such that $\gcd(dy_{1},n)=d$,
$\gcd(dy_{2},n)=d$ and prove that the representation of $l$ exists if
$\frac{n}{d}\in 2{\mathbb{N}}+1$. We actually need to find $y_{1}$ and $y_{2}$
such that $y_{1}+y_{2}\equiv\frac{l}{d}\pmod{\frac{n}{d}}$,
$\gcd(y_{1},\frac{n}{d})=1$ and $\gcd(y_{2},\frac{n}{d})=1$. Now, let $p_{i}$
be an arbitrary divisor of $\frac{n}{d}$ such that
$S_{p_{i}}(\frac{n}{d})=\alpha_{i}$. By solving the above congruence equation
system modulo $p_{i}^{\alpha_{i}}$ we get that
$y_{1}\equiv\frac{l}{d}-y_{2}\not\equiv p_{i}u\pmod{p_{i}^{\alpha_{i}}}$ and
$y_{2}\not\equiv 0\pmod{p_{i}}$ (which is equivalent to $y_{2}\not\equiv
p_{i}v\pmod{p_{i}^{\alpha_{i}}}$), for $0\leq u,v<p_{i}^{\alpha_{i}-1}-1$.
Finally, we obtain
$y_{2}\not\equiv\\{p_{i}v,\frac{l}{d}-p_{i}u\\}\pmod{p_{i}^{\alpha_{i}}}$ and
it can be concluded that the maximal number of values that $y_{2}$ modulo
$p_{i}^{\alpha_{i}}$ can not take is equal to $2p_{i}^{\alpha_{i}-1}$. This
number is less than the number of residues modulo $p_{i}^{\alpha_{i}}$ for
$p_{i}>2$, so this system has a solution in this case. Now, suppose that
$\frac{n}{d}\in 2{\mathbb{N}}$. In the case for $p_{i}=2$ we observe that
there also exists $y_{2}$ modulo $p_{i}^{\alpha_{i}}$ if $\frac{l}{d}\in
2{\mathbb{N}}$. Furthermore, for $p_{i}=2$ and $\frac{l}{d}\in
2{\mathbb{N}}+1$, we have already concluded that there exists $y_{1},y_{2}\in
2{\mathbb{N}}+1$ such that $dy_{1}+dy_{2}\equiv l-d\pmod{p_{i}^{\alpha_{i}}}$
(notice that $\frac{l-d}{d}\in 2{\mathbb{N}}$) and therefore the
representation $dy_{1}+dy_{2}+d\equiv l\pmod{n}$ exists, under the constraints
$\gcd(dy_{1},n)=d$ and $\gcd(dy_{2},n)=d$.

$\square$

###### Theorem 3.4

Let $diam(\mathrm{ICG}_{m}(d_{1},\ldots,d_{t}))=d>2$. For $n^{\prime}>1$ such
that $\gcd(n^{\prime},m)=1$ it holds that

$\displaystyle diam(\mathrm{ICG}_{mn^{\prime}}(d_{1},\ldots,d_{t}))$
$\displaystyle=$ $\displaystyle\left\\{\begin{array}[]{rl}d+1,&n^{\prime}\in
2{\mathbb{N}}\\\ d,&n^{\prime}\in 2{\mathbb{N}}+1.\\\ \end{array}\right.$ (13)

Proof.  Let
$d_{1}^{\prime}y_{1}+d_{2}^{\prime}y_{2}+\cdots+d_{s}^{\prime}y_{s}$ be a
representation of $0\leq l\leq n^{\prime}m-1$ modulo $m$ that satisfies the
equations $\gcd(d_{j}^{\prime}y_{1},m)=d_{j}^{\prime}$, such that $0\leq s\leq
d$ and $d_{j}^{\prime}\in\\{d_{1},\ldots,d_{t}\\}$, $1\leq j\leq s$.

Now, we examine which additional conditions $y_{1},y_{2},\ldots,y_{s}$ must
satisfy by considering the following system

$\displaystyle
d_{1}^{\prime}y_{1}+d_{2}^{\prime}y_{2}+\cdots+d_{s}^{\prime}y_{s}\equiv
l\pmod{mn^{\prime}}$
$\displaystyle\gcd(d_{j}^{\prime}y_{j},mn^{\prime})=d_{j}^{\prime},\ 1\leq
j\leq s.$

Since $\gcd(n^{\prime},m)=1$, $\gcd(d_{j}^{\prime}y_{j},m)=d_{j}^{\prime}$ and
$d_{1}^{\prime}y_{1}+d_{2}^{\prime}y_{2}+\cdots+d_{s}^{\prime}y_{s}\equiv
l\pmod{m}$, we conclude that it is sufficient to find
$y_{1},y_{2},\ldots,y_{s}$ such that for every $p_{i}\mid n^{\prime}$ it holds

$\displaystyle
d_{1}^{\prime}y_{1}+d_{2}^{\prime}y_{2}+\cdots+d_{s}^{\prime}y_{s}\equiv
l\pmod{n^{\prime}}$ (14) $\displaystyle p_{i}\nmid y_{j},\ 1\leq j\leq s,\
1\leq i\leq u,$ (15)

where $u$ denotes the number of prime factors of $n^{\prime}$.

Let $s=1$. From (14) and (15) follow that $y_{1}\equiv
d_{1}^{{}^{\prime}-1}l\pmod{p_{i}^{\alpha_{i}}}$ and $y_{1}\not\equiv
0\pmod{p_{i}}$ must be satisfied, for every $1\leq i\leq u$ . But, if
$p_{i}\mid l$ then the system has no solution and we first proceed by
considering the representation of $l$ in the following form
$d_{1}^{\prime}y_{1}^{(1)}+d_{1}^{\prime}y_{1}^{(2)}\equiv l\pmod{m}$ such
that $\gcd(d_{1}^{\prime}y_{1}^{(1)},m)=d_{1}^{\prime}$ and
$\gcd(d_{1}^{\prime}y_{1}^{(2)},m)=d_{1}^{\prime}$. According to Lemma 3.3
there exists such a representation if $\frac{m}{d_{1}^{\prime}}\in
2{\mathbb{N}}+1$. Moreover, using the same assertion there is a representation
of $l$ in the following form
$d_{1}^{\prime}y_{1}^{(1)}+d_{1}^{\prime}y_{1}^{(2)}+d_{1}^{\prime}\equiv
l\pmod{m}$ such that $\gcd(d_{1}^{\prime}y_{1}^{(1)},m)=d_{1}^{\prime}$ and
$\gcd(d_{1}^{\prime}y_{1}^{(2)},m)=d_{1}^{\prime}$ if
$\frac{m}{d_{1}^{\prime}}\in 2{\mathbb{N}}$.

Notice that $s=0$ if and only if $l$ is divisible by $m$. This means that
$d_{j}\mid l$ for $1\leq j\leq t$ and hence we can proceed as in the previous
case by finding a representation of $l$ modulo $m$ on two or three summands
depending on the parity of $m$.

Now, in the following we show that for every representation
$d_{1}^{\prime}y_{1}+d_{2}^{\prime}y_{2}+\cdots+d_{s}^{\prime}y_{s}\equiv
l\pmod{m}$ with constraints $\gcd(d_{j}^{\prime}y_{1},m)=d_{j}^{\prime}$ and
$s>1$ there exists the representation (14) under the constraints (15) with $s$
or $s+1$ summands (depending on the parity of $n^{\prime}$). Indeed, for any
prime $p_{i}\mid n^{\prime}$ ($1\leq i\leq u$) where
$S_{p_{i}}(n^{\prime})=\alpha_{i}$, we have that $\gcd(m,p_{i})=1$ implying
that $\gcd(d_{j},p_{i})=1$, for $1\leq j\leq t$. Thus, from (14) and (15), we
conclude that

$\displaystyle y_{1}$ $\displaystyle\equiv$
$\displaystyle(l-d_{2}^{\prime}y_{2}-\cdots-
d_{s}^{\prime}y_{s})d_{1}^{{}^{\prime}-1}\pmod{p_{i}^{\alpha_{i}}}$
$\displaystyle y_{1}$ $\displaystyle\not\equiv$ $\displaystyle
p_{i}v\pmod{p_{i}^{\alpha_{i}}},\ 0\leq v<p_{i}^{\alpha_{i}-1}.$

From these two conditions it follows that $(l-d_{2}^{\prime}y_{2}-\cdots-
d_{s}^{\prime}y_{s})d_{1}^{{}^{\prime}-1}\not\equiv
p_{i}v\pmod{p_{i}^{\alpha_{i}}}$, $0\leq v<p_{i}^{\alpha_{i}-1}$, whence we
further obtain that

$\displaystyle y_{2}$ $\displaystyle\not\equiv$
$\displaystyle(l-d_{3}^{\prime}y_{3}-\cdots-
d_{s}^{\prime}y_{s}-p_{i}d^{\prime}_{1}v)d_{2}^{{}^{\prime}-1}\pmod{p_{i}^{\alpha_{i}}}$
$\displaystyle y_{2}$ $\displaystyle\not\equiv$ $\displaystyle
p_{i}w\pmod{p_{i}^{\alpha_{i}}},\ 0\leq w<p_{i}^{\alpha_{i}-1}.$

Since $v$ and $w$ each may take $p_{i}^{\alpha_{i}-1}$ values, we conclude
that the maximal number of values modulo $p_{i}^{\alpha_{i}}$ that $y_{2}$ can
not take is equal to $2p_{i}^{\alpha_{i}-1}$. This number is obviously less
than the number of residues modulo $p_{i}^{\alpha_{i}}$ for $p_{i}>2$, from
where we further deduce that if $n^{\prime}\in 2{\mathbb{N}}+1$, this system
of congruence equations has a solution modulo $n^{\prime}$.

If $n^{\prime}\in 2{\mathbb{N}}$ and we take $p_{i}=2$ then (15) implies that
$y_{1},\ldots,y_{s}\in 2{\mathbb{N}}+1$ and as
$d_{1}^{\prime},\ldots,d_{s}^{\prime}$ are divisors of $m\in 2{\mathbb{N}}+1$
it also holds that $d_{1}^{\prime},\ldots,d_{s}^{\prime}\in 2{\mathbb{N}}+1$.
On the other hand, if we choose $l\not\equiv s\pmod{2}$, then we obtain that
$d_{1}^{\prime}y_{1}+d_{2}^{\prime}y_{2}+\cdots+d_{s}^{\prime}y_{s}\equiv
s\not\equiv l\pmod{2}$, which is a contradiction. This means that we can not
make the representation of $l$ into $s>0$ summands that satisfy the system of
congruence equations (14) and (15) for $n^{\prime}\in 2{\mathbb{N}}$ and $l$
such that $l\not\equiv s\pmod{2}$. However, since $l\not\equiv
l-d_{1}^{\prime}\pmod{2}$, there is a representation on $s$ summands of
$l-d^{\prime}_{1}$ and hence there is a representation on $s+1$ summands of
$l$ such that $l\not\equiv s\pmod{2}$.

From the above discussion we conclude that for $n^{\prime}\in 2{\mathbb{N}}+1$
($m\in 2{\mathbb{N}}$) the diameter of
$\mathrm{ICG}_{mn^{\prime}}(d_{1},\ldots,d_{t})$ is equal to
$\max\\{3,d\\}=d$. On the other hand, if $n^{\prime}\in 2{\mathbb{N}}$ ($m\in
2{\mathbb{N}}+1$) the diameter of
$\mathrm{ICG}_{mn^{\prime}}(d_{1},\ldots,d_{t})$ is equal to
$\max\\{2,d+1\\}=d+1$.

$\square$

###### Remark 3.5

Notice that for the complete graph $\mathrm{ICG}_{m}(D_{m})$ the diameter of
$\mathrm{ICG}_{mn^{\prime}}(D_{m})$ is equal to $2$ if $n^{\prime}\in
2{\mathbb{N}}+1$ and equal to $3$ if $n^{\prime}\in 2{\mathbb{N}}$. Indeed,
since for every edge $uv$ there exists the path $u-w-v$ we conclude that for
every $0\leq l\leq m-1$ there exists the representation (4) modulo $n$ on
$s=2$ summands and from the second part of the above proof the assertion
directly holds. Moreover, for the integral circulant graph such that
$diam(\mathrm{ICG}_{m}(D))=2$ and $m\in 2{\mathbb{N}}+1$, according to the
above proof we have that $diam(\mathrm{ICG}_{mn^{\prime}}(D))=3$. On the other
hand, if $m\in 2{\mathbb{N}}$ and for every $0\leq l\leq m-1$ there exists a
path $0-l_{1}-l$ for some $0\leq l_{1}\leq l\leq m-1$ the diameter of
$\mathrm{ICG}_{mn^{\prime}}(D)$ remains the same as the diameter of
$\mathrm{ICG}_{m}(D)$. Otherwise, $diam(\mathrm{ICG}_{mn^{\prime}}(D))=3$.

From Theorem 3.4 it follows that $diam(\mathrm{ICG}_{n\cdot
n^{\prime}}(d_{1},\ldots,d_{k}))\leq$
$diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{k}))+1$, for some $n^{\prime}>1$ and
$\gcd(n,n^{\prime})=1$. Furthermore, by Theorem 3.2 we have
$diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{k}))\leq r(n)$, which implies that
$diam(\mathrm{ICG}_{n\cdot n^{\prime}}(d_{1},\ldots,d_{k}))\leq r(n)+1$.
Finally, from the definition of the function $r$, since $\gcd(n,n^{\prime})=1$
and $n^{\prime}>1$, follows that $r(n)+1\leq r(n\cdot n^{\prime})$ and
therefore $diam(\mathrm{ICG}_{n\cdot n^{\prime}}(d_{1},\ldots,d_{k}))\leq
r(n\cdot n^{\prime})$ holds. Therefore, we can not increase the upper bound
given in Theorem 3.2 of the diameter of integral circulant graphs using
Theorem 3.4, but we can find new classes of graphs that attain the bound.

We further see that the equation $diam(\mathrm{ICG}_{n\cdot
n^{\prime}}(d_{1},\ldots,d_{k}))=r(n\cdot n^{\prime})$ holds if and only if
$diam(\mathrm{ICG}_{n\cdot
n^{\prime}}(d_{1},\ldots,d_{k}))=diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{k}))+1$,
$diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{k}))=r(n)$ and $r(n)+1=r(n\cdot
n^{\prime})=r(n)+r(n^{\prime})$. By Theorem 3.4 we obtain that
$diam(\mathrm{ICG}_{n\cdot
n^{\prime}}(d_{1},\ldots,d_{k}))=diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{k}))+1$
if and only if $n^{\prime}\in 2{\mathbb{N}}$ and $n\in 2{\mathbb{N}}+1$.
Furthermore, since $n\in 2{\mathbb{N}}+1$, the diameter of
$\mathrm{ICG}_{n}(d_{1},\ldots,d_{k})$ can attain the value $r(n)$ only in the
case given by the first part of the assertion of Theorem 3.2. Finally,
$r(n)+1=r(n)+r(n^{\prime})$ holds if and only if $n^{\prime}$ is prime and
this proves the following theorem.

###### Theorem 3.6

Let $diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{k}))>2$. The diameter of the
integral circulant graph $\mathrm{ICG}_{n\cdot
n^{\prime}}(d_{1},d_{2},\ldots,d_{k})$, where $n^{\prime}>1$,
$\gcd(n,n^{\prime})=1$ and the set of the divisors
$\\{d_{1},d_{2},\ldots,d_{k}\\}$ satisfies the properties (2) and (3) with
respect to primes $\\{p_{1},\ldots p_{k}\\}$, is less or equal to $r(n\cdot
n^{\prime})$. The equality holds if and only if $n^{\prime}=2$, $n\in
2{\mathbb{N}}+1$ and the sets of divisors $D\subseteq 2{\mathbb{N}}+1$
satisfies the conditions $i)$ in the assertion of Theorem 3.2.

We have already mentioned that Saxena, et al. determine the upper bound of the
diameter of $\mathrm{ICG}_{n}(d_{1},\ldots,d_{t})$ in terms of the number of
divisors $t$, i.e. $diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{t}))\leq 2t+1$. They
also present a class of integral circulant graphs in Theorem 5 [16], where
$n=2m$, $m=p_{1}^{2}\cdots p_{k}^{2}$ and
$D_{0}=\\{m/p_{1}^{2},\ldots,m/p_{k}^{2}\\}$ as an example for which the bound
is tight. However, using a similar approach as in the proof of Theorem 3.6 we
can characterize all the graphs $\mathrm{ICG}_{n\cdot
n^{\prime}}(d_{1},\ldots,d_{k})$ with the diameters equal to $2k+1$. First,
notice that

$diam(\mathrm{ICG}_{n\cdot n^{\prime}}(d_{1},\ldots,d_{k}))\leq
diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{k}))+1\leq r(n)+1\leq 2k+1.$

The equality holds if and only if $n^{\prime}\in 2{\mathbb{N}}$,
$\alpha_{1}>1,\ldots,\alpha_{k}>1$ and and the set of divisors
$\\{d_{1},\ldots,d_{k}\\}\subseteq 2{\mathbb{N}}+1$ satisfies the conditions
$i)$ in the assertion of Theorem 3.2. Finally, the diameter of
$\mathrm{ICG}_{n\cdot n^{\prime}}(d_{1},\ldots,d_{k})$, for
$\gcd(n,n^{\prime})=1$, attains the upper bound $2k+1$ if and only if
$n^{\prime}\in 2{\mathbb{N}}$ and for every $d_{j}\in 2{\mathbb{N}}+1$, $1\leq
j\leq k$, $p_{j}\nmid d_{j}$, $p_{i}^{2}\mid d_{j}$, $1\leq i\neq j\leq k$.
Clearly, the class of graphs $\mathrm{ICG}_{2m}(D_{0})$ found in Theorem 5 in
[16] has the smallest parameters $n$ and $d_{1},\ldots,d_{k}$ that satisfy the
condition above.

According to Remark 3.5 we can derive new classes of graphs whose maximal
diameters attain the upper bounds $r(n)$ or $r(n)+1$ in some special cases

###### Theorem 3.7

For a given positive integer $n>1$, the diameter of $\mathrm{ICG}_{n}(D)$ is
equal to $r(n)$ in the following cases

  * i)

$n=p_{1}p_{2}\in 2{\mathbb{N}}+1$, $D=\\{1\\}$,

  * ii)

$n=4p_{2}$, $D=\\{1\\}$,

  * iii)

$n=2p_{2}p_{3}$,
$D\in\\{\\{1\\},\\{1,p_{2}\\},\\{2,p_{2}\\},\\{p_{2},p_{3}\\},\\{1,p_{2},p_{3}\\}\\}$,

  * iv)

$n=2p_{2}^{2}$, $D\in\\{\\{1\\},\\{1,p_{2}\\}\\}$.

The diameter of $\mathrm{ICG}_{n}(D)$ is equal to $r(n)+1$ if $n=2p_{2}$,
$D=\\{1\\}$.

Proof.  Notice that $diam(\mathrm{ICG}_{n\cdot n^{\prime}}(D))=3$ if
$diam(\mathrm{ICG}_{n}(D))=1$ and $n^{\prime}\in 2{\mathbb{N}}$. We see that
$diam(\mathrm{ICG}_{n\cdot n^{\prime}}(D))$ attains $r(n\cdot n^{\prime})$ if
$n\cdot n^{\prime}\in\\{2p_{2}^{2},4p_{2},2p_{2}p_{3}\\}$. Since
$\gcd(n,n^{\prime})=1$, we further have
$(n^{\prime},n)\in\\{(2,p_{2}^{2}),(4,p_{2}),(2,p_{2}p_{3}),(2p_{2},p_{3})\\}$.
If $n=p_{2}$ then $diam(\mathrm{ICG}_{n}(D))=1$ for $D=\\{1\\}$, if
$n=p_{2}^{2}$ then $diam(\mathrm{ICG}_{n}(D))=1$ for $D=\\{1,p_{2}\\}$ and if
$n=p_{2}p_{3}$ then $diam(\mathrm{ICG}_{n}(D))=1$ for $D=\\{1,p_{2},p_{3}\\}$.
Furthermore, $diam(\mathrm{ICG}_{n\cdot n^{\prime}}(D))$ attains $r(n\cdot
n^{\prime})+1$ if $n\cdot n^{\prime}=2p_{2}$ and therefore
$(n^{\prime},n)=(2,p_{2})$, $D=\\{1\\}$.

The diameter of $\mathrm{ICG}_{n\cdot n^{\prime}}(D)$ is equal to $2$ if
$diam(\mathrm{ICG}_{n}(D))=1$ and $n^{\prime}\in 2{\mathbb{N}}+1$. Moreover,
$diam(\mathrm{ICG}_{n\cdot n^{\prime}}(D))$ attains $r(n\cdot n^{\prime})$ if
$(n,n^{\prime})=(p_{1},p_{2})$ and $diam(\mathrm{ICG}_{n}(D))=1$ if
$D=\\{1\\}$.

The diameter of $\mathrm{ICG}_{n\cdot n^{\prime}}(D)$ is equal to $3$ if
$diam(\mathrm{ICG}_{n}(D))=2$ and $n\in 2{\mathbb{N}}+1$. Moreover,
$diam(\mathrm{ICG}_{n\cdot n^{\prime}}(D))=3$ attains $r(n\cdot n^{\prime})$
if $(n^{\prime},n)\in\\{(2,p_{2}p_{3}),(2p_{2},p_{3}),(2,p_{2}^{2})\\}$. If
$n=p_{2}p_{3}$ then $diam(\mathrm{ICG}_{n}(D))=2$ for
$D\in\\{\\{1\\},\\{1,p_{2}\\},\\{p_{2},p_{3}\\}\\}$, and if $n=p_{2}^{2}$ then
$diam(\mathrm{ICG}_{n}(D))=2$ for $D=\\{1\\}$.

The diameter of $\mathrm{ICG}_{n\cdot n^{\prime}}(D)$ is equal to $3$ if
$diam(\mathrm{ICG}_{n}(D))=2$, $n\in 2{\mathbb{N}}$ and there exists $0\leq
l\leq n-1$ such that $(0,l)$ are adjacent and there is no $0\leq l_{1}\neq
l\leq n-1$ such that $(0,l_{1})$ are adjacent and $(l_{1},l)$ are adjacent.
Moreover, $diam(\mathrm{ICG}_{n\cdot n^{\prime}}(D))=3$ attains $r(n\cdot
n^{\prime})$ if
$(n^{\prime},n)\in\\{(p_{2}p_{3},2),(p_{2},2p_{3}),(p_{2}^{2},2),(p_{2},4)\\}$.
If $n=2p_{3}$ then $D\in\\{\\{1,p_{3}\\},\\{2,p_{3}\\}\\}$ and if $n=4$ then
$D=\\{1\\}$.

$\square$

In the following assertion without loss of generality we assume that the
indices $\\{i_{1},\ldots,i_{t}\\}$ from the properties (2) and (3) are equal
$\\{1,\ldots,t\\}$. Furthermore, we also suppose that for every prime $p_{i}$,
$1\leq i\leq k$, there exists at least one $d_{j}$, $1\leq j\leq t$, such that
$p_{i}\mid d_{j}$ (in the opposite case we have already calculated the
diameter in Theorem 3.6).

###### Theorem 3.8

Let $\mathrm{ICG}_{n}(d_{1},d_{2},\ldots,d_{t})$ be an integral circulant
graph such that $t<k$ and the set of the divisors
$D=\\{d_{1},d_{2},\ldots,d_{t}\\}$ satisfies the properties (2) and (3) with
respect to primes $\\{p_{1},p_{2},\ldots,p_{t}\\}$. Then, the diameter of the
of the graph is less or equal to

  * i)

$r(n)$, if $n\not\in 4{\mathbb{N}}+2$ and there exist at least two divisors
$p_{i}$ and $p_{j}$, $1\leq i\neq j\leq k$, such that
$\alpha_{i}=\alpha_{j}=1$. The equality holds if and only if
$\\{d_{1},\ldots,d_{t}\\}$ satisfies ($i$) from Theorem 3.2, there exist
$p_{1},\ldots,p_{t}\in 2{\mathbb{N}}+1$ and an injection
$f:\\{{t+1},\ldots,k\\}\rightarrow\\{1,\ldots,t\\}$ such that for every prime
$p_{j}$, $t+1\leq j\leq k$, there exists exactly one $d_{f(j)}$ such that
$p_{j}\nmid d_{f(j)}$ and $\alpha_{j}=\alpha_{f(j)}=1$.

  * ii)

$r(n)+1$, if $n\in 4{\mathbb{N}}+2$ and there exists at least one divisor
$p_{i}\in 2{\mathbb{N}}+1$, $1\leq i\leq k$, such that $\alpha_{i}=1$. The
equality holds if and only if $\\{d_{1},\ldots,d_{t}\\}$ satisfies ($i$) from
Theorem 3.2, there exist $p_{1},\ldots,p_{t}\in 2{\mathbb{N}}+1$ and an
injection $f:\\{{t+1},\ldots,k\\}\rightarrow\\{1,\ldots,t\\}$ such that for
every prime $p_{j}$, $t+1\leq j\leq k$, there exists exactly one $d_{f(j)}$
such that $p_{j}\nmid d_{f(j)}$ and $\alpha_{j}=\alpha_{f(j)}=1$.

  * iii)

$2t$, if $n\in 2{\mathbb{N}}+1$ and there exists at most one divisor $p_{i}$,
$1\leq i\leq k$, such that $\alpha_{i}=1$. The equality holds if and only if
there exist $p_{1},\ldots,p_{t}$ such that for every $d_{j}$, $1\leq j\leq t$,
$p_{i}^{2}\mid d_{j}$, $1\leq i\neq j\leq t$.

  * iv)

$2t+1$, if $n\in 2{\mathbb{N}}$ and there exists at most one divisor $p_{i}$,
$1\leq i\leq k$, such that $\alpha_{i}=1$. The equality holds if and only if
there exist $p_{1},\ldots,p_{t}\in 2{\mathbb{N}}+1$ such that for every
$d_{j}$, $1\leq j\leq t$, $p_{i}^{2}\mid d_{j}$, $1\leq i\neq j\leq t$.

Proof.  First we prove the parts $i)$ and $ii)$ of the assertion. According to
the proof of Lemma 3.1 we show that for every prime factor $p_{j}$, $1\leq
j\leq t$, we need at most one edge if $\alpha_{j}=1$ and two edges if
$\alpha_{j}>1$ in order to construct a path from $0$ to $l$, $0\leq l\leq
n-1$. Therefore, we can write

$\displaystyle d_{1}y_{1}+d_{2}y_{2}+\cdots+d_{t}y_{t}\equiv
l\pmod{p_{j}^{\alpha_{j}}},$ (16)

for $1\leq j\leq t$, where some $y_{i}$, $1\leq i\leq t$, need to be split
into two summands $y_{i}^{\prime}+y_{i}^{\prime\prime}$ for $\alpha_{i}>1$ and
certain values of $l$ modulo $p_{j}^{\alpha_{j}}$. Notice also that some of
$y_{i}$ can be equal to zero.

In the following, we examine how many edges we can add at the most to obtain
the diameter path when we consider modulus $p_{j}$, $t+1\leq j\leq k$. Now,
let $p_{j}$ be a prime factor of $n$ such that $t+1\leq j\leq k$. Observe that
the relation (16) can be rewritten in the following form

$\displaystyle s_{1}+\cdots+s_{u_{j}}+p_{j}(s_{u_{j}+1}+\cdots+s_{t})\equiv
l\pmod{p_{j}^{\alpha_{j}}},$ (17)

where $u_{j}=|\\{d_{i}\ |\ i\in\\{1,\ldots,t\\},\ \ p_{j}\nmid d_{i}\\}|$,
$s_{i}=d_{i}y_{i}$, for $1\leq i\leq u_{j}$ and $p_{i}s_{i}=d_{i}y_{i}$, for
$u_{j}+1\leq i\leq t$.

Suppose $p_{j}>2$. Using a consideration similar to the one given in the proof
of Theorem 3.2 for the existence of the solution $t_{1},\ldots,t_{k-1}$ in the
equation (10) we can conclude in the same way that there exist
$s_{1},\ldots,s_{t}$ modulo $p_{j}$ for $u_{j}>1$, such that $p_{j}\nmid
y_{1},\ldots,y_{t}$. This means that we do not need any additional edges for
the path from $0$ to $l$ corresponding to the modulus $p_{j}$. However, if
$u_{j}=1$ then it must be that $p_{j}\mid s_{1}$ for $l$ divisible by $p_{j}$,
which is a contradiction. Furthermore, as $p_{j}\in 2{\mathbb{N}}+1$ and
$p_{j}\nmid d_{1}$, according to Lemma 3.3 it holds that $y_{1}$ can be split
into two summands $y_{1}^{\prime}+y_{1}^{\prime\prime}$, since there exist
$y_{1}^{\prime}$ and $y_{1}^{\prime\prime}$ not divisible by $p_{j}$ such that
$y_{1}^{\prime}+y_{1}^{\prime\prime}\equiv(l-p_{j}t)d_{1}^{-1}\pmod{p_{j}^{\alpha_{j}}}$,
where $p_{j}t=d_{u_{j}+1}y_{u_{j}+1}+\cdots+d_{t}y_{t}$. Therefore, in this
case we need two edges for the parts of the path corresponding to the moduli
$p_{1}$ and $p_{j}$. Finally, we conclude that the path length is increased by
one if one edge for the part of the path corresponding to the modulus $p_{1}$
is needed and that is for $\alpha_{1}=1$. Also notice that these two edges can
reach the value $r(p_{1}^{\alpha_{1}})+r(p_{j}^{\alpha_{j}})$ if and only if
$\alpha_{j}=1$. If there are two primes $p_{j_{1}}>2$ and $p_{j_{2}}>2$ not
dividing $d_{1}$, for $t+1\leq j_{1},j_{2}\leq k$, it can be immediately seen
that there exist $y_{1}^{\prime},y_{1}^{\prime\prime}$ modulo $p_{j_{i}}$ such
that $p_{j_{i}}\nmid y_{1}^{\prime},y_{1}^{\prime\prime}$, $1\leq i\leq 2$ and
path length can not be increased. Thus we prove that the path length is
increased by one if and only if an arbitrary divisor is not divisible by
exactly two prime factors $p_{i}$ and $p_{j}$, where $1\leq i\leq t$, $t+1\leq
j\leq k$ and $\alpha_{i}=\alpha_{j}=1$. Now, if we take $l$ such that the
equation (16) has maximal number of summands and that is
$r(p_{1}^{\alpha_{1}}\cdots p_{t}^{\alpha_{t}})$, we obtain that the diameter
of the graph is equal to $r(n)$ for $n\in 2{\mathbb{N}}+1$. In this way, we
also prove that the diameter is smaller than $r(n)$ and $r(n)+1$, for $n\in
4{\mathbb{N}}$ and $4{\mathbb{N}}+2$, respectively if $p_{1}=2$. Therefore, in
the following we assume that $p_{1},\ldots,p_{t}\in 2{\mathbb{N}}+1$.

Suppose now that $n\in 2{\mathbb{N}}$. If $p_{j}=2$, similarly to the
discussion above we can conclude that there exist $s_{1},\ldots,s_{t}$ modulo
$p_{j}$ for $u_{j}>2$ and we do not need any additional edges for the path
from $0$ to $l$. Furthermore, if $u_{j}=1$, according to Lemma 3.3 it holds
that $y_{1}$ can be split into three summands
$y_{1}^{\prime}+y_{1}^{\prime\prime}+y_{1}^{\prime\prime\prime}$, $p_{j}\nmid
y_{1}^{\prime},y_{1}^{\prime\prime},y_{1}^{\prime\prime\prime}$. In this case
we need three edges for the parts of the path corresponding to the moduli
$p_{1}$ and $p_{j}$ and these three edges reach the value
$r(p_{1}^{\alpha_{1}})+r(p_{j}^{\alpha_{j}})+1$ if and only if
$\alpha_{1}=\alpha_{j}=1$. This proves that under the conditions given in the
part $ii)$ of the assertion the diameter of the graph attains $r(n)+1$.
Moreover, if $n\in 4{\mathbb{N}}$ then
$r(p_{1}^{\alpha_{1}})+r(p_{j}^{\alpha_{j}})+1>3$ and
$r(p_{1}^{\alpha_{1}})+r(p_{j}^{\alpha_{j}})=3$ if and only if $\alpha_{1}=1$.
Thus we conclude that under the conditions from the part $i)$ the diameter of
the graph attains $r(n)$, for $n\in 4{\mathbb{N}}$.

To prove the assertions $i)$ and $ii)$ completely, we need to prove that if
$p_{j}=2$ and $u_{j}=2$ the path from $0$ to $l$ can not be greater or equal
$r(n)+1$ for $n\in 4{\mathbb{N}}+2$ and $r(n)$ for $n\in 4{\mathbb{N}}$.
Indeed, according to Lemma 3.3 again, we need three edges
($y_{1}^{\prime},y_{1}^{\prime\prime}$ and $y_{2}$) for the parts of the path
corresponding to the moduli $p_{1}$, $p_{2}$ and $p_{j}$ and since
$r(p_{1}^{\alpha_{1}})+r(p_{2}^{\alpha_{2}})+r(p_{j}^{\alpha_{j}})$ is always
greater or equal to three, it can be seen that
$r(p_{1}^{\alpha_{1}})+r(p_{2}^{\alpha_{2}})+r(p_{j}^{\alpha_{j}})+1>3$ for
$n\in 4{\mathbb{N}}+2$ and
$r(p_{1}^{\alpha_{1}})+r(p_{2}^{\alpha_{2}})+r(p_{j}^{\alpha_{j}})>3$ for
$n\in 4{\mathbb{N}}$.

Now, we are going to prove the parts $iii)$ and $iv)$ of the assertion. First,
suppose that there exist $p_{1},\ldots,p_{t}$ such that
$\alpha_{1},\ldots,\alpha_{t}>1$. According to the proof of Lemma 3.1 the path
from $0$ to $l$, for certain values $0\leq l\leq n-1$ and $d_{1},\ldots,d_{t}$
that satisfy $i)$ from Theorem 3.2, can be written in the form

$\displaystyle
d_{1}(y_{1}^{\prime}+y_{1}^{\prime\prime})+d_{2}(y_{2}^{\prime}+y_{2}^{\prime\prime})+\cdots+d_{t}(y_{t}^{\prime}+y_{t}^{\prime\prime})\equiv
l\pmod{p_{j}^{\alpha_{j}}},$

for $1\leq j\leq t$. Following the above deduction we conclude that for any
$p_{j}>2$, $t+1\leq j\leq k$ such that $p_{j}\nmid d_{s}$, $1\leq s\leq t$, we
can find $y_{s}^{\prime}$ and $y_{s}^{\prime\prime}$ modulo $p_{j}$ such that
$p_{j}\nmid y_{s}^{\prime},y_{s}^{\prime\prime}$. Similarly, if $p_{j}=2$ and
$p_{j}\nmid d_{s}$ for some $1\leq s\leq t$, then we can not find
$y_{s}^{\prime}$ and $y_{s}^{\prime\prime}$ modulo $p_{j}$ such that
$p_{j}\nmid y_{s}^{\prime},y_{s}^{\prime\prime}$. Therefore, we replace those
two edges $y_{s}^{\prime}+y_{s}^{\prime\prime}$ with three edges
$y_{s}^{\prime}+y_{s}^{\prime\prime}+y_{s}^{\prime\prime\prime}$ modulo
$p_{j}$ such that $p_{j}\nmid
y_{s}^{\prime},y_{s}^{\prime\prime},y_{s}^{\prime\prime\prime}$. So, if $n\in
2{\mathbb{N}}+1$ we can not find $l$ such that we need more than $2t$ summands
and for $n\in 2{\mathbb{N}}$ it is possible by increasing the number of the
summands by one.

Finally, if there are no $p_{1},\ldots,p_{t}$ such that
$\alpha_{1},\ldots,\alpha_{t}>1$ then there exists a divisor $d_{i}$ such that
$p_{u}\nmid d_{i}\Rightarrow\alpha_{u}=1$ for $1\leq u\leq k$. On the other
hand, since there exists at most one prime factor $p_{i}$ of $n$ such that
$\alpha_{i}=1$, we see that $p_{i}$ is the only factor dividing $d_{i}$ (if it
exists) and for all other prime factors it holds that $p_{u}\mid d_{i}$,
$1\leq u\neq i\leq k$, where $\alpha_{u}>1$. According to the proof of Lemma
3.1 the path from $0$ to $l$, for certain values $0\leq l\leq n-1$ can be
written in the form

$\displaystyle
d_{1}(y_{1}^{\prime}+y_{1}^{\prime\prime})+\cdots+d_{i}y_{i}+\cdots+d_{t}(y_{t}^{\prime}+y_{t}^{\prime\prime})\equiv
l\pmod{p_{j}^{\alpha_{j}}},$

for $1\leq j\leq t$ (the maximal number of summands is equal to $2t-1$
considering to the moduli $p_{1},\ldots,p_{t}$). As we have seen above for any
$p_{j}>2$, $t+1\leq j\leq k$ such that $p_{j}\nmid d_{s}$, $1\leq s\neq i\leq
t$ we can not increase the number of the summands and for $p_{j}=2$, $t+1\leq
j\leq k$ such that $p_{j}\nmid d_{s}$, $1\leq s\neq i\leq t$ we can increase
the number of the summands by one, but we can not reach the value $2t+1$.
$\square$

###### Remark 3.9

According to $i)$ and $ii)$ of the assertion we may notice that there is a
subset $\\{d_{f(t+1)},\ldots,d_{f(k)}\\}$ of the divisor set $D$ such that
there exist exactly two divisors $p_{i},p_{f(i)}\nmid d_{f(i)}$ and
$p_{i},p_{f(i)}\|n$, for $t+1\leq i\leq k$. Now, if $s(n)=|\\{i\
|\alpha_{i}=1,\ 1\leq i\leq k\\}|$ we conclude that $2(k-t)\leq s(n)$ and
therefore $k-\lfloor{\frac{s(n)}{2}}\rfloor\leq t<k$. So, the assertions $i)$
and $ii)$ hold for the divisor set with cardinality
$k-\lfloor{\frac{s(n)}{2}}\rfloor\leq t<k$ and for the cardinalities
$t<k-\lfloor{\frac{s(n)}{2}}\rfloor$ it can be very easily seen that
$diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{t}))\leq 2t$ if $n\in 2{\mathbb{N}}+1$
and $diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{t}))\leq 2t+1$ if $n\in
2{\mathbb{N}}$ (the reasoning is analogous to that in the parts $iii)$ and
$iv)$).

Notice that we can neither increase nor find new classes of graphs whose
diameters attain $r(n)$ or $r(n)+1$ using Theorems 3.4 and 3.8, where $n$ is
the order of the integral circulant graph. Indeed, if $n^{\prime}\in
2{\mathbb{N}}+1$ then the diameter of $\mathrm{ICG}_{n\cdot
n^{\prime}}(d_{1},\ldots,d_{t})$ remains the same and the potential upper
bound $r(n\cdot n^{\prime})$ can not be attained as $r(n\cdot
n^{\prime})>r(n)$. Furthermore, if $n^{\prime}\in 2{\mathbb{N}}$ then $n\in
2{\mathbb{N}}+1$ and

$diam(\mathrm{ICG}_{n\cdot
n^{\prime}}(d_{1},\ldots,d_{t}))=diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{t}))+1\leq
r(n)+1\leq r(n\cdot n^{\prime}).$

It is easy to see that if $diam(\mathrm{ICG}_{n\cdot
n^{\prime}}(d_{1},\ldots,d_{t}))=r(n\cdot n^{\prime})$ then $n^{\prime}=2$ and
therefore $n\cdot n^{\prime}\in 4{\mathbb{N}}+2$. However, since $n\cdot
n^{\prime}\in 4{\mathbb{N}}+2$, according to the part $ii)$ of Theorem 3.8
there exist $d_{1}^{\prime},\ldots,d_{t}^{\prime}$ such that
$diam(\mathrm{ICG}_{n\cdot n^{\prime}}(d_{1},\ldots,d_{t}))$ is equal to
$r(n\cdot n^{\prime})+1$.

Now, if $n\cdot n^{\prime}$ is divisible by at most one prime factor then new
classes of graphs that attain the bounds $2t$ and $2t+1$ can be found in the
cases $n\cdot n^{\prime}\in 2{\mathbb{N}}+1$ and $n\cdot n^{\prime}\in
2{\mathbb{N}}$, respectively.

On the other hand, if $n$ has at most one divisor $p_{i}\|n$ and $n\cdot
n^{\prime}$ is divisible by at least two divisors $p_{i}$ and $p_{j}$ such
that $p_{i},p_{j}\|n\cdot n^{\prime}$ and then we have for $n\in
2{\mathbb{N}}+1$, $n^{\prime}\in 2{\mathbb{N}}$ and
$D=\\{d_{1},\ldots,d_{t}\\}$

$diam(\mathrm{ICG}_{n\cdot n^{\prime}}(D))=diam(\mathrm{ICG}_{n}(D))+1\leq
2t+1\leq 2(k-1)+1\leq r(n)<r(n\cdot n^{\prime}).$

Similarly, if $n^{\prime}\in 2{\mathbb{N}}+1$ and $n\in 2{\mathbb{N}}$ we can
similarly conclude that
$diam(\mathrm{ICG}_{n\cdot
n^{\prime}}(d_{1},\ldots,d_{t}))=diam(\mathrm{ICG}_{n}(d_{1},\ldots,d_{t}))\leq
2t+1<r(n\cdot n^{\prime}).$ Since $n\cdot n^{\prime}$ is divisible by at least
two divisors $p_{i}$ and $p_{j}$ such that $\alpha_{i}=\alpha_{j}=1$,
according to $i)$ and $ii)$ of the above assertion there exists a set of the
divisors $d_{1}^{\prime},\ldots,d_{t}^{\prime}$ such that
$diam(\mathrm{ICG}_{n\cdot
n^{\prime}}(d_{1}^{\prime},\ldots,d_{t}^{\prime}))\geq r(n\cdot n^{\prime})$
and thus we can neither increase nor find new classes of graphs whose
diameters attain maximal values using Theorem 3.4.

Finally, we give the formula for the maximal diameter of an integral circulant
graph of a given order $n$ and the set of divisors $D$ with cardinality $t$

$\displaystyle\max(diam(\mathrm{ICG}_{n}(D)))=\left\\{\begin{array}[]{rl}r(n),&t=k\\\
r(n)+1,&n\in 4{\mathbb{N}}+2,\ s(n)\geq 2,\
k-\lfloor{\frac{s(n)}{2}}\rfloor\leq t<k\\\ r(n),&n\not\in 4{\mathbb{N}}+2,\
s(n)\geq 2,\ k-\lfloor{\frac{s(n)}{2}}\rfloor\leq t<k\\\ 2t+1,&n\in
2{\mathbb{N}},\ s(n)\geq 2,\ t<k-\lfloor{\frac{s(n)}{2}}\rfloor\\\ 2t,&n\in
2{\mathbb{N}}+1,\ s(n)\geq 2,\ t<k-\lfloor{\frac{s(n)}{2}}\rfloor\\\
2t+1,&n\in 2{\mathbb{N}},\ s(n)\leq 1,\ t<k\\\ 2t,&n\in 2{\mathbb{N}}+1,\
s(n)\leq 1,\ t<k.\\\ \end{array}\right.$ (25)

In some real-world applications such as construction of a quantum
communication network with prescribe order and the largest possible diameter
it is good to know the maximal diameter of integral circulant graphs of a
given order $n$.

It is sufficient to check if there exists some $\mathrm{ICG}_{n}(D)$ whose
maximal diameter is $2|D|+1$ or $2|D|$ and it is greater than $r(n)+1$ or
$r(n)$. From (25) it follows that diameter of $\mathrm{ICG}_{n}(D)$ can attain
$2|D|+1$ or $2|D|$, if $s(n)\leq 1$ or $s(n)\geq 2$ and
$t<k-\lfloor{\frac{s(n)}{2}}\rfloor$. Now, suppose first that $s(n)\leq 1$.
The following chain of inequalities holds

$diam(\mathrm{ICG}_{n}(D))\leq 2|D|+1\leq 2(k-1)+1\leq
2k-s(n)=s(n)+2(k-s(n))=r(n),$

and therefore we see that in this case can not find a class of graphs with
diameter greater than $r(n)$.

Now, if $s(n)\geq 2$ and $t<k-\lfloor{\frac{s(n)}{2}}\rfloor$ then we have

$diam(\mathrm{ICG}_{n}(D))\leq 2|D|+1\leq
2(k-\lfloor{\frac{s(n)}{2}}\rfloor-1)+1=2k-(s(n)-1)-1=r(n),$

and therefore we conclude that the maximal diameter is equal to $r(n)$ if
$n\not\in 4{\mathbb{N}}+2$ and $r(n)+1$ if $n\in 4{\mathbb{N}}+2$.

##  4 Conclusion

In this paper we find the maximal diameter of all integral circulant graphs of
a given order $n$. We also calculate the maximal diameter of integral
circulant graphs of a given order $n$ and cardinality of the divisor set
$t\leq k$. Moreover, we characterize all $\mathrm{ICG}_{n}(D)$ such that the
maximal diameter is attained. Generally, the proofs presented in this paper
are based on the connections between number and graph theory and fall into a
good many of distinct cases.

We have already mentioned that the maximal diameter of some class of graphs of
a given order plays an important role if that class is used for modeling a
quantum network that allows quantum dynamics, having in mind applications like
perfect state transfer. Therefore, we conclude with a partial result about
maximal diameter of integral circulant graphs having perfect state transfer.
We actually prove that diameter of $\mathrm{ICG}_{n}(D)$ having perfect state
transfer such that $|D|\leq k$ can not attain the value $r(n)$. In a recent
paper [1], complete characterization of integral circulant graph having
perfect state transfer was given and it was shown that $\mathrm{ICG}_{n}(D)$
has perfect state transfer if and only if $n\in 4{\mathbb{N}}$ and
$D=\widetilde{D_{3}}\cup D_{2}\cup 2D_{2}\cup 4D_{2}\cup\\{n/2^{a}\\}$, where
$\widetilde{D_{3}}=\\{d\in D\ |\ n/d\in 8{\mathbb{N}}\\}$, $D_{2}=\\{d\in D\
|\ n/d\in 8{\mathbb{N}}+4\\}\setminus\\{n/4\\}$ and $a\in\\{1,2\\}$. Now,
suppose that there exists $\mathrm{ICG}_{n}(D)$ of a given order $n$ allowing
perfect state transfer that attains maximal diameter. Since
$\mathrm{ICG}_{n}(D)$ attains maximal diameter we conclude that $D$ satisfies
(2) and (3) and therefore there exists $p_{i}$ not dividing $n/2$, if $n/2\in
D$. This means that $p_{i}=2$ and hence $n\in 4{\mathbb{N}}+2$ implying that
$\mathrm{ICG}_{n}(D)$ does not permit perfect state transfer. Furthermore, if
$n/4\in D$ then in the similar way we conclude that $n\in 8{\mathbb{N}}+4$. On
the other hand, for every $d_{i}\in D_{2}$ it holds that $2d_{i},4d_{i}\in D$
and the set of prime factors dividing $2d_{i}$ and $4d_{i}$ are the same,
which is a contradiction according to (2) and (3). The above discussion
suggests that a possible challenging direction in future research would be
finding the maximal diameter in the class of integral circulant graphs having
perfect state transfer.

On the other hand, we may notice that we can not improve the lower bound in
the inequality (1) for prescribed $n$ and any prescribed cardinality of the
divisor set $D$. Indeed, according to Theorem 9 from [13] we observe that
$\mathrm{ICG}_{n}(1)=2$ if and only if $n$ is a power of $2$ or $n$ is odd (in
both of the cases $n$ is not prime). This implies that
$diam(\mathrm{ICG}_{n}(1,d_{2},\ldots,d_{t}))=2$, for any $t$ and the
mentioned values of $n$ (as long as $\\{1,d_{2},\ldots,d_{t}\\}\neq D_{n}$ ).

In the remaining case, for $n=2^{\alpha_{1}}m$, where $m>1$ is odd and
$\alpha\geq 1$, we can prove that
$diam(\mathrm{ICG}_{n}(1,2^{\alpha_{1}}))=2$. Indeed, for every $0\leq l\leq
n-1$, such that $l$ is even we will prove the existence of $l$ in the form
$s_{1}+s_{2}\equiv l\pmod{n}$ such that $\gcd(s_{1},n)=1$, $\gcd(s_{2},n)=1$.
Now, let $p_{i}$ be an arbitrary divisor of $n$ such that
$S_{p_{i}}(n)=\alpha_{i}$. By solving the above congruence equation system
modulo $p_{i}^{\alpha_{i}}$ we get that $s_{1}\equiv l-s_{2}\not\equiv
p_{i}u\pmod{p_{i}^{\alpha_{i}}}$ and $s_{2}\not\equiv 0\pmod{p_{i}}$ (which is
equivalent to $s_{2}\not\equiv p_{i}v\pmod{p_{i}^{\alpha_{i}}}$), for $0\leq
u,v<p_{i}^{\alpha_{i}-1}-1$. Therefore, we obtain
$s_{2}\not\equiv\\{p_{i}v,l-p_{i}u\\}\pmod{p_{i}^{\alpha_{i}}}$ and it can be
concluded that the maximal number of values that $s_{2}$ modulo
$p_{i}^{\alpha_{i}}$ can not take is equal to $2p_{i}^{\alpha_{i}-1}$. This
number is less than the number of residues modulo $p_{i}^{\alpha_{i}}$ any
$p_{i}$ (as $l$ is even), so this system has a solution in this case.

Now, suppose that $l\in 2{\mathbb{N}}+1$. We find $s_{1}$ and $s_{2}$ such
that $s_{1}+s_{2}\equiv l\pmod{n}$, $\gcd(s_{1},n)=1$ and
$\gcd(s_{2},n)=2^{\alpha_{1}}$. Similarly to the previous discussion, we can
conclude that the above conditions can be reduced to the following system
$s_{2}\not\equiv\\{p_{i}v,l-p_{i}u\\}\pmod{p_{i}^{\alpha_{i}}}$, for $2\leq
i\leq k$ and $s_{2}\equiv 0\pmod{2^{\alpha_{1}}}$. As $p_{i}>2$ this system
has a solution. We finally conclude that
$diam(\mathrm{ICG}_{n}(1,2^{\alpha_{1}},d_{3},\ldots,d_{t}))=2$, for any $t$
and the mentioned values of $n$ (as long as
$\\{1,2^{\alpha_{1}},d_{3},\ldots,d_{t}\\}\neq D_{n}$).

## Declaration of competing interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## Data availability

No data was used for the research described in the article.

## Acknowledgments

Authors gratefully acknowledge support from the Research Project of the
Ministry of Education, Science and Technological Development of the Republic
of Serbia (number 451-03-47/2023-01/ 200124).

## References

  * [1] M. Bašić, Characterization of circulant graphs having perfect state transfer, Quantum Information Processing 12 (2013) 345–364.
  * [2] M. Bašić, Which weighted circulant networks have perfect state transfer?, Information Sciences 257 (2014) 193–209.
  * [3] M. Bašić, A. Ilić, On the clique number of integral circulant graphs, Applied Mathematics Letters 22 (2009) 1406–1411.
  * [4] M. Bašić, A. Ilić, On the automorphism group of integral circulant graphs, The Electronic Journal of Combinatorics 18 (2011) #P68.
  * [5] P. Berrizbeitia, R. E. Giudic, On cycles in the sequence of unitary Cayley graphs, Discrete Mathematics 282 (2004) 239–243.
  * [6] M. Christandl, N. Datta, A. Ekert, A.J. Landahl, Perfect state transfer in quantum spin networks, Physical Review Letters 92 (2004) 187902 [quant-ph/0309131].
  * [7] E. Fuchs, Longest induced cycles in circulant graphs, The Electronic Journal of Combinatorics 12 (2005) 1–12.
  * [8] G.H. Hardy, E.M. Wright, An introduction to the Theory of Numbers, 5th ed, Clarendon Press, Oxford University Press, New York, 1979.
  * [9] F. K. Hwang, A survey on multi-loop networks, Theoretical Computer Science 299 (2003) 107–121.
  * [10] A. Ilić, Distance spectra and distance energy of integral circulant graphs, Linear Algebra and its Applications 433 (2010) 1005–1014.
  * [11] A. Ilić, M. Bašić, On the chromatic number of integral circulant graphs, Computers & Mathematics with Applications 60 (2010) 144–150.
  * [12] A. Ilić, M. Bašić, New results on the energy of integral circulant graphs, Applied Mathematics and Computation 218 (2011) 3470–3482.
  * [13] W. Klotz, T. Sander, Some properties of unitary Cayley graphs, The Electronic Journal of Combinatorics 14 (2007) #R45.
  * [14] J.H. Park, K.Y. Chwa, Recursive circulants and their embeddings among hypercubes, Theoretical Computer Science 244 (2000) 35–62.
  * [15] H. N. Ramaswamy, C. R. Veena, On the Energy of Unitary Cayley Graphs, The Electronic Journal of Combinatorics 16 (2007) #N24.
  * [16] N. Saxena, S. Severini, I. Shparlinski, Parameters of integral circulant graphs and periodic quantum dynamics, International Journal of Quantum Information 5 (2007) 417–430.
  * [17] J.W. Sander, T. Sander, The maximal energy of classes of integral circulant graphs, Discrete Applied Mathematics 160 (2012) 2015–2029.
  * [18] W. So, Integral circulant graphs, Discrete Mathematics 306 (2006) 153–158.