1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ That's not the definition of strong connectivity. $\endgroup$ – Brendan McKay Oct 25 '15 at 22:03
  • $\begingroup$ 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$. $\endgroup$ – MarcosDNMaia Oct 26 '15 at 9:07
6
$\begingroup$

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

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.