0
votes
0answers
26 views

The lower bound of Cheeger Inequality as the degree goes to infinity

Consider an undirected graph $G(V,E)$ with adjacency matrix $A$ and define the graph Laplacian as \begin{equation} L = D - A \end{equation} where $D$ is a diagonal matrix such that $D(i,i) = d_i$. ...
0
votes
1answer
42 views

Can this famous theorem extended to the weighted undirected graphs?

There is well-known bound on the largest eigenvalue of graphs that says $$\sqrt{d_{max}}\leq \lambda_{max}$$. Is it also true for weighted graphs? (Where as usual, the degree of a vertex in a weighted ...
0
votes
1answer
20 views

Is there any weighted graph which smallest eigenvalue of its adjacency matrix is greater than 1?

Is there any weighted or unweighted graph which smallest eigenvalue of its adjacency matrix is greater than 1?
8
votes
1answer
175 views

Two formulas for the minimal eigenvalue of a graph

Hello again everybody, I'm reading Fan Chung's monograph Spectral Graph Theory. In it, she has two formulas for the minimal eigenvalue of a graph. She doesn't explain why they're equivalent, and I'm ...
12
votes
1answer
449 views

What does the minimal eigenvalue of a graph say about the graph's connectivity?

I'm reading Fan Chung's Spectral Graph Theory, and I'm now in chapter 2. There, Chung proves Cheeger's inequality, which is that $2h_G \geq \lambda_1 > h_G^2/2$ for any graph $G$. To me, this ...
1
vote
1answer
243 views

eigen decomposition of an interesting matrix (general case)

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= b^{L},$ the set of all different sequences of length $L$ where each element of the sequence can be an integer in $\left \{ 0, 1, .., b-1 ...
4
votes
1answer
336 views

eigen decomposition of an interesting matrix

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$. $V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...