Normal matrices subordinate to a graph

Recently, it has been noticed that if the graph of an n-by-n complex matrix is a tree, then normality of the matrix is equivalent to three conditions, associated with the edges of the graph, that are much simpler than checking the standard definition of normality. Here, we characterize the precise class of graphs (much more general than trees), for which the three conditions are equivalent to normality, under a slight (and necessary) regularity condition. The graphs are those that are both triangle and 4-cycle free. For triangle-free graphs, normality implies absolute symmetry, under the same regularity condition. The results permit strong applications to real matrices, and to the notions of “principal normality”, and “essentially Hermitian”.