Maximal Diameter on a Class of Circulant Graphs

Abstract

Integral circulant graphs are proposed as models for quantum spin networks. Specifically, it is important to know how far information can potentially be transferred between nodes of the quantum networks modeled 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\le 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], which is equal to $2|D|+1$, 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}$ and $|D|=k$, is equal to $k + |\{ i \ | \alpha _i> 1,\ 1\le i\le k \}|$. This way we further improve the upper bound of Saxena, Severini and Shparlinski. Moreover, we characterize all such extremal graphs. We also show that the upper bound is attainable for integral circulant graphs $\mathrm {ICG}_n(D)$ such that $|D|\le k$.

This work was supported by Research Grant 174013 of Serbian Ministry of Science and Technological Development.