Which graphs do have invertible adjacency matrices?

I would like to know if there is any class of graphs for which the adjacency matrices are invertible. At this moment I am aware of only the class of graphs $n K_2$ which is the disjoint union of $n$ number of $K_2$ matrices where the adjacency matrices are self-inverse.

Are there any other classes?

• – Bach Nov 12 '15 at 10:43

Given a permutation $\pi$ of a finite set $V$, form its cycle graph $G$ as follows: the vertex set is $V$ and the edges are pairs $(v,w)$ for which $\pi(v)=w$. (This is a simple directed graph.) The adjacency matrix will in fact be the permutation matrix corresponding to $\pi$, which is invertible.
We can also form graphs with loops whose adjacency matrices are upper triangular: take the vertex set $\{1,\cdots,n\}$ and adjoin edges $i\to j$ as one wishes but only when $i\le j$ (and of course make sure every vertex has at least one loop).
• @OmarShehab Yes, for instance $[\begin{smallmatrix}2 & 1 \\ 1 & 1 \end{smallmatrix}]$. A complete classification would seem to characterize all invertible matrices with nonnegative integer entries, and I am not aware of such a characterization (although I haven't looked). My guess is it'd be unlikely there is a strictly graph-theoretic characterization of these graphs, but you'd have to ask a graph theorist to be more confident. – whacka Oct 7 '15 at 17:39