Let $ζ_m$ ($m \ge 2$) be an $m$th primitive root of unity and $A$ a nonzero ideal of $ℤ[ζ_m]$. We define the $m$th cyclotomic graph $G_{m}(A)$ to be the Cayley graph on the additive group of $ℤ[ζ_m]/A$ such that $α + A, β + A 𝟄 ℤ[ζ_m]/A$ are adjacent if and only if $(α-β) + A = ζ_m^i + A$ or $-ζ_m^i + A$ for some $i$. Motivated by constructions of perfect codes as well as interconnection networks efficient for information transmission, in this paper we study cyclotomic graphs and their connections with two families of Frobenius circulant graphs. We also study the second kind cyclotomic graph $G^*_{m}(A)$, which is defined in the same way as $G_{m}(A)$ but with $i$ ranging from $0$ to $ϕ(m)-1$. We give a necessary and sufficient condition for $D/A$ to be a perfect $t$-error-correcting code in $G^*_{m}(A)$ and a necessary condition for $D/A$ to be such a code in $G_{m}(A)$, where $D$ is an ideal of $ℤ[ζ_m]$ containing $A$ and $t \ge 1$ is an integer. In particular, in the case $m = 3, 4$ we obtain necessary conditions for $(β)/(α)$ to be a perfect $t$-error-correcting code in the Eisenstein-Jacobi or Gaussian network $G_m((α))$, where $0 \ne α, β 𝟄 ℤ[ζ_m]$ with $β$ dividing $α$. In the literature such a condition was known to be sufficient when $m=4$, and sufficient when $m=3$ under an additional condition. We classify first kind Frobenius circulants of valency $2p$ or $2p^2$, where $p$ is a prime, and prove that such circulants of valency $2p$ are $p$th cyclotomic graphs. ; Comment: A few mistakes in the previous version have been corrected by the author