Maximal diameter of integral circulant graphs
Preprint
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 $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 1,\ 1\leq i\leq k \}|$, depending on whether $n\not\in 4N+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 that paper.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Which weighted circulant networks have perfect state transfer?Information Sciences, 2014
- The maximal energy of classes of integral circulant graphsDiscrete Applied Mathematics, 2012
- New results on the energy of integral circulant graphsApplied Mathematics and Computation, 2011
- Distance spectra and distance energy of integral circulant graphsLinear Algebra and its Applications, 2010
- On the chromatic number of integral circulant graphsComputers & Mathematics with Applications, 2010
- On the clique number of integral circulant graphsApplied Mathematics Letters, 2009
- PARAMETERS OF INTEGRAL CIRCULANT GRAPHS AND PERIODIC QUANTUM DYNAMICSInternational Journal of Quantum Information, 2007
- Integral circulant graphsDiscrete Mathematics, 2006
- Perfect State Transfer in Quantum Spin NetworksPhysical Review Letters, 2004
- Recursive circulants and their embeddings among hypercubesTheoretical Computer Science, 2000