Which directed graphs have a normal adjacency matrix? I am working on a problem in matrix analysis and I am looking for certain types of normal matrices.  I suspect that these "special" normal matrices arise as adjacency matrices of certain graphs.  My question, then, is what types of graphs have normal adjacency matrices?  
 A: I think there are problems with the accepted answer.
As there, a directed graph is balanced if the in-degree of each vertex
is equal to its out-degree. A directed graph with adjacency matrix $A$ is balanced
if and only if the diagonal entries of $AA^T-A^TA$ are zero, and so normal
directed graphs are balanced. The cited article in the second paragraph above refers
to a result of Wu and Chua, proving that if the Laplacian of a directed graph is
normal then the directed graph is balanced. (In fact the obvious variant of the proof for
adjacency matrices works.)
On five vertices, my sage calculations found 111 balanced directed graphs from a 
total of 9608. Of these 111, I found that 49 were normal and 47 were Laplacian
normal. So balanced does not imply normal.
All Laplacian normals on five vertices were adjacency normal. With obvious notation, my calculations give that if $D-A$ is normal then
$$
    A^TA-AA^T = D(A-A^T) - (A-A^T)D.
$$
I cannot get from here to the conclusion that Laplacian normal implies normal,
but this might just be stupidity on my part.
Edit: Krystal Guo went through the directed graphs on six vertices and found four
directed graphs that are Laplacian normal but not normal. The first has adjacency matrix
$$
\left(\begin{array}{rrrrrr}
0 & 1 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 1 & 1 \\
1 & 1 & 1 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 & 0
\end{array}\right)
$$
A: This turns out to be more complicated that I first thought it'd be. Apparently the graphs you are asking about are usually called normal digraphs and a proper characterization does not seem to be known. This recent paper treats characterization in the special case of Cayley digraphs and also refers to previous work on other cases (alas, almost all of it is in not-immediately-accessible-online places).
There is case, I think, that is easy to work out: graph where in-degrees equals\ the out-degrees. The write-up here indicates (once again, based on a 2005 paper I can't access here and now) that such graphs (called balanced) have a normal Laplacian matrix, which is easily seen to be equivalent to having a normal adjacency matrix.
A: k-regular directed ring graphs, they have circulant adjacency, are normal because of their rotational symmetry.
