4
$\begingroup$

Given an undirected graph $G$, and let $V$ denote its set of vertices and $E$ its set of edges. Suppose that there are no edges connecting the same vertex, and no more than one edge connecting any pair of vertices.

The adjacency matrix is \begin{equation} a_{ij} = \begin{cases} 1 & If \, (i,j) \in E \\ 0 & \textrm{Otherwise} \end{cases}, \end{equation} and the Laplacian is $L = \delta_{ij} \sum_{k} a_{ik} - a_{ij}$.

It is known that the number of connected components of $G$ is equal to the multiplicity of the zero eigenvalue of $L$.

Is this result true also for weighted undirected graphs, where \begin{equation} a_{ij} = \begin{cases} w_{ij} & If \, (i,j) \in E \\ 0 & \textrm{Otherwise} \end{cases}, \end{equation} with $w_{ij}$ some positive weight? If so, may you please give me a reference where I can find the proof for weighted graph?

Thank you

$\endgroup$
7
$\begingroup$

Start with the unweighted case. We have $L=BB^T$ where $B$ is (what I call) the incidence matrix of an orientation of $G$. So $B$ has one 1 and one $-1$ in each column with all other entries zero. The left kernel of $B$ consists of the functions on $V(G)$ that are constant on the components of $G$. Since $B$ and $BB^T$ have the same rank, we get the connection between number of components and multiplicity of 0 as an eigenvalue of $L$.

Now suppose we have a non-zero weight on each edge of $G$, and let $\Delta$ be the diagonal matrix with rows and columns indexed by $E(G)$, and with $i$-th diagonal entry equal to the weight of the $i$-th edge. Then $B\Delta B^T$ is your weighted Laplacian and, since $BB^T$ and $B\Delta B^T$ have the same rank, we're done.

$\endgroup$
  • $\begingroup$ This works, thank you. I am looking for a reference including the proof for weighted graphs, to cite it in a paper. The closest one that I could find is 'Algebraic graph theory' by R. Royle, Springer 2001, but it includes the proof for non-weighted graphs only. Do you know a reference containing the proof in the weighted case? $\endgroup$ – James Aug 3 '15 at 13:42
  • $\begingroup$ I am not sure that it needs a reference. You could make the observation that the weighted Laplacian is $B\Delta B^T$, and its rank is equal to the rank of $B$. (And then appeal to the unweighted case.) $\endgroup$ – Chris Godsil Aug 3 '15 at 14:22
  • 2
    $\begingroup$ @Michele maybe it went unnoticed but Professor Chris Godsil is one of the authors of the book you mentioned ;-) $\endgroup$ – MSardelich Feb 7 '16 at 21:46
2
$\begingroup$

You can simply imitate the proof in the unweighted case. The Rayleigh quotient associated to the Laplacian is:

$$R_G(f) = \frac{\langle Lf, f \rangle}{\langle f, f \rangle} = \frac{\sum_{x \sim y} (f(x) - f(y))^2 w_{x,y}}{\sum_x f(x)^2}$$

Assuming the weights are all positive we get that $R_g(f) \geq 0$ with equality if and only if $f$ is locally constant, and the dimension of the space of locally constant functions on a graph is just the number of connected components.

An additional advantage of having the formula above lying around is that you can also use it to adapt the usual proof of the Cheeger inequality to weighted graphs.

$\endgroup$

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.