# Tagged Questions

31 views

### Explicit expression of eigenvalue and eigenvector of a graph

Could any one tell me what kind of graph has the explicit expression of its eigenvalue and eigenvector? Thanks!
35 views

### Principal EigenVector of an Adjacency matrix of an undirected graph

For an undirected graph, since the adjacency matrix will be symmetric, can we draw any relations between the principal eigenvector and the degree of nodes in the graph. Also can we do the same with ...
39 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 ...
18 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?
47 views

### Are perfect graphs always invertible?

Is it always the case that perfect graph is invertible? Also, is it any meaningful relation between inverse of a perfect graph and itself? Thanks.
67 views

### 0 eigenvalue of weighted laplacian

I consider (weighted) directed graph and eigenvalues of its laplacian matrix. If a graph contains rooted out-branching which is the subgraph possessing a node can approaching to any nodes in the ...
53 views

### Eigenvalues of weighted Laplacian

Let $L_{n \times n}$ be a Laplacian matrix of a directed graph, for example, $$L = \begin{bmatrix} 2 & -1 & -1\\ 0 & 1 & -1\\ -1 & 0 &1 \end{bmatrix}.$$ Gersgorin disc ...
98 views

### Minimal spectral radius of a primitive matrix

Given the set of all primitive matrices of dimensions $m$ by $m$ that are non-negative and integer - which one is the matrix with the minimal spectral radius? Edit (according to the first comment): ...
63 views

91 views

### Possible relation between spectra bounds of two matrices

A Laplacian matrix $L\in\mathbb{R}^{n\times n}$, is a symmetric matrix with entries, l_{ij}=\begin{cases} 1=\sum_{i,~ i\neq j} w_{ij} &\mbox{if } i=j \\ -w_{ij} & ...
153 views

### Eigenvalues of a special block matrix associated with strongly connected graph

Definition Let $G=(V,E,A)$ be a strongly connected directed graph, where $V=\{1,2,...,n\}$ denotes the vertex set, $E$ is the edge set, and $A$ is the associated adjacent matrix with $0-1$ weighting, ...
972 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?
2k 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 ...
1k views

### Spectrum of adjacency matrix of complete graph

Fooling around in matlab, I did an eigenvalue decomposition of the adjacency matrix of $K_5$. ...
179 views

### Eigenvalues of regular graphs

Could someone give me a hint for exercise 2.iii of these lecture notes? The exercise asks to show that a $k$-regular undirected graph (without loops) whose adjacency matrix $A$ has eigenvalues ...
311 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 ...
158 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 ...
380 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 ...
220 views

### Graphs with eigenvalues of large multiplicity

For a strongly regular graph, there are exactly 3 eigenvalues, all nonzero (I believe). One has multiplicity 1, which means the other two have pretty high multiplicities. There are tables that give ...
671 views

### Is there any relation between the principal eigenvector of the original matrix and its inverse?

This question pop'd up when I was studying graph. I am thinking about the relation between principal eigenvector of adjacency matrix $A$ and its inverse $A^{-1}$, do they have any relation?
222 views

### Why the eigenvectors of the Laplacian of a Ring graph are sinusoids?

The eigenvectors of the Laplacian of a Ring graph with $n$ vertices are: $x_k(u) = \sin(2\pi ku/n)$ and $y_k(u) = \cos(2\pi ku/n)$ for $1\leq k \leq n/2$. The explanation according to Spielman's ...
165 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 ...