2
$\begingroup$

What are the necessary and sufficient conditions for a PSD matrix $S$, to be a graph Laplacian? I know $S1=0$ is required. But clearly a real zero sum PSD matrix is not necessarily a graph Laplacian.

Second question arises after seeing the useful responses here: What are the conditions for a PSD matrix to be a weighted graph Laplacian?

  • 0
    Sorry, I meant positive semi-definite matrix.2012-10-05

1 Answers 1

1

Assuming you mean positive-semidefinite for PSD, a graph laplacian has degrees of the graph on the diagonal, so we must have the Erdos Gallai condition for the degrees (that's necessary and sufficient for existance of the graph with given degree sequence). Other than that, the other entries must be either -1 or 0 with row and column sumbs equal to 0.

  • 0
    @Alex: For your example, the row-sums are not zero. What I want to claim is that any PSD matrix $S$, where $S_{ij}\in {-1, 0}$ and $S1= 0$ is a Laplacian matrix regardless of Erdos Gallai condition. However, I think some of my conditions are redundant2012-10-06