5
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Are there any other classes? $\endgroup$ – Omar Shehab Oct 7 '15 at 17:30
  • 1
    $\begingroup$ @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. $\endgroup$ – whacka Oct 7 '15 at 17:39
  • $\begingroup$ Just asked a supplementary question at cstheory.stackexchange.com/questions/32743/… $\endgroup$ – Omar Shehab Oct 7 '15 at 17:41
  • 1
    $\begingroup$ @OmarShehab I don't know what the term in graph theory would be or if there is one (it would seem the term "cycle graph" that graph-theorists use is a more restrictive notation), but I'm almost certain I have seen the term "cycle graph of a permutation" used for this construction in the theory of combinatorial species (a mixture of combinatorics, permutation group theory and category theory). $\endgroup$ – whacka Oct 7 '15 at 23:36
  • 1
    $\begingroup$ The cycle graph of a permutation, specifically, is what I defined in my answer, yes. $\endgroup$ – whacka Oct 8 '15 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.