Skip to main content
added more detail
Source Link
Chris Godsil
  • 12.1k
  • 5
  • 37
  • 61

These are usually known as the Laplacian, the normalized Laplacian and the unsigned Laplaian. All three are positive semidefinite. If the graph is regular, they all provide the same information.

If the graph is not regular they are, in general, independent. The normalized Laplacian is the right tool for the analysis of random walks. The spectral information provided by the unsigned Laplacian is equivalent to what you get from the spectrum of the line graph of the original graph.

To expand on the last comment: if $B$ is the vertex-edge incidence matrix, then $BB^T$ is the unsigned Laplacian and $B^TB=2I+A(L(G))$. This appears for example on page 16 of the first edition of Cvetkovic et al "Spectra of Graphs", but it is older. (I know I did not learn it from there.) Note that it follows that $BB^T$ and $B^TB$ have the same non-zero eigenvalues with the same multiplicities.

These are usually known as the Laplacian, the normalized Laplacian and the unsigned Laplaian. All three are positive semidefinite. If the graph is regular, they all provide the same information.

If the graph is not regular they are, in general, independent. The normalized Laplacian is the right tool for the analysis of random walks. The spectral information provided by the unsigned Laplacian is equivalent to what you get from the spectrum of the line graph of the original graph.

These are usually known as the Laplacian, the normalized Laplacian and the unsigned Laplaian. All three are positive semidefinite. If the graph is regular, they all provide the same information.

If the graph is not regular they are, in general, independent. The normalized Laplacian is the right tool for the analysis of random walks. The spectral information provided by the unsigned Laplacian is equivalent to what you get from the spectrum of the line graph of the original graph.

To expand on the last comment: if $B$ is the vertex-edge incidence matrix, then $BB^T$ is the unsigned Laplacian and $B^TB=2I+A(L(G))$. This appears for example on page 16 of the first edition of Cvetkovic et al "Spectra of Graphs", but it is older. (I know I did not learn it from there.) Note that it follows that $BB^T$ and $B^TB$ have the same non-zero eigenvalues with the same multiplicities.

Source Link
Chris Godsil
  • 12.1k
  • 5
  • 37
  • 61

These are usually known as the Laplacian, the normalized Laplacian and the unsigned Laplaian. All three are positive semidefinite. If the graph is regular, they all provide the same information.

If the graph is not regular they are, in general, independent. The normalized Laplacian is the right tool for the analysis of random walks. The spectral information provided by the unsigned Laplacian is equivalent to what you get from the spectrum of the line graph of the original graph.