All Questions
11 questions
3
votes
1
answer
148
views
Spectrum of the adjacency matrix of certain directed graphs
For an undirected graph $G$, its adjacency matrix $A_G$ is symmetric, and by the (consequence of) spectral theorem, each of its Jordan blocks has size $1$. This is not true for a general directed ...
- 161
2
votes
0
answers
351
views
Spectral norm bound for lower triangular matrix
Let $A$ be a $0/1$ square matrix which can be permuted to a non singular or a singular lower triangular matrix. Determinant is either $0$ or $1$. Can we provide tighter upper bounds on its spectral ...
- 13.9k
6
votes
1
answer
744
views
Relationship between spectral gaps of adjacency and Laplacian matrices of graphs
Let $G$ be an undirected simple graph on $n$ vertices, with self-loops allowed, and with arbitrary positive edge weights $w_{u,v}$ (which is $0$ if there is no edge between $u$ and $v$).
Let $A$ be ...
- 150
1
vote
0
answers
127
views
Delocalization of eigenvectors of graph Laplacians
Let $(V,E)$ be an undirected, connected graph with $n$ nodes. The graph Laplacian is defined as $L = D - A$, where $D$ is the degree matrix and $A$ is the adjacency matrix. Let $0 = \lambda_1 < \...
- 41
5
votes
1
answer
678
views
Finding zero-one vectors in the row space of a matrix
Suppose that $M$ is a square matrix with all elements on its main diagonal equal to $1$, and every row containing exactly two off-diagonal elements equal to $-1$; all other elements are equal to $0$. ...
- 23k
0
votes
0
answers
67
views
Singular values and the chromatic number
What relation, if any, is there between the singular values of the adjacency matrix ( or possibly incidence matrix) of a simple graph and its chromatic number. Typically, do we have Hoffmann type, or ...
- 2,089
9
votes
3
answers
356
views
Spectrum of orthogonality graph (2)
The orthogonality graph, $\Omega(n)$, has vertex set the set of $\pm 1$ vectors of length $n$, with orthogonal vectors being adjacent.
I am only interested when $4|n$, since otherwise $\Omega(n)$ is ...
- 421
5
votes
0
answers
397
views
spectrum of orthogonality graphs
The orthogonality graph $\Omega(n)$ with $2^n$ vertices is the graph with vertex set $\{-1,+1\}^n$, with two vertices being adjacent if and only if they are orthogonal (as vectors in the standard ...
- 421
1
vote
0
answers
51
views
Relation between nullity of components to its parent graph
Let $G$ be an undirected graph and the corresponding adjacency matrix be $A$. Let $v$ be a cut-vertex of $G$. Let $G_1, G_2,\dots, G_k$ are the connected components of the induced graph $G-v$ ( the ...
- 640
10
votes
0
answers
225
views
Cospectral mate of rhombic dodecahedron
I am wondering if the following pair of cospectral graphs was previously known.
The rhombic dodecahedron graph looks like this (graph6 string: 'M?????rrAiTOd_YO?'):
As far as I know, it was previously ...
- 2,339
9
votes
1
answer
420
views
Coherence between different ranking methods of a graph's vertices
Given a (connected) graph $G$ it is natural to want to rank its vertices, with the more "central" vertices ranked higher.
Two natural ways of doing it are:
By the degrees.
By the entries in a Perron ...
- 6,962