All Questions
12 questions
21
votes
5
answers
2k
views
The middle eigenvalues of an undirected graph
Let $ \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_{2n} $
be the collection of eigenvalues of an adjacency matrix of an undirected graph $G$ on $2n$ vertices. I am looking for any work or references ...
- 784
8
votes
3
answers
8k
views
Spectrum of an adjacency matrix
The adjacency matrix of a non-oriented connected graph is symmetric, hence its spectrum is real.
If the graph is bipartite, then the spectrum of its adjacency matrix is symmetric about 0. A few ...
- 3,388
7
votes
1
answer
641
views
Lower bound on the eigenvalues of the Laplacian
I am looking for a graph for which $2 d_{i} < \mu_{i}$, for some index $i$, where $\mu_{1} \leq \mu_{2} \leq \dots\leq \mu_{n}$ are the eigenvalues of the Laplacian matrix $L(G)$ and $d_{1} \leq d_{...
- 123
3
votes
1
answer
336
views
Eigenvalues of random graphs
At time $t=0$, let $G_n(V,E)$ be a graph with $n$ vertices and $m < n$ edges. Then there exists a unique symmetric adjacency matrix $A_n$ associated with $G_n(V,E)$, defined as follows: $a_{ij} = 1$...
- 101
2
votes
1
answer
316
views
When does a row standardized adjacency matrix have a real spectrum?
A colleague in spatial statistics was looking at a map with about 600 regions. For the application she's considering, the induced adjacency matrix had some undesirable properties (where two regions ...
- 6,001
2
votes
1
answer
133
views
Is the sum of the circulant matrix with a super upper triangular matrix diagonalizable?
By the circulant matrix $C$ in $M_n(\mathbb{R})$, we mean that
$$C=[e_n|e_1|\cdots|e_{n-1}]$$ where $e_1,\cdots,e_n$ are the standard basis vectors in $\mathbb{R}^n$. It is well-known that
$$C=\...
- 4,058
2
votes
1
answer
156
views
Minimal Laplacian spread of a graph
Laplacian spread of a graph is the difference among the largest and the second smallest Laplacian eigenvalue of the graph. Is there any result or conjecture that discusses about the graphs having ...
2
votes
0
answers
35
views
Limiting spectral distribution of a random matrix with specific structure
First, consider an $N \times N$ Hermitian random matrix $V$ from the Gaussian Unitary Ensemble (GUE). It is well known that the empirical spectral distribution of the GUE satisfies the semicircle law ...
- 21
1
vote
1
answer
847
views
Do there exist graphs whose adjacency matrix is positive semi-definite? [closed]
If so, could you provide examples and specify the conditions under which this occurs? Thank you in advance
1
vote
1
answer
143
views
Eigenvalues of directed graph with one outward edge for each vertex
I am concerned with unweighted directed graphs where each node contains exactly one edge pointing to another node, which could be itself. In other words, each row of the adjacency matrix contains one ...
- 283
0
votes
1
answer
154
views
Energy of a symmetric matrix with $0$, $1$ or $-1$ entries
I have a symmetric matrix with entries $0$, $1$ or $-1$ which appeared in my works in graph theory (the diagonal entries are all zero). I need a good upper bound for the energy of this matrix; i.e. "...
- 351
-1
votes
1
answer
492
views
Upper bound on iterations count for power iteration algorithm
I'm stuck trying to get upper bound on iterations count for power iteration algroithm for finding first eigenvalue of adjacency matrix $A$ given tolerance value. I've tried to figure something out ...
- 89