# Strongly connected graph and the eigenvalues of the laplacian matrix

Given a directed graph $G$, consider that $G$ is strongly connected iff every vertex $i$ in $G$ has inner degree $k_i\geq 1$. Reformulation of this definition: $G$ is strongly connected iff for any two vertices $i,j$ in $G$ there is at least one directed path from $i$ to $j$ and from $j$ to $i$.

The laplacian matrix $L =[l_{ij}]$ $i,j=1,\cdots,n$ is such that $l_{ij}=-1$ if there is a link from $j$ to $i$; $l_{ij} = k_i$ if $j=i$ and $l_{ij}=0$ otherwise.

The conjecture is: Given a directed graph $G$, the eigenvalues of the laplacian matrix $L$ of $G$ are all simple iff $G$ is strongly connected.

Do you know if this "conjecture" is already a well-known result? Any suggestions of references where I can find the proof of this result? In the case its not valid, do you know a counter-example?

• That's not the definition of strong connectivity. – Brendan McKay Oct 25 '15 at 22:03
• Brendan McKay, you are right. The definition in terms of the inner degree is not good. I think the right definition would be: Given any two vertices $i,j$ in $G$ there is always a directed path from $i$ to $j$ and from $j$ to $i$. – MarcosDNMaia Oct 26 '15 at 9:07

I think your conjecture does not fly. Indeed, consider a "Paley tournament": let $p=4k-1$ e a prime, and define a digraph with the set of vertices 0,1,..,$p-1$, so that $i$ is connected to $j$ whenever $i-j$ is a non-0 square modulo $p$. It has in-degree (and out-degree) $(p-1)/2$ for any vertex. Such a digraph has only 3 distinct eigenvalues, and thus it will only have 3 distinct laplacian eigenvalues.

(In particular, this construction gives a counterexample on 7 vertices).

   [ 3 -1 -1  0 -1  0  0]
[ 0  3 -1 -1  0 -1  0]
[ 0  0  3 -1 -1  0 -1]
[-1  0  0  3 -1 -1  0]
[ 0 -1  0  0  3 -1 -1]
[-1  0 -1  0  0  3 -1]
[-1 -1  0 -1  0  0  3]
sage: mm.characteristic_polynomial().factor()
x * (x^2 - 7*x + 14)^3

• Can you paste here the Laplacian matrix for the example you gave? – MarcosDNMaia Oct 26 '15 at 21:12
• sure, see the edited answer – Dima Pasechnik Oct 26 '15 at 21:28
• so you see, the laplacian has one eigenvalue 0, and 2 conjugate complex eignevalues, each with multiplicity 3. – Dima Pasechnik Oct 26 '15 at 21:30
• That's it! Thanks for your response. – MarcosDNMaia Oct 26 '15 at 21:42