Skip to main content
added 175 characters in body
Source Link

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?

Given a directed graph $G$, consider that $G$ is strongly connected iff every vertex $i$ in $G$ has inner degree $k_i\geq 1$. 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?

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?

Added top-level tag.
Link
Stefan Kohl
  • 19.6k
  • 21
  • 75
  • 137
Source Link

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$. 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?