Maximal diameter of integral circulant graphs
share
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 ICG_n (D) has the vertex set Z_n = {0, 1, 2, …, n - 1} and vertices a and b are adjacent if (a-b,n)∈ D, where D ⊆{d : d | n, 1≤ d<n}. Motivated by the result on the upper bound of the diameter of 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 ICG_n(D) of a given order n with its prime factorization p_1^α_1⋯ p_k^α_k, is equal to r(n) or r(n)+1, where r(n)=k + |{ i | α_i> 1, 1≤ i≤ k }|, depending on whether n∉4N+2 or not, respectively. Furthermore, we show that, for a given order n, a divisor set D with |D|≤ 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≤ 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 that paper.
READ FULL TEXT