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
393
questions
3
votes
0
answers
141
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 ...
9
votes
2
answers
236
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 ...
5
votes
0
answers
110
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 ...
4
votes
1
answer
185
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 $...
1
vote
0
answers
105
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
votes
1
answer
318
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 ...
6
votes
1
answer
234
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 ...
2
votes
0
answers
55
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 $\...
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^...
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 ...
4
votes
1
answer
511
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
76
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}$.
...
1
vote
1
answer
174
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 ...
2
votes
0
answers
160
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{...
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 ...
0
votes
0
answers
80
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 ...
7
votes
1
answer
279
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$, ...
3
votes
0
answers
141
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 ...
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 ...
0
votes
0
answers
146
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 $...
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 ...
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 ...
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 ...
2
votes
1
answer
142
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 ...
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 ...
2
votes
1
answer
159
views
Anderson localization for Bernoulli potentials on half-line
Anderson localisation for (discrete) Schrödinger operators with Bernoulli potentials on $l^2(\mathbb{Z})$ was proven in
https://link.springer.com/article/10.1007/BF01210702
I am wondering if there ...
2
votes
2
answers
111
views
Question about eigenvalues of connectivity matrices for graphs [closed]
I'm a computer science student working on a research project that deals with computational study of atomic clusters. I'm using a graph based representation of the clusters using a binary connectivity ...
2
votes
0
answers
422
views
Normalized Laplacian matrix versus walk Laplacian matrix (or normalized adjacency matrix versus walk adjacency matrix)
In graphs, found that two different normalization matrices exist for Laplacian and adiacency matrix. I will ask about the adjacency matrix (for the Laplacian matrix the questions are the same). The ...
3
votes
1
answer
172
views
Reference request: maximal Cheeger constant for 3-regular graphs
Given a connected graph $G$, the Cheeger constant $h(G)$ (a.k.a. Cheeger number or isoperimetric number) roughly measures the "bottleneckedness" of $G$. See Wikipedia for the precise definition.
I ...
11
votes
2
answers
930
views
Algebraic properties of graph of chess pieces
For the purpose of this question, a chess piece is the King, Queen, Rook, Bishop or Knight of the game of chess. To a chess piece is attached a graph which represents the legal moves it can make on an ...
2
votes
0
answers
65
views
Infinite trees whose spectrum has more than 3 connected components
I was wondering whether there exists any infinite tree $T$ such that the action of $\mathit{Aut}(T)$ on the set of vertices $V=V(T)$ has finitely many orbits, and whose spectrum $\sigma(T)$ has ...
0
votes
1
answer
126
views
Spectral of a connected d-regular bipartite graph [closed]
Let $G$ be a connected $d$-regular bipartite graph.
Would you please tell me about the spectrum of this graph?
0
votes
0
answers
62
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
votes
0
answers
213
views
Graphs with the same Laplacian eigenvalues
Let $L$ be the
Laplacian matrix
for a simple graph $G$ of $n$ vertices,
and $\lambda_0,\ldots,\lambda_{n-1}$ its $n$ eigenvalues.
Q.
What is the cardinality of the class of $n$-vertex graphs $\...
1
vote
0
answers
159
views
Large bounded degree expanders in the hypercube
Does the $n$ dimensional hypercube graph contain large bounded degree expanders as subgraphs? For example, of exponential size in $n$?
If not, one could relax the problem and allow the maximum ...
3
votes
1
answer
138
views
Eigenfunctions adjacency operator on infinite graph in $l^2$
Let $\Gamma$ be an infinite (connected) graph without edges going from a vertex to itself (though it might have multi-edges). Let us suppose that $\Gamma$ has finite valence.
Is there always a ...
1
vote
0
answers
110
views
Digraphs with same number of semiwalks
This is a follow-up question to Characterisation of walk-equivalent digraphs.
Question: Do there exists two directed graphs $G$ and $H$ consisting of the same number ($n$) of vertices, such that
\...
1
vote
1
answer
135
views
Characterisation of walk-equivalent digraphs
Setting Let $G=(V,E)$ be an undirected graph. A walk $\pi$ in $G$ of length $k$ is a sequence of $k+1$ vertices $v_1,\ldots,v_{k+1}$ such that for each $i\in[1,k]$,
$\{v_i,v_{i+1}\}\in E$. Let $H=(W,F)...
2
votes
0
answers
318
views
Why do we assume that $\mathcal{A}$ is an algebra in this 2003 paper of Bobkov and Tetali?
In Bobkov and Tetali - Modified Log-Sobolev Inequalities, Mixing and Hypercontractivity (extended version Modified Logarithmic Sobolev Inequalities in Discrete Settings), at the beginning of section 3,...
2
votes
1
answer
117
views
Two cospectral (normal) digraphs which are not orthogonal similar
Preliminaries
A complex matrix $A$ is normal when $A$ and $A^*$ commute. A real matrix $A$ is normal when $A$ and $A^t$ commute.
Two complex matrices $A$ and $B$ are said to be unitary similar if ...
2
votes
1
answer
181
views
On sum of elements in products of matrices for a simple graph
Let $G$ be a simple graph with vertex set $\{v_1,v_2,\ldots,v_n\}$. The adjacency matrix of $G$ is the 0-1 matrix
$A$, where $A_{i,j}=1$ when $v_i$ is adjacent with $v_j$. The degree matrix is the ...
1
vote
2
answers
911
views
Eigenvectors of graph Laplacian for spectral clustering
I have the following questions regarding the graph Laplacian for spectral clustering:
What is the intuition behind projecting the Laplacian (D-A, where D is the degree matrix and A is the affinity ...
2
votes
0
answers
168
views
Algebraic connectivity of the path $P_n$
Let $G$ be a graph with $n$ vertices.
Denote by $L(G)$ the Laplacian matrix of $G$ and
$0=\lambda_1\leqslant\lambda_2\leqslant...\leqslant\lambda_n$ its spectrum.
The number $\lambda_2$ is called the ...
1
vote
1
answer
111
views
Spectral bound for maximum clique $k(G)$ in a permutation graph
Let $\pi \in S_n$ be an arbitrary permutation. By permutation graph, we refer to a simple graph with nodes $[n]$ and edges that connect pairs of nodes that appear sorted in $\pi$. Formally, $G=(V=[n],...
5
votes
0
answers
267
views
Can the corollary of the Ihara–Bass formula be extended to $ u^2 = 1 $?
Suppose there is a finite undirected graph $G(V,E)$ having $n$ vertices and $m$ edges.
The non-backtracking matrix $B$ is indexed by $2m$ directed edges and defined as
$$
B(a \to b, c \to d) = \delta_{...
4
votes
2
answers
1k
views
What's the full assumption for Laplacian matrix $L=BB^T=\Delta-A$?
Graph with no-selfloop, no-multi-edges, unweighted.
directed
For directed graph Adjacency matrix is a non-symmetric matrix $A_{in}$ considering indegree or $A_{out}$ considering outdegree. Degree ...
7
votes
1
answer
482
views
Understanding Gillman's proof of the Chernoff bound for expander graphs
My question is about the proof of Claim 1 in this paper: Gillman (1993).
At the end of the proof, the author says:
The matrix product $U^\top\sqrt{D^{-1}}(P+(\mathrm{e}^x-1)B(0)-\mu I)\sqrt{D}U$, ...
7
votes
1
answer
335
views
Co-spectral fractional isomorphic graphs with different Laplacian spectrum
I am looking for two undirected graphs $G$ and $H$ of the same order (i.e., they have the same number of vertices) such that $G$ and $H$ are
cospectral (i.e., their adjacency matrices $A_G$ and $A_H$ ...
2
votes
2
answers
859
views
Upper bounds for the second largest eigenvalue in terms of degree?
I am looking for upper bounds on the second largest eigenvalue, $\lambda_2(G)$ of a given graph $G$, with respect to minimum/maximum degrees of the graph. I looked around for some existing bounds most ...
3
votes
1
answer
397
views
Graph Fourier transform definition
I have a question about the definition of the graph Fourier transform. Let me start with definition.
Let $A$ be the adjacency matrix of a graph $G$ with vertex set $V = \{1, 2, \dots, n\}$. The ...