For questions on spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial,...

learn more… | top users | synonyms

27
votes
6answers
2k views

Motivation for spectral graph theory.

Why do we care about eigenvalues of graphs? Of course, any novel question in mathematics is interesting, but there is an entire discipline of mathematics devoted to studying these eigenvalues, so ...
22
votes
1answer
3k views

What do the eigenvectors of an adjacency matrix tell us?

The principal eigenvector of the adjacency matrix of a graph gives us some notion of vertex centrality. What do the second, third, etc. eigenvectors tell us? Motivation: A standard information ...
12
votes
1answer
455 views

What does the minimal eigenvalue of a graph say about the graph's connectivity?

I'm reading Fan Chung's Spectral Graph Theory, and I'm now in chapter 2. There, Chung proves Cheeger's inequality, which is that $2h_G \geq \lambda_1 > h_G^2/2$ for any graph $G$. To me, this ...
11
votes
5answers
2k views

Spectrum of adjacency matrix of complete graph

Fooling around in matlab, I did an eigenvalue decomposition of the adjacency matrix of $K_5$. ...
9
votes
1answer
621 views

Eigenstructure of discrete Laplacian on uniform grid

The discrete Laplacian of a graph is the matrix $L = D - A$ where $D$ is a diagonal matrix with $d_{ii}$ being the degree of $v_i$, and $A$ is the usual adjacency matrix. Is there anything known ...
8
votes
1answer
176 views

Two formulas for the minimal eigenvalue of a graph

Hello again everybody, I'm reading Fan Chung's monograph Spectral Graph Theory. In it, she has two formulas for the minimal eigenvalue of a graph. She doesn't explain why they're equivalent, and I'm ...
7
votes
3answers
1k views

Eigenvalues of a bipartite graph

Let $X$ be a connected graph with maximum eigenvalue $k$. Assume that $-k$ is also an eigenvalue. I wish to prove that $X$ is bipartite. Now if $\vec{x}=(x_1,\cdots ,x_n)$ is the eigenvector for ...
7
votes
3answers
1k views

Significance of eigenvalue

When I represent a graph with a matrix and calculate its eigenvalues what does it signify? I mean, what will spectral analysis of a graph tell me?
7
votes
1answer
371 views

Spielman's proof of graph connectivity

I use Spielman's lectures on course Spectral Graph Theory I have few question regarding Lecture 2. The Laplacian, especially Lemma 2.3.1 (Graph connectivity). Please, help me to make it a little bit ...
6
votes
0answers
110 views

Applications of Cayley Graphs in Physics

I have been recently reading about Cayley graphs and character theory. It is evident that Cayley graphs are very useful tool in theoretical computer science. In physics, Cayley graphs seem do appear ...
5
votes
1answer
121 views

Laplacians, Diagonal Perturbations

Setup: Consider a Laplacian (or Kirchoff) matrix $L = L^T \in \mathbb{R}^{n \times n}$ corresponding to a weighted, undirected and connected graph. That is, a matrix with $L_{ij} \leq 0$ for $i\neq j$ ...
5
votes
0answers
78 views

Spectral gap of mixture of Markov chains

Context Let $P$ be the transition matrix of an irreducible, aperiodic, discrete-time Markov chain. The spectral gap is given by $$\xi = 1 - \lambda_\max$$ where $\lambda_\max = \max\{\lambda_2, ...
5
votes
0answers
139 views

Generating a stochastic matrix with a given second dominant eigenvalue

I need a procedure (iterative or otherwise) that, given a positive integer $N$ and a (possibly complex) number $\lambda$ such that $0 < \vert \lambda \vert < 1$, will be able to generate an $N ...
4
votes
1answer
253 views

Intuitive interpretation of the adjacency matrix as a linear operator.

Naturally we can describe graphs via tables of "yes there is an edge" or "no there is not" between each pair of vertices, so the definition of an adjacency matrix is easily understood. Thinking of ...
4
votes
1answer
229 views

Spectral graph theory and connected components of graphs

We know that multiplicity of least eigenvalue of laplacian matrix of graph gives us number of connected components in graph.What is intuition behind this theorem? How do we know that this works in ...
4
votes
1answer
84 views

What graph Laplacians commute

I know that the graph Laplacian of a fully connected graph commutes with the Laplacian of any other graph. Is there any theorem stating something similar about some more general family of graphs? ...
4
votes
1answer
162 views

Questions on fractional Laplacian graph spectra

Both the signed ($D-A$) and unsigned ($D+A$) Laplacian are of interest in spectral graph theory, see eg Cvetkovic: Bibliography on the signless Laplacian eigenvalues: first one hundred references. ...
4
votes
1answer
214 views

characteristic polynomial of the adjacency matrix of a tree

I have read that if $A$ is the adjacency matrix of a tree $T$, then we have that $$\det(\lambda I - A) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k N_k(T) \lambda^{n-2k} $$ where $N_k(T)$ is the number ...
4
votes
0answers
159 views

spectral radius (adjacency matrix) of a partitioned graph

Is the following bound on the largest eigenvalue of a partitioned graph known? It seems like it should be but I am not able to find a reference to it. Given a graph $G=(V,E)$ whose vertices are ...
4
votes
0answers
75 views

Extension of Cheeger's inequality with distinguished vertices

The standard Cheeger's inequality for graph $G$ states that $\frac{1}{2}$ $\lambda$ < $\phi(G)$ < $\sqrt{2\lambda}$ where $\lambda$ is the second smallest eigenvalue of the normalized ...
3
votes
2answers
61 views

Graphs with zero spectrum / nilpotent symmetric matrices

Is there a graph theoretic characterization of those graphs with zero spectrum? Alternatively, can one at least characterize all symmetric nilpotent (complex) matrices, so that one could recognize ...
3
votes
2answers
321 views

A finite graph G is $d$-regular if, and only if, its adjacency matrix has the eigenvalue $λ = d$

Show that a graph $G$ finite with $n$ vertices is $d$-regular if, and only if, the vector with all the coordinates equals to 1 is eigenvetor from eigenvalue $λ = d$ from the adjacency matrix $A$ ...
3
votes
1answer
50 views

Show the relationship between the trace and the number of 4-cycles

Let $G$ be a k-regular graph. Show the exact relationship between $tr(A^4)$ and the number of 4-cycles in $G$. I understand how $tr(A^4)$ tells us the total number of closed paths of length 4 in ...
3
votes
1answer
357 views

Does an $n\times n$ adjacency matrix of a scale-free network graph have $n$ distinct eigenvalues?

Question updated Suppose that I have an $n\times n$ adjacency matrix $\mathbf{A}$ of a simple graph $G$ where the entry $(i,j)$ represent the number of edges between node $i$ and $j$ in $G$. Note ...
3
votes
2answers
78 views

Is the eigenvectors of vertex transitive graphs bounded

For a connected and regular graph $G$ with degree $ d $ at each vertex and adjacency matrix $A$, the normalized Laplacian of $G$ is defined as $L = I-\frac{1}{d}M$. Let $\psi$ be an eigenvector of $L$ ...
3
votes
2answers
1k views

Lowest Eigenvalue of a positive semi-definite matrix

I am reading a paper on spectral graph theory. Let us say we have an adjacency matrix W and a degree matrix D. We construct a Laplacian matrix, L defined as: L = D - W The paper claims that L is ...
3
votes
0answers
84 views

Constructing a directed graph from its spectrum

This is related to the following question from cs theory stack exchange: http://cstheory.stackexchange.com/questions/3742/reverse-graph-spectra-problem So it seems as if given a sequence of real ...
3
votes
0answers
40 views

Is the upper Cheeger Inequality tight?

The (upper) Cheeger Inequality says: Let $G$ be an unweighted, undirected, regular graph of degree $d$. Let $\lambda_2$ be the second eigenvalue of the Laplacian matrix of $G$, and let $\phi(G)$ ...
3
votes
0answers
129 views

What can we say about two graphs if they have similar adjacency matrices?

Suppose we have two (finite, simple, undirected) graphs, what can we say about these graphs if they have similar adjacency matrices? Observations to begin with: If $G_1$ and $G_2$ are isomorphic, ...
2
votes
1answer
288 views

Connectedness of a regular graph and the multiplicity of its eigenvalue

Suppose $X$ is a $k$-regular graph with adjacency matrix $A$. I wish to show that if $k$ has multiplicity $1$ as an eigenvalue of $A$ then $X$ is connected. By way of contradiction I assume that X is ...
2
votes
1answer
274 views

The number of connected components of a $k$-regular graph equals the multiplicity of k

In similar vein to this question, I am trying to understand the proof of the fact that in a $k$-regular graph, the multiplicity of the eigenvalue $k$ equals the number of connected components. The ...
2
votes
1answer
72 views

Eigenvalues of the distance-k graph of a graph

Let $G$ be a (finite, simple, connected) graph. Define the distance-$k$ graph $G_k$ to be the graph with the same vertex set and $x\sim y$ iff $d(x,y)=k$. A graph is integral if all of the eigenvalues ...
2
votes
1answer
93 views

Connection between the Tutte and characteristic polynomials?

Both the Tutte polynomial $T_G(x,y)$ and the characteristic polynomial $\phi_G(x)$ encode a great amount of structure of the input graph $G$. I've read somewhere that the Tutte polynomial has a kind ...
2
votes
1answer
105 views

Global solution for spectral clustering

I used spectral clustering for directed graphs suggested by Dengyong Zhou paper to partition the graph.I selected the eigen vectors corresponding to k largest eigen values and then I use kmeans or FCM ...
2
votes
1answer
170 views

Kinks in the eigenvalue spectrum of short range lattices

Take a periodic one-dimensional lattice of size $N$ with $2k$ nearest neighborers. That is, vertex $i$ is connected to $i+1,i+2,...,i+k$ and $i-1,i-2,...i-k$ (with the understanding that the indices ...
2
votes
1answer
46 views

the solution of matrix polynomials

In order to get the eigenvalues of \begin{equation} P=\left[ \begin{array}{cc} 0_{n\times n} & I_{n\times n} \\ -A & -B% \end{array} \right], \end{equation} where $A$ and $B$ are both $n\times ...
2
votes
1answer
3k views

Plotting a one-sided amplitude spectrum

I have a continuous signal $x(t)$ such that $$x(t)=12\cos(6\pi t)+6\cos(24\pi t)+3\cos(30 \pi t)$$ and is asked to sketch a $1$-sided Amplitude Spectrum of the signal $x(t)$ if sampled above the ...
2
votes
1answer
210 views

Justifying a pair of inequalities involving the exponential function

I'm reading Fan Chung's Spectral Graph Theory. There's a pair of inequalities I don't know how to justify. Chung doesn't attempt to explain them, so maybe they're very obvious. Example 1.19 on page ...
2
votes
0answers
109 views

a closed formula to enumerate the self avoiding walks of a graph

Let $G$ be a directed graph with $N$ nodes and weighted adjacency matrix $W $ defined by $$ W_{ij} = \left\{ \begin{array}{cl} w_{ij} & \text{ if } \ i \ \text{ is connected to } j \\ 0 & ...
2
votes
1answer
36 views

Functions on adjacency matrices

From Norman Biggs, Algebraic Graph theory 2j, p13: The adjacency matrix has a spectral decomposition $A = \sum \lambda_aE_a$, where the matrices $E_a$ are idempotent and mutually orthogonal. (...) It ...
2
votes
1answer
65 views

Algebraic Combinatorics

Let $K_{r,s}$ denote the complete bipartite graph, defined on $r + s$ vertices $\{v_1,v_2,...,v_r,w_1,...,w_s\}$, with an edge between $v_i$ and $w_j$ for $1 ≤ i ≤ r$ and $1 ≤ j ≤ s$. By ...
2
votes
0answers
51 views

Interesting Questions in Spectral Graph Theory

In the past, I have worked on few problems in Spectral graph theory and their applications to Physics. I have read parts of Fan Chung's book and Daniel Spielman lecture notes. I really enjoyed the ...
2
votes
0answers
47 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 ...
2
votes
0answers
48 views

Possible Eigenvalues of Graph

How would one prove (or disprove) that there is no such graph $G$ with $\lambda$ as an eigenvalue? I tried setting up a system of equations to see if it's possible for $-\frac{1}{2}$ to be an ...
2
votes
0answers
150 views

Bounds on the maximum eigenvalue of the adjacency matrix of a graph.

I managed to proof the following result for the maximum eigenvalue: $ d_{avg}\leq \lambda_{max} \leq \Delta(G) $ where $d_{avg}$ is the average degree of the graph while $\Delta(G)$ is the maximum ...
2
votes
0answers
46 views

Properties of a generalized graph

I'll start with formulating my problem and then ask my question: To generalize a graph $Ga = (Va,Ea)$, we partition its nodes into disjoint sets. The elements of a partitioning $V$ are subsets of ...
2
votes
0answers
71 views

algebraic connectivity of the giant component [closed]

In percolation theory there is this idea of a giant component, and I am curious what is known about its algebraic connectivity. I looked on google but I was not able to find anything particularly ...
2
votes
0answers
451 views

Is there any relation between the principal eigenvalue of sub matrix and the original matrix?

I am wondering whether there is any relation between principal eigenvalue of sub matrix and the original matrix. In fact I am facing a problem which is to select $n$ rows and $n$ columns from the ...
1
vote
3answers
222 views

How to find the spectrum of the hypercube?

I want to find the proof of the spectrum of the hypercube
1
vote
2answers
87 views

Spectrum of a 3-regular graph

Let $D_n$ be the following graph on $2n$ vertices: $V=\mathbb{Z}_n\times\{0,1\}$ and $E=\{(i,j)(i+1,j): i\in \mathbb{Z}_n,j\in \{0,1\}\}\cup\{(i,0)(i,1):i\in\mathbb{Z}_n\}$. What is the spectrum of ...