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

Filter by
Sorted by
Tagged with
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
soerenssen's user avatar
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 ...
H A Helfgott's user avatar
  • 19.3k
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 $...
Antoine Labelle's user avatar
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 ...
ARG's user avatar
  • 4,342
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 ...
beta_me me_beta's user avatar
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 ...
M. Winter's user avatar
  • 12.5k
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 $\...
M. Winter's user avatar
  • 12.5k
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^...
Rafael L. Greenblatt's user avatar
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 ...
Giulio Castegnaro's user avatar
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 ...
H A Helfgott's user avatar
  • 19.3k
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}$. ...
Yahav Boneh's user avatar
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 ...
N math's user avatar
  • 219
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{...
Subhayan's user avatar
  • 221
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 ...
Rahul Sarkar's user avatar
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 ...
Johnny Cage's user avatar
  • 1,543
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$, ...
Yahav Boneh's user avatar
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 ...
Jackson Abascal's user avatar
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 ...
Yahav Boneh's user avatar
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 $...
avocado's user avatar
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 ...
Shahrooz's user avatar
  • 4,738
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 ...
Saheb's user avatar
  • 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 ...
Shahrooz's user avatar
  • 4,738
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 ...
N math's user avatar
  • 219
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 ...
Charlotte's user avatar
  • 444
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 ...
Mathmo's user avatar
  • 223
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 ...
thedeathstar1997's user avatar
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 ...
volperossa's user avatar
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 ...
Xin Nie's user avatar
  • 1,764
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 ...
Olivier's user avatar
  • 10.2k
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 ...
Maurizio Moreschi's user avatar
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?
user149371's user avatar
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 ...
vidyarthi's user avatar
  • 2,007
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 $\...
Joseph O'Rourke's user avatar
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 ...
alesia's user avatar
  • 2,572
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 ...
Ferran V.'s user avatar
  • 627
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 \...
Sirolf's user avatar
  • 493
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)...
Sirolf's user avatar
  • 493
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,...
Ella Sharakanski's user avatar
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 ...
Sirolf's user avatar
  • 493
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 ...
W. Wang's user avatar
  • 437
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 ...
YtroS's user avatar
  • 11
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 ...
Ivan Feshchenko's user avatar
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],...
kvphxga's user avatar
  • 175
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_{...
Eli4ph's user avatar
  • 151
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 ...
Nick Dong's user avatar
  • 211
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$, ...
Ella Sharakanski's user avatar
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$ ...
Sirolf's user avatar
  • 493
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 ...
mtheorylord's user avatar
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 ...
Hanna Gábor's user avatar

1 2
3
4 5
8