Periodic graphs

Chris Godsil

The electronic journal of combinatorics, Tome 18 (2011) no. 1

Résumé

Let $X$ be a graph on $n$ vertices with adjacency matrix $A$ and let $H(t)$ denote the matrix-valued function $\exp(iAt)$. If $u$ and $v$ are distinct vertices in $X$, we say perfect state transfer from $u$ to $v$ occurs if there is a time $\tau$ such that $|H(\tau)_{u,v}|=1$. If $u\in V(X)$ and there is a time $\sigma$ such that $|H(\sigma)_{u,u}|=1$, we say $X$ is periodic at $u$ with period $\sigma$. It is not difficult to show that if the ratio of distinct non-zero eigenvalues of $X$ is always rational, then $X$ is periodic. We show that the converse holds, from which it follows that a regular graph is periodic if and only if its eigenvalues are distinct. For a class of graphs $X$ including all vertex-transitive graphs we prove that, if perfect state transfer occurs at time $\tau$, then $H(\tau)$ is a scalar multiple of a permutation matrix of order two with no fixed points. Using certain Hadamard matrices, we construct a new infinite family of graphs on which perfect state transfer occurs.

Détail

DOI : 10.37236/510

Classification : 05C50, 81P68