0
$\begingroup$

Suppose there is a directed graph of which every two nodes have connections to each other but with DIFFERENT WEIGHTS. In this case, this is a strongly connected digraph (cycle) but not necessarily symmetric or balance. However, it also looks like a undirected graph since the connections between every two nodes are bidirectional (but with different weights).

Actually I think those theorems or properties that apply to undirected graph CANNOT apply to this kind of digraph as discussed above. Am I right?

For example, does the following theorem apply to the directed graph mentioned above?

For a connected graph $G$ that is undirected, we have: \begin{equation} \min_{x \ne 0, ~ > 1^Tx=0}\frac{x^TLx}{||x||^2}=\lambda_2(L) \end{equation} wherer $L$ is the Laplacian matrix of graph $G$ and $\lambda_2$ is the Fiedler eigenvalue of $L$, i.e., the second smallest nonzero eigenvalue.

$\endgroup$

1 Answer 1

1
$\begingroup$

No, such theorems will not generalize to this kind of graph as a rule. Of course, some results might turn out to apply more generally, but you have to verify this.

In your example, if $L$ is not symmetric, the quadratic form $x^T L x$ is still the quadratic form corresponding to some symmetric matrix: it is equal to $x^T \left(\frac{L + L^T}{2}\right)x$. So we have \begin{equation} \min_{x \ne 0, 1^Tx=0}\frac{x^TLx}{||x||^2} = \min_{x \ne 0, 1^Tx=0}\frac{x^T\left(\frac{L + L^T}{2}\right)x}{||x||^2} = \lambda_2\left(\frac{L + L^T}{2}\right)\end{equation} and you will basically never have $\lambda_2\left(\frac{L + L^T}{2}\right) = \lambda_2(L)$ except by coincidence. So the theorem is not true, and just about every $2$-node weighted digraph you try will give you a $2 \times 2$ counterexample.

$\endgroup$
1
  • $\begingroup$ And actually if $L+L^T$ is not a Laplacian matrix unless $L$ is balanced, $1$ is not its eigenvector associated with its $\lambda_1=0$. Therefore, according to the Rayleigh theorem, this theorem is not true since the condition $1^Tx=0$ does not satisfy. $\endgroup$
    – winston
    May 15, 2017 at 1:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .