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

3
votes
2answers
360 views

A finite graph G is $d$-regular if, and only if, its adjacency matrix has the eigenvalue $λ = d$

Show that a graph $G$ finite with $n$ vertices is $d$-regular if, and only if, the vector with all the coordinates equals to 1 is eigenvetor from eigenvalue $λ = d$ from the adjacency matrix $A$ ...
10
votes
1answer
684 views

Eigenstructure of discrete Laplacian on uniform grid

The discrete Laplacian of a graph is the matrix $L = D - A$ where $D$ is a diagonal matrix with $d_{ii}$ being the degree of $v_i$, and $A$ is the usual adjacency matrix. Is there anything known ...
2
votes
0answers
49 views

Properties of a generalized graph

I'll start with formulating my problem and then ask my question: To generalize a graph $Ga = (Va,Ea)$, we partition its nodes into disjoint sets. The elements of a partitioning $V$ are subsets of ...
4
votes
1answer
244 views

Spectral graph theory and connected components of graphs

We know that multiplicity of least eigenvalue of laplacian matrix of graph gives us number of connected components in graph.What is intuition behind this theorem? How do we know that this works in ...
7
votes
3answers
1k views

Significance of eigenvalue

When I represent a graph with a matrix and calculate its eigenvalues what does it signify? I mean, what will spectral analysis of a graph tell me?
25
votes
1answer
4k views

What do the eigenvectors of an adjacency matrix tell us?

The principal eigenvector of the adjacency matrix of a graph gives us some notion of vertex centrality. What do the second, third, etc. eigenvectors tell us? Motivation: A standard information ...
11
votes
5answers
2k views

Spectrum of adjacency matrix of complete graph

Fooling around in matlab, I did an eigenvalue decomposition of the adjacency matrix of $K_5$. ...
1
vote
0answers
133 views

Spielman. Spectral Graph Theory Proposition

Spielman says in Lecture 3: Laplacians and Adjacency Matrices Fiedler’s Theorem will follow from an analysis of the eigenvalues of tri-diagonal matrices with zero row-sums. These may be viewed as ...
1
vote
1answer
184 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
75 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
423 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
227 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
187 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 ...
13
votes
1answer
486 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
506 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
399 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
229 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
174 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
182 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 ...