The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
0answers
240 views

What is a “Ramanujan Graph”?

I noticed an apparent conflict in the definition in literature about what is a "Ramanujan graph, which I was wondering if someone could kindly clarify. (1) The Hoory-Linial-Wigderson review on ...
0
votes
0answers
13 views

Looking to derive bound for modulus of harmonic eigenfunction on weighted graph

We have a homogeneous graph $G = (V,E)$ with a function $f:V\rightarrow \mathbb{R}$. We define the following modulus: $\displaystyle \omega(s) = \sup\{f(x)-f(y) \ | \ |x-y|=s \}$ and wish to lower ...
1
vote
0answers
50 views

Is there an elliptic Harnack equality for directed graphs?

The elliptic Harnack inequality for undirected graphs was proven by Delmotte in the paper "Inegalite de Harnack elliptique sur les graphes" (French, ...
4
votes
1answer
173 views

Do perfect matching(s) have signatures in the graph eigenvalues?

If the edges of a bipartite graph are such that they can be seen as a disjoint union of perfect matchings then will this somehow reflect in the eigenvalues of the Laplacian? It would be helpful to ...
4
votes
2answers
113 views

Graphs whose degree vectors coincide for all powers of their adjacency matrices

Let symmetric $A,B \in \{0, 1\}^{n \times n}$ denote the adjacency matrices of two simple graphs. Further let $\mathbf{1}$ denote the all-one-vector. Now assume that $A^k \mathbf{1} = B^k \mathbf{1}$ ...
9
votes
4answers
257 views

Are these three different notions of a graph Laplacian?

I seem to see three different things that are being called the Laplacian of a graph, One is the matrix $L_1 = D - A$ where $D$ is a diagonal matrix consisting of degrees of all the vertices and $A$ ...
7
votes
3answers
359 views

Is there a continuous analogue of Ramanujan graphs?

I think it might help to think of the following definition of a Ramanujan graph - a graph whose non-trivial eigenvalues are such that their magnitude is bounded above by the spectral radius of its ...
4
votes
0answers
110 views

minimal polynomial for a graph

I wonder if there is any result relating the degree $d$ of the minimal polynomial of a directed finite graph to any of its topological features - such as its diameter, or any other similar 'natural' ...
2
votes
2answers
89 views

About the roots of the matching polynomial

Can someone kindly give me an expository reference on matching polynomial and its roots? (there is a proof that they are always real?) I saw these two related discussions, Roots of matching ...
2
votes
0answers
61 views

Are there two-sided $\varepsilon$-expanders with independent sets of size $(1-\varepsilon)n$?

Terry Tao's notes on expander graphs has the following exercise: Exercise 13 Let $G$ be a $k$-regular graph on $n$ vertices that is a two-sided $\epsilon$-expander for some $n > k \geq 1$ and ...
0
votes
0answers
171 views

A question about Assaf Naor's review in Bourbaki about the Batson-Spielman-Srivastava result

I am referring to this article - http://www.cims.nyu.edu/~naor/homepage%20files/Exp.1033.pdf If I understand right, the author states that his equations (8) and (9) are equivalent to the equations ...
3
votes
1answer
133 views

Meaning of eigenvalue 1 and symmetry in Laplacian spectra of graphs

We often see normalized Laplacian spectra of graphs where density on eigenvalue 1 serves as an axis of symmetry, with particularly high (blue spectra in the figure) or low densities (red spectrum) ...
0
votes
2answers
99 views

Form of the Shannon capacity for Heptagon?

Is the $0$-error capacity of $7$-cycle: $(1)$ known to be of form $7^q$ for some $q\in \mathbb Q$?
3
votes
2answers
106 views

eigenvalue estimate of the adjacency matrix

The adjacency matrix of a nonempty (undirected) graph has a strictly positive largest eigenvalue $\lambda_\max$. A very easy upper estimate for it can be obtained directly by Gershgorin's theorem: $$ ...
5
votes
0answers
160 views

(Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples

Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...
8
votes
1answer
110 views

Can the graph Laplacian be well approximated by a Laplace-Beltrami operator?

It seems rather well known that given a Laplace-Beltrami operator $\mathcal{L}_{M}$ on a manifold $M$ we can approximate its spectrum by that of a graph Laplacian $L_{G}$ for some $G$ (where $G$ is ...
2
votes
2answers
105 views

Largest eigenvalue adjacency matrix-link deletion

Let G be a connected undirected graph and G\e be a graph obtained by removing a random link e from the graph G. Let $\lambda_1(A(G))$ be the largest eigenvalue of the adjacency matrix of graph G. Is ...
7
votes
1answer
207 views

A conjecture about strongly regular graphs

Let $G \neq K_{v}$ be a $(v,k,\lambda,\mu)$ strongly regular graph. After perusing through Brouwer's tables of parameters I have formed the conjecture $$\lambda-\mu \leq \frac{k}{2}.$$ So far I have ...
5
votes
1answer
167 views

Full-rank factorization of the graph Laplacian

Is there a combinatorially meaningful full-rank factorization of the Laplacian matrix of a graph? The usual factorization $L=BB^{T}$, where $B$ is an oriented incidence matrix, is full-rank if and ...
1
vote
0answers
68 views

Cheeger inequality for the maximal eigenvalue

Let $G = (V,E)$ be an undirected graph and let $L = I - D^{-1/2} A D^{-1/2}$ be its normalized Laplacian matrix. The Cheeger inequality asserts that: $$\frac{\Phi_G^2}{2} \leq \lambda_2 \leq 2 ...
2
votes
1answer
84 views

limiting empirical spectral distribution of the Laplacian matrix on an Erdos-Renyi graph?

Let $G$ be an Erdos-Renyi random graph (i.e. an edge ($ij$) exists with probability $0 < p < 1$ and all edges are independent). Let $L$ be the Laplacian matrix of this graph (i.e $L=D-A$, where ...
5
votes
2answers
264 views

Roots of matching polynomial of graph

At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial: If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ ...
0
votes
0answers
22 views

Diffusion maps for non-Markov

Diffusion maps based on the work of Coifman and Lafon use concepts from Markov chains and heat diffusions. Have there been work to extend diffusion maps to non-Markovian or fractional heat ...
8
votes
1answer
198 views

Spectral lower bounds on the diameter of a graph

There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$: $$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$ This bound is very elegant but ...
2
votes
1answer
87 views

Eigenvalues of a graph and its one-edge-delation graph

Let $G$ be any graph with at least one edge and let $e$ be any edge of $G$. Let $G-e$ denote the subgraph of $G$ obtained by deletion of the edge $e$. Assume that $G$ has $n$ vertices. Suppose ...
3
votes
0answers
143 views

Must distinct tree eigenvalues be relatively far apart?

How close to each other can two distinct eigenvalues of a tree be, as a function of the number $n$ of nodes ? For example, the path $P_n$ exhibits a gap of order $\frac{2\pi^2}{n^2}$ asymptotically ...
1
vote
0answers
70 views

interpretation of generalized eigenvalue/vectors in spectral graph theory

Let us say I have a symmetric graph adjacency matrix A, a degree matrix D, a laplacian L (D-A). I have a generalized eigenvalue equation $Av=\lambda Lv$. Does the eigenvalue/vectors produced in this ...
12
votes
3answers
294 views

How can I prove that a particular family of graphs is integral?

I'm working with an infinite family of graphs that seems to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs $G_{n,k}$ and define them ...
3
votes
1answer
109 views

The spectral radius of a modified graph

Let $H$ be a graph and let $G=H \vee K_{1}$ be obtained by creating a new vertex and joining it to every vertex in $H$. This situation has many different names: $G$ is called the cone or the ...
0
votes
1answer
127 views

Which graph topology has the greatest eigenvalue?

I am looking at comparing multiple graph topologies based on their spectra. From the set of all $N\times N$ adjacency matrices, is there any result which points to the adjacency matrix with the ...
5
votes
2answers
164 views

Reflexive (hyperbolic) graphs

Is there an effective description of the graphs such that exactly one eigenvalue (of the conventional adjacency matrix) is $>2$ whereas all others are $\le2$? By "effective" I mean something ...
3
votes
2answers
447 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 ...
0
votes
0answers
98 views

How could I prove this equality for eigenvalues of Laplacian matrix?

I would be glad if you have some comments that how I could prove following statement. Suppose that graph $G =(N, E)$ be given. The the following program computes the $k$-smallest eigenvalues of the ...
2
votes
1answer
205 views

Graph of Grassmannian

Let p be an integer, and let G be the graph $(V=Gr(k,\mathbb{F}_q ^n),E)$ where: $Gr(k,\mathbb{F}_q ^n)$ is the set of all subspace of $\mathbb{F}_q$ of dimension k, and $E=\{ W_1,W_2 \in V | ...
9
votes
1answer
314 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 ...
2
votes
0answers
139 views

If two graphs have same Laplacian spectrums, are they the similar graphs?

If graph A and graph B have exactly the same Laplacian spectrums, can I just say they are same graphs? (only with scaling edge weights and node index reordering) I don't know if there is any explicit ...
2
votes
0answers
216 views

On the existence of Graph Monomorphism

A graph monomorphism is an injective graph homomorphism. Determining existence of Graph monomorphism between graph pairs is computationally hard. Assume we talk only about classes of undirected ...
1
vote
1answer
246 views

When does graph Laplacian have eigenvalue -1?

Consider an undirected graph $G$ with (symmetric) adjacency matrix $A \in \{0,1\}^{n \times n}$ and degree sequence $d = (d_i)$ where $d_i = \sum_{j} A_{ij}$. Assume that every node has degree at ...
7
votes
1answer
309 views

normalized laplacian spectrum of trees

Is it known for which class of graphs the normalized laplacian has only simple eigenvalues (i.e., with multiplicity one)? In particular, are there trees (or perhaps a specific class of trees) whose ...
3
votes
1answer
234 views

Cospectrality and dimension of graphs

Firstly, I apologize if the question is long. I appreciate any helpful answers and ideas. In the following all graphs are simple and connected. Let $G$ be graph with vertex set ...
2
votes
2answers
271 views

What is the state of the art on triangle-free strongly regular graphs?

From what I've read I've gathered the following facts: There are seven known such graphs. Certain parameter sets are ruled out by the Krein conditions and the absolute bound. Beyond that, little or ...
4
votes
1answer
259 views

How to find or constrain “particularly good” (two-sided) spectral expanders?

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs. A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...
1
vote
2answers
133 views

Are trees spectrally determined?

Are trees (connected acyclic graphs) determinable up to isomorphism by their spectra or characteristic polynomials? If not, what other pieces of information may help determine the tree?
3
votes
0answers
235 views

A problem on graph theory and complex numbers!

Let ${\mathcal G} = ({\mathcal V},{\mathcal E})$ be a simple connected undirected graph with $n$ vertices. Also let $z_1, \ldots, z_n \in {\mathbb C}$ be complex numbers such that $$ ||z_1||=\ldots = ...
10
votes
0answers
244 views

Spectral theory of graph Laplacian besides $\lambda_2$

Most of what I've seen about the spectral theory of the graph Laplacian concentrates on $\lambda_2$, the second-smallest eigenvalue. This eigenvalue contains information regarding the connectivity of ...
3
votes
1answer
199 views

Graph Laplacian simple eigenvalues

Is there a class of graphs (besides the path graphs) for which we know that the Laplacian L = D - A (where D is the degree matrix and A is the adjacency matrix) has simple spectrum, i.e. all Laplacian ...
7
votes
2answers
288 views

Small eigenvalues and spectral clustering

Let $L$ be the discrete Laplacian associated to an undirected graph. It is well-known that the spectral gap of $L$, i.e. the smallest nonzero eigenvalue, is a measure of how well connected the graph ...
1
vote
0answers
69 views

Effect of removing a Hamiltonian cycle on the Laplacian spectrum

Notation: $\lambda_{\max}(G)$ is the largest eigenvalue of the Laplacian matrix of the graph $G$ (aka the Laplacian index of $G$). Now suppose $G$ is a Hamiltonian graph with Hamiltonian cycle $C$. ...
1
vote
0answers
125 views

Recovering a partition from spectral properties of the graph Laplacian

Let $G$ be a weighted graph with vertices $V$. Let $W$ be its real-valued, non-negative, $|V|\times|V|$ adjacency/affinity matrix. Let $L = \mathrm{diag}(W\mathbf1)-W$ be the (unnormalized) graph ...
4
votes
1answer
216 views

What is the largest possible operator norm of a sparse (0,1)-matrix?

Inspired by this question, I was wondering about the following problem: Consider all $n\times n$ $(0,1)$-matrices with $k$ ones. Which of these matrices has the largest operator norm? And how does ...