Conjecture regarding second smallest eigenvalue of a Laplacian matrix

387 Views Asked by At

I am conjecturing that: Let $G$ be a connected graph, after min-cut let $C_1$ and $C_2$ are two almost equal sized (vertex difference should not go beyond 1) connected components of a graph $G$. Then the second smallest eigenvalue of Laplacian matrix of $G$ can not be more than the second smallest eigenvalue of any of $C_1$ and $C_2$. That is, $\lambda_2(L(G))\leq\lambda_2(L(C_i)), i=1,2.$

Intuition behind this conjecture is that min-cut throws away weak edge connections from the graph and keeps strong connections in components. And we know that second smallest eigenvalue of the Laplacian (Fiedler Value or algebraic connectivity) of a graph represents the connectivity of the graph, more the Fiedler value stronger connected the graph.

Does it make sense? If so, I am interested to convert this conjecture to a mathematically result. Any comment/idea/hint/suggestion/mathematically proof/counterexample is welcome. If result is already there in literature, kindly let me know.

Below information might be useful:

Let $L(C_i), i=1,2$ are of order $m\times m$, then order of $L(G)$ will be $2m \times 2m$. By matching the order of $L(C_i)$ and L(cut-set) to $L(G)$ by adding zero rows and columns, we have $$L(C_1)=L(G)-L(\text{cut-set})-L(C_2) ~\text{and}~ L(C_2)=L(G)-L(\text{cut-set})-L(C_1).$$

Note that here second-smallest eigenvalue of $L(C_i)$ will be first non-zero eigenvalue. Thus we have to show that $\lambda_2(L(G))\leq\lambda_{m+2}(L(C_i)), i=1,2.$