Questions tagged [spectral-graph-theory]
Questions related to the spectrum of graphs, defined using one of the possible variants of the discrete Laplace operator or Laplacian matrix. See https://en.wikipedia.org/wiki/Discrete_Laplace_operator
397
questions
1
vote
0
answers
100
views
Varieties determined by a characteristic-type of polynomial with the structure of an underlying graph
While writing my master thesis, following problem came up:
Given a digraph $G$ with edges $e_1,..,e_n$ and a
given a $n\times n$- matrix $A\in\mathbb{C}^{n\times n}$ such that $A_{ij}=0$ if the ending ...
- 11
2
votes
0
answers
115
views
Formulas to determine the value of graph energy with addition or deletion of edges
If $G$ is a graph, then the graph energy of $G$ denoted by $E(G)$ is defined as the sum of absolute values of eigenvalues of the adjacency matrix of $G$. It is known that $E(G)\geq E(G-v)$, where $ ...
- 203
6
votes
3
answers
415
views
Eigenvalues of the Laplacian of the directed De Bruijn graph
We will denote by $DB(n,k)$ the directed De Bruijn graph, which is a digraph whose vertices are elements of $\{0,1,\dots,k-1\}^n$, and $\sigma_1\cdots \sigma_n$ is connected to $\tau_1\cdots \tau_{n}$ ...
- 1
0
votes
0
answers
57
views
How can I find family of non-isomorphic graphs with specific properties?
I asked this question:
How to find non-isomorphic graphs with specific orders?
Two new questions have arisen for me.
I have a graph, $G$, with $2n$ vertices. It has one connected component of order $...
- 219
3
votes
1
answer
167
views
How to find non-isomorphic graphs with specific orders?
I work on a problem in my research. I have a graph, $G$, with $2n$ vertices. It has one connected component of order $2n-1$ and an isolated vertex. $\lambda_1\geq \lambda_2\geq \ldots \geq \lambda_{2n}...
- 12.3k
62
votes
5
answers
12k
views
Intuitively, what does a graph Laplacian represent?
Recently I saw an MO post Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs? that got me interested. ...
- 270
0
votes
0
answers
165
views
Closed non-backtracking walks and eigenvalues of the adjacency matrix in non-regular graphs
Let $\Gamma$ be an undirected finite graph. Write $M_r$ for the number of non-backtracking closed walks of length $r$ in $\Gamma$, i.e., walks where a step is never
followed by its inverse. Let $A$ be ...
- 19.4k
2
votes
0
answers
158
views
Closed geodesics and eigenvalues in a non-regular graph
Let $\Gamma$ be an undirected graph the degree of whose $n$ vertices is $\leq D$ without necessarily being constant. Say we have bounds of type $\leq \gamma^{2 k}$ for the number of closed geodesics ...
- 19.4k
4
votes
0
answers
155
views
Relation between two conjectures on reconstruction of graphs
In spectral graph theory, there is a conjecture that claims: Almost every graph is determined by its adjacency spectrum ($DS$). This conjecture belongs to professor Willem Haemers.
Also, we have a ...
- 4,748
7
votes
1
answer
283
views
Is this lower bound for the size of minimal vertex cover new/interesting?
I have found this lower bound for the size of minimal vertex cover (and proved it).
If a simple connected graph G on n vertices has largest and smallest eigenvalues $\lambda_1,\lambda_n$, ...
- 133
5
votes
1
answer
610
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$. ...
- 22.8k
0
votes
1
answer
92
views
If there are eigenvectors with largest components $i$ resp. $j$, then is there an eigenvector with two largest components $i$ and $j$?
Let $G=(V,E)$ be a connected (finite simple) graph with vertex set $V=\{1,...,n\}$ and let $\theta_2\in\Bbb R$ be the second-largest eigenvalue of its adjacency matrix. I wonder about the following ...
- 12.6k
2
votes
0
answers
185
views
The rank of a Laplacian-type matrix
Suppose that $M$ is an integer, symmetric matrix of order $n>2$ with the positive integers $K_1,\dotsc,K_n$ on its main diagonal, and with all the off-diagonal elements equal to $0$ or $1$ so that ...
- 22.8k
3
votes
1
answer
127
views
Spectral properties of half-transitive graphs
The half-transitive graphs form a curious class of graphs with some kind of intermediate symmetry that is non-trivial to achieve. More precisely, a graph is half-transitive if its symmetry group is
...
- 12.3k
0
votes
0
answers
250
views
How is the second smallest eigenvalue of normalized laplacian bounded for random graphs?
It is well known that for any graph G following holds
$\frac{\lambda_2}{2} ≤ \phi(G) ≤ \sqrt{2\lambda_2}$, where $\phi(G)$ is the conductance of the graph and $\lambda_2$ is the second smallest ...
- 2,758
1
vote
1
answer
244
views
Jordan blocks of directed graphs
Let $G$ be a (possibly weighted) directed graph with $n$ vertices and let $P$ be its transition matrix. That is, $P = D^{-1}A$ where $A$ is the graph's adjacency matrix and $D$ is a diagonal matrix ...
- 111
12
votes
1
answer
659
views
Is there Matrix-Tree theorem for counting the bases of a connected matroid?
The famous Kirchhoff's Matrix-Tree theorem counts the number of spanning trees of a connected graph, that is, the number of bases of its cycle matroid. But it appeals to vertices, that's why I do not ...
- 22.9k
77
votes
4
answers
14k
views
What are good mathematical models for spider webs?
Sometimes I see spider webs in very complex surroundings, like in the middle of twigs in a tree or in a bush. I keep thinking “if you understand the spider web, you understand the space around it”. ...
- 111
2
votes
0
answers
193
views
Expansion of random subgraphs of a bi-regular bipartite graph
Let $G = (L, R, E)$ be a bi-regular bipartite graph, with $|L|=n$ and $|R| = C \cdot n$, where $C$ is a large constant. Let $d$ be its (constant) right-degree.
We know $G$ is a good spectral expander. ...
- 428
3
votes
1
answer
252
views
Sums over products over short paths in an expander graph
Let $\Gamma=(V,E)$ be an undirected graph of degree $d$. (Say $d$ is a large constant and the number of vertices $n=|V|$ is much larger.) Let $W_0$ be the space of functions $f:V\to \mathbb{C}$ with ...
- 9,631
3
votes
0
answers
250
views
Eigenvalue bounds and triple (and quadruple, etc.) products
Very basic and somewhat open-ended question:
Let $A$ be a symmetric operator on functions $f:X\to \mathbb{R}$, where $X$ is a finite
set. Assume that the $L^2\to L^2$ norm of $A$ is $\leq \epsilon$, i....
- 19.4k
11
votes
1
answer
2k
views
Eigenvalues of the complement of a graph
Let $A$ and $\widetilde A$ be the adjacency matrices of a graph $G$ and of its complement, respectively.
Is there any relation between the eigenvalues of $A + \widetilde A$ and the eigenvalues of $A$ ...
- 51.6k
17
votes
1
answer
598
views
Graph embeddings in the projective plane: for the 35 forbidden minors, do we know their Colin de Verdière numbers?
The Graph Minor Theorem of Robertson and Seymour asserts
that any minor-closed graph property is determined by a finite set
of forbidden graph minors. It is a broad generalization e.g. of the ...
- 9,421
1
vote
2
answers
150
views
From one eigenvector to many, in a very local graph?
Let $\Gamma$ be an undirected graph of bounded degree $d$ with $V = \{1,2,\dotsc,N\}$ as its set of vertices, and edges only between vertices that are at a distance $\leq M$ apart (where $M$ is much ...
- 19.4k
3
votes
0
answers
142
views
Chromatic number of regular graphs using spectra
There exist inequalities relating the maximum and minimum eigenvalues of the adjacency matrix of a graph with its chromatic numbers, i.e. the Wilf's and Hoffmann's inequalities, which put together ...
- 4,618
9
votes
2
answers
237
views
Conjecture of van der Holst and Pendavingh related to bound for Colin de Verdière invariant
In their 2009 paper (“On a graph property generalizing planarity
and flatness”. In: Combinatorica 29.3 (May 2009), pp. 337–361. issn: 1439-6912.
doi: 10.1007/s00493-009-2219-6.), van der Holst and ...
- 71
5
votes
0
answers
112
views
Closed paths, closed trails and traces
Let $A$ be the adjacency matrix of a (non-oriented) graph $\Gamma$. Then $\textrm{Tr} A^k$ equals both the sum $\sum_i \lambda_i^k$ of $k$th powers of eigenvalues of $A$, on the one hand, and the ...
- 19.4k
4
votes
1
answer
190
views
Digraphs with unique walk of length $k$ between any two vertices
Let $G$ be a digraph such that there is an unique directed walk of length $k$ between any two vertices.
Equivalently, if $A$ is the adjacency matrix of $G$, then $A^k$ is the matrix with all entries $...
- 30k
1
vote
0
answers
109
views
Cheeger constant of truncated hypercube
Look at the $d$-dimensional hypercube and truncate it. This means one replaces each vertex by a cycle (of length $d$) in such a way the the new graph is 3-regular.
Question 1: What is the asymptotic ...
- 4,342
6
votes
1
answer
237
views
An eigenvalue upper bound for 1-walk-regular graphs
Let $G$ be a graph and suppose that $G$ is 1-walk-regular (or, if you prefer, vertex- and edge-transitive, or distance-regular).
Let $\theta_1>\theta_2>\cdots>\theta_m$ be the distinct ...
- 12.3k
2
votes
1
answer
154
views
Gaussian bounds with exponential decay for discrete (graph) Dirichlet heat kernel
Let $\Omega$ be a finite, connected subset of $\mathbb{Z}^n$, $W_t$ a standard random walk on $\mathbb{Z}^n$ started at $x$, and $T_\Omega$ the first time at which $W_t$ leaves $\Omega$; consider
$$
P^...
4
votes
1
answer
330
views
Relation between Kirchhoff's Circuital law and Matrix tree Theorem
I'm not a professional mathematician, just an undergraduate student. I was reading Introduction to Graph Theory by West, I came over the topic which discuses the methods to find the spanning trees in ...
- 178k
2
votes
0
answers
57
views
Antipodal vertices in spectral graph embeddings
Suppose your are given an antipodal graph $G=(V,E)$, that is, for every vertex $v\in V$ there is a unique maximally distant vertex $v'\in V$.
Under which condistions does the following hold:
If $\...
- 12.6k
5
votes
2
answers
2k
views
Fiedler vector, what else?
In the spectral analysis of a graph with 1 connected component, the first non-trivial eigenvector (corresponding to the non-zero smallest eigenvalue) is also called the Fiedler vector. This vector is ...
- 338
4
votes
1
answer
524
views
Closed paths, traces and spectra
Let $\Gamma$ be a graph. Write $A$ for its adjacency matrix. It is trivial to show that $\mathrm{Tr} A^k$ equals the number of closed walks of length k, that is, the number of $k$-step walks that ...
2
votes
0
answers
77
views
Upper bound for smallest eigenvalue of infinite family of graphs
Let $\left\{G_{n}\right\}_{n=1}^{\infty}$ be a sequence of regular simple connected graphs with at least one edge such that $G_i$ is an induced sub-graph of $G_{i+1}$ and is not equal to $G_{i+1}$.
...
- 60.4k
0
votes
0
answers
125
views
Lower bounds on the length of circuits, depending on the number of times it crosses itself
I have this problem that I have been stuck on for months, and would like to know if somebody can tell me a way to attack the problem. Let me ask the problem in a simple example below.
Let $G(V,E)$ be ...
- 359
1
vote
1
answer
181
views
Cayley graphs on $Z_{11}$ and $Z_p$
I want to find all cayley graphs on $Z_{11}$. I know how many connected cayley graphs exist but i want to find all of them, connected or not, to find their eigenvalues. I found some of them and a ...
- 12.3k
2
votes
0
answers
162
views
On norms of Boolean functions
Let $f: \mathbb{F}_2^n \rightarrow \{-1,1\}$ be a Boolean function, represented by a $N=2^n$ dimensional vector, $f \in \{-1,+1\}^N$.
Define the Fourier transform of $f$ to be $\hat{f}$, where $$\hat{...
- 60.4k
7
votes
2
answers
1k
views
Dimension of Specht Modules $S^\lambda$
In the study of representation theory of $S_n$, we know that the irreducible characters of $\chi_\lambda$ of $S_n$ are indexed by partitions $\lambda \vdash n$. There are several methods in ...
- 15.6k
0
votes
0
answers
87
views
4-cycles vs eigenvalue information on quasi-random graphs
My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs.
The main purpose of the paper is to show ...
- 1,543
3
votes
0
answers
144
views
How related are Fourier transforms on finite groups and Fourier transforms on graphs?
Here are two generalizations of the notion of a Fourier transform. I am also aware of the Pontryagin Duality generalization for locally compact abelian groups, though I am personally more concerned ...
5
votes
2
answers
603
views
Matching polynomials and Ramanujan graphs
Is it purely coincidental that the same number $2\sqrt{d-1}$ appears in these two following apparently disparate concepts?
A $d-$regular graph is said to be called Ramanujan if its adjacency ...
- 1
4
votes
1
answer
1k
views
Relation of row sums to largest eigenvalue
I know that the largest eigenvalue of a graph is bounded between the minimal and maximal row sum of the matrix. If I have a $0-1$ symetric matrix (an adjacency matrix) and I know $k$ of the rows have ...
- 37.2k
2
votes
0
answers
112
views
Number of components of self-index complementary graphs
Let $G$ be a simple graph. We say this graph is self-index complementary ($SIC$) if $\lambda_1 (G)=\lambda_1 (\overline{G})$, where $\lambda_1(G)$ denotes the index of the adjacency matrix of the ...
- 632
0
votes
0
answers
156
views
$\lambda_2$ of Laplacian of a regular graph
Given a $d$-regular graph $G=(V,E)$ with $|V| =n$. We know that the smallest eigenvalue of the normalized laplacian matrix of $G$ is $0$. I have seen the formulation of the second smallest eigenvalue $...
- 1
0
votes
0
answers
41
views
Orthogonality condition of symmetric matrix pencil
Let $P(\lambda)=\lambda M−L\in \mathbb{R}^{n \times n}$ be a matrix pencil with symmetric nonsingular matrix $M$ and $L$ is a weighted Laplacian matrix of a connected graph. Clearly $(0,1_n)$ is an ...
- 21
1
vote
1
answer
87
views
Total behaviour of graph spectrum
Let $\mathcal{G}$ be the set of all finite connected simple graphs minus the complete graphs. For any $G\in \mathcal{G}$, let $\lambda_{\geq0}(G)$ denotes the smallest positive adjacency eigenvalue of ...
- 470
2
votes
1
answer
145
views
Cocktail party and tripartite graphs are DS?
Cocktail party graphs and $k_{n,n,n}$ (a tripartite graph) are determined by the spectra of their adjacency matrices? I think thay are DS ( determined by the adjacency spectrum) but I can't find a ...
- 31.5k
9
votes
3
answers
2k
views
What happens to eigenvalues when edges are removed?
I am stuck at the following :
Let $G$ be a graph and $A$ is its adjacency matrix.
Let the eigenvalues of $A$ be $\lambda_1\le \lambda_2\leq \cdots \leq \lambda_n$.
If we remove some edges from the ...
- 12.6k