For questions related to the study of properties of a graph in relationship to the spectral properties of some associated matrix.

learn more… | top users | synonyms

4
votes
2answers
384 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$ ...
2
votes
2answers
43 views

Why Laplacian Matrix need normalization and how come the sqrt of Degree Matrix?

I am new here. If I do any rough, please forgive me. My question: Why Laplacian Matrix need normalization and how come the sqrt-power of Degree Matrix? The ...
2
votes
0answers
65 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
1answer
52 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 ...
3
votes
2answers
101 views

Are 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$ ...
5
votes
1answer
52 views

Understanding and interpreting graph spectra

I'm not a mathematician, but a geographer trying to get a grasp on some network analysis I'm experimenting with. I have a few questions related to spectral graph theory that a mathematician could help ...
0
votes
0answers
34 views

Multigrid eigensolver: properties of the Laplacian at different levels of the hierarchy

I'm not entirely sure this is the right place, but I could really use some help. I'm attempting to implement a hierarchical eigensolver specific to graph Laplacians $L_0$, but after one iteration, the ...
1
vote
1answer
56 views

What is the multiplicity of the largest eigenvalue of a graph?

The Laplacian of a graph is a symmetric positive semi-definite matrix and hence has all real eigenvalues. Is there any characterization for the multiplicity of the largest Laplacian (and/or Adjacency ...
0
votes
0answers
10 views

Faber-Krahn inequality for domain in Z^d with nearest-neighbor connections

In $\mathbb{R}^d$ there is a theorem that if you are looking for the first Dirichlet eigenvalue $\lambda_1$ of a domain $D \subset \mathbb{R}^d$ with a given volume $V$, then $\lambda_1$ will be ...
0
votes
0answers
29 views

the number of ways a planar graph can be partitioned

i have a connected planar graph to cut into k parts and want to know how many possible solutions there are. it clearly depends on the shape of the graph since nodes all in a row cannot be partitioned ...
1
vote
0answers
22 views

Weighted undirected graphs, complex Laplacian, complex eigenvalues & spectral clusering

I am rather puzzled and confused, I have been trying to get a clear understanding of how would spectral clustering work for an undirected weighted graph, I have used the normalized Laplacian, but I ...
0
votes
2answers
591 views

Rank of adjacency matrix vs rank of graph Laplacian

What is the relation between rank of the adjacency matrix of a graph and rank of the corresponding graph Laplacian matrix?
4
votes
1answer
196 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
106 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? ...
0
votes
1answer
158 views

Eigenvalues of graph's laplacians

I'm trying to tackle a question from a homework assignment and one of the problems concerns the relation between eigenvalues of a graph's laplacian and its complement's laplacian. The relation is: ...
0
votes
0answers
15 views

Modifications to the definition of graph Laplacian?

Many people have defined various definitions for graph Laplacian. For example see here [1]. What is common between various definitions of Laplacian that makes all of them ``Laplacian"? For example ...
0
votes
1answer
43 views

Graph Laplacian - Spectral Clustering with Regularization

Assume a graph $G=(V,E)$ where the vertices $V$ are points in ${{R}^{D}}$ with $\left| V \right|=n$. The edges $E$ are represented by a $n\times n$ affinity matrix $W$. Consider the graph Laplacian ...
0
votes
0answers
40 views

Eigen vectors of graph laplacians

I have been reading about spectral graph theory from Daniel A. Spielman's notes. Fiedler’s Nodal Domain Theorem from this note says that : Let $G = (V, E, w)$ be a weighted connected graph, and let ...
1
vote
1answer
25 views

Can we say anything about the order of the second largest eigen-value?

Suppose we have a vertex-transitive graph ($G$) with degree $n$ and the number of vertices $N$. Is it possible to say anything about the exact order of $\frac{1}{n-\lambda _2}$ in terms of $N$ and ...
2
votes
3answers
59 views

Can I find the connected components of a graph using matrix operations on the graph's adjacency matrix?

If I have an adjacency matrix for a graph, can I do a series of matrix operations on the adjacency matrix to find the connected components of the graph?
1
vote
2answers
39 views

How to use spectral graph theory to get a measure for graph symmetry?

I looked at graphs, like $K_{12}$ or Frucht's graph and wondered if their spectrum, more specific the degenercies of their eigenvalues, is a mesaure for the (a)symmetry of the corresponding graph? ...
0
votes
0answers
13 views

Extremal eigenvalues & eigenvectors of skew-adjacency matrix

I am looking for ways to obtain the extremal eigenvalues and eigenvectors of the skew-adjacency matrix of a directed graph. The graphs I am interested in are not regular (but they have a maximum ...
1
vote
0answers
26 views

About the topology of a $d$-regular tree

What is the proof that the infinite $d$-regular tree is an universal covering space for any $d$-regular graph? Is it true that the infinite $d$-regular tree is a Ramanujan graph? (any easy way to see ...
2
votes
0answers
24 views

Spectral radius of a time-varying matrix with strictly positive increment

Consider a time varying non-negative matrix $A(t)$ and its spectral radius $\rho(A(t))$ where $t$ denotes the time. If $A(t)$ changes over time with each time a random element in $A(t)$ is being ...
2
votes
1answer
56 views

What is the smallest and the largest possible adjacency eigenvalue of a regular graph?

For a $d-$regular graph I think $d$ is always the largest adjacency eigenvalue and if its bipartite then I think $-d$ is the smallest possible.
1
vote
1answer
26 views

give an example to show it is possible to remove one vertex and the multiplicity of one of eigenvalue rise.

I know that if we consider a graph $G$ with $\lambda$ as one of its eigenvalue of adjacency matrix with multiplicity $n$ ,there is a vertex of $G$ that by removing it ,the multiplicity of $\lambda$ ...
1
vote
1answer
34 views

Spectrum of infinite d-regular tree

Consider the adjacency matrix of the infinite d-regular tree, call it A. To find the spectrum we consider it as an operator in $L^2(V)$. It is stated that $A-\lambda I$ is always one-to-one. I do ...
1
vote
1answer
47 views

Prove a certain matrix is positive semidefinte.

Consider a stochastic matrix $P$, i.e. real, non-negative, square, rows sum to one. Consider $\Xi$ to be a diagonal matrix with a principal left eigenvector of $P$ on the main diagonal and zeros ...
0
votes
0answers
7 views

correlations between network parameters

I am calculating spectral densities for networks. Is there a reason why skewness and kurtosis would, in general, be correlated across many networks? That is, as a feature of networks rather than ...
0
votes
0answers
24 views

Spectral methods with linear programming

Is it possible to model and solve some fundamental spectral methods (say Singular-Value Decomposition) with (Integer?) Linear Programming? Update: say you want to do SVD. Can you model it as a ...
2
votes
1answer
56 views

Is there any graph property which is equivalent to that the spectral radius of its adjacency matrix is less then $1$?

Let $G$ be a directed graph and $A$ the corresponding adjacency matrix. I'll denote with $\rho$ the spectral radius, and with $I$ the identity matrix. What can we say about $G$ when the spectral ...
3
votes
2answers
88 views

How adjacency matrix shows that the graph have no cycles?

Let $G$ a directed graph and $A$ the corresponding adjacency matrix. Let denote the identity matrix with $I$. I've read in a wikipedia article, that the following statement is true. Statement. $I-A$ ...
1
vote
0answers
35 views

Fast Cholesky Factrorization for Tree Laplacians

Suppose $T_1$ and $T_2$ represent two Laplacian matrices of two spanning trees of $n$ vertices. Since the Cholesky factorization needs $O(n)$ time for each $T_i\ (i=1,2)$ due to the tree structure, ...
0
votes
0answers
19 views

K-way Undirected Weighted Graph Partition with K Vertices Pre-Assigned

I have an undirected weighted graph to be partitioned into k subgraphs with minimal edge weight between the partitions and k of the vertices are constrained to lie in separate partitions. I am ...
0
votes
0answers
52 views

Kac's question 'Can one hear the shape of a drum' and Sunada method, a clarification

I'm reading the article http://www.math.upenn.edu/~kazdan/425S11/Drum-Gordon-Webb.pdf, , where Gordon and Webb describe in a simple a way the contruction of a pair of isospectral but non isometric ...
1
vote
1answer
54 views

prove that $G$ is complete graph.

suppose that $G$ is connected graph and for every eigenvalue of its adjacency matrix we have $\lambda \geq -1$. prove that $G$ is complete graph. I think that the easiest way is to show that we have ...
2
votes
1answer
33 views

eigenfunctions on covering spaces of graphs

I am reading about lifts of graphs in relation to covering spaces. Before I pose my question I will explain some of the terminology. Let $G$ and $H$ be two graphs. We say that a function $f: V(H) ...
1
vote
1answer
31 views

Possible eigenvalue of Laplacian

I came across an exercise of book Spectra of Graphs. Show that there does not exist graph whose adjacency matrix eigenvalue is -1/2. Any thougts?
6
votes
1answer
95 views

Graph with largest eigenvalue “almost” $\pi$

While doodling recently I found that the largest eigenvalue of the adjacency matrix of the following undirected graph (ignore directions on edges in picture) is "almost" $\pi$. According to octave ...
1
vote
2answers
26 views

Motivations for Shi-Malik Algorithm

So I've been trying to make sense of the clustering algorithm on page 6 of this paper. Are the "first" k eigenvalues they refer to the smallest eigenvalues? What are the $y_i$ exactly? I don't see ...
4
votes
2answers
61 views

Is there anything special about a graph with the golden ratio in its spectrum?

Given a simple connected graph $g$ with adjacency matrix $\mathbf{A}$. Let the spectrum $\lambda_1 < \lambda_2 < \ldots < \lambda_N$ be the eigenvalues of the equation $\mathbf{A} v=\lambda ...
1
vote
1answer
31 views

Steps in a proof from Spectral Graph Theory by Fan Chung

On page 15 of Spectral Graph Theory by Fan Chung, http://www.math.ucsd.edu/~fan/research/cb/ch1.pdf, before eq (1.14) is the step, $\displaystyle || \sum_{i\neq 0} (1-\lambda_i)^s a_i \phi_i ...
5
votes
1answer
127 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, ...
8
votes
1answer
139 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 ...
0
votes
1answer
73 views

Finding the smallest max eigenvalues for related matrices?

While messing around with a spectral approach to a graph coloring question, I happened upon a type of problem I hadn't seen before. Suppose you have two symmetric $n$ x $n$ matrices in the form ...
0
votes
1answer
43 views

Top and bottom power spectral density of a height profile

Imagine I have a simple 1D height profile which is NOT symmetric. Now, what is truly important for me is to know what are the frequency content of the top profile (i.e. a cut profile above the ...
0
votes
1answer
30 views

If $G$ is connected then $\lambda_2 < \lambda_1$.

Let $G=(V,E)$ be an $n$-vertex , undirected graph with maximum degree $d$, then how to prove the following result. If $G$ is connected then $\lambda_2 < \lambda_1$. where $\lambda_1 \geq \lambda_2 ...
2
votes
0answers
122 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 & ...
0
votes
1answer
51 views

Control principal eigenvector of a row stochastic matrix

I am just trying to consider the classical discrete-time Markov Chain problem. Consider the transition matrix P, which transforms state vector $x(k)$ to $x(k+1)$, satisfying: $x(k+1)$ = $P*x(k)$ It ...
1
vote
1answer
69 views

Graph Isomorphism algorithm that doesn't always work

I just thought of the following incomplete algorithm for deciding whether two graphs are isomorphic: Let $A$ and $A'$ be adjacency matrices of two graphs. Then for some unitary $U,U’$ and diagonals ...