Tagged Questions

For questions related to the study of properties of a graph in relationship to the spectral properties of some associated matrix.

learn more… | top users | synonyms

1
vote
1answer
180 views

Relationship Between Eigenvalue and Degree

I have a question regarding Rayleigh quotient. It's well known that maximal eigenvalue can be found by $$\lambda_{\max}(M)=\max_{x\neq 0}\frac{x^{T}Mx}{x^{T}x}.$$ Using this how to prove that ...
2
votes
0answers
72 views

algebraic connectivity of the giant component [closed]

In percolation theory there is this idea of a giant component, and I am curious what is known about its algebraic connectivity. I looked on google but I was not able to find anything particularly ...
7
votes
1answer
397 views

Spielman's proof of graph connectivity

I use Spielman's lectures on course Spectral Graph Theory I have few question regarding Lecture 2. The Laplacian, especially Lemma 2.3.1 (Graph connectivity). Please, help me to make it a little bit ...
0
votes
1answer
223 views

Proof of Algebraic connectivity

I am very curious about the proof of Algebraic connectivity Algebraic connectivity: The algebraic connectivity of a graph $G$ is the second-smallest eigenvalue of the Laplacian matrix of $G$. ...
8
votes
1answer
183 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
467 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 ...
2
votes
0answers
477 views

Is there any relation between the principal eigenvalue of sub matrix and the original matrix?

I am wondering whether there is any relation between principal eigenvalue of sub matrix and the original matrix. In fact I am facing a problem which is to select $n$ rows and $n$ columns from the ...
3
votes
1answer
382 views

Does an $n\times n$ adjacency matrix of a scale-free network graph have $n$ distinct eigenvalues?

Question updated Suppose that I have an $n\times n$ adjacency matrix $\mathbf{A}$ of a simple graph $G$ where the entry $(i,j)$ represent the number of edges between node $i$ and $j$ in $G$. Note ...
2
votes
1answer
222 views

Justifying a pair of inequalities involving the exponential function

I'm reading Fan Chung's Spectral Graph Theory. There's a pair of inequalities I don't know how to justify. Chung doesn't attempt to explain them, so maybe they're very obvious. Example 1.19 on page ...
0
votes
2answers
172 views

Question from section 1.5 of Chung's Spectral Graph Theory

I'm (slowly) reading Fan Chung's Spectral Graph Theory. At the moment, I'm in section 1.5 which is about eigenvalues and random walks. There's a small technical point that puzzles me. The context ...
2
votes
1answer
174 views

Kinks in the eigenvalue spectrum of short range lattices

Take a periodic one-dimensional lattice of size $N$ with $2k$ nearest neighborers. That is, vertex $i$ is connected to $i+1,i+2,...,i+k$ and $i-1,i-2,...i-k$ (with the understanding that the indices ...