0
votes
0answers
11 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
0answers
28 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
13 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 ...
1
vote
1answer
48 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
30 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) ...
4
votes
1answer
37 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 ...
1
vote
1answer
28 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
90 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 ...
4
votes
2answers
53 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
27 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 ...
0
votes
1answer
67 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
26 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
115 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
0answers
24 views

What is the importance of Laplacian Matrix in spectral clustering

In spectral clustering algorithms, we often use Laplacian matrix of adjacency matrix instead of Adjacency matrix itself. What is the advantage of using Laplacian matrix over simple adjacency matrix?
1
vote
0answers
32 views

Spectrum of an infinite graph independent of labelling

Does there exist an infinite graph whose spectrum does not depend upon the labelling of the graph? While evaluating the spectrum, I am considering adjacency matrix of the infinite graph as a bounded ...
2
votes
1answer
81 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 ...
6
votes
1answer
128 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 ...
3
votes
1answer
53 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 ...
1
vote
2answers
84 views

Graph Theory - Proof

I am need help to Prove the following statement: Let G be a $k$-regular graph with $n$ vertices and $k \geq 1$. Prove that $G$ does not have an independent set of size greater than $\dfrac{n}{2}$. ...
0
votes
0answers
29 views

The lower bound of Cheeger Inequality as the degree goes to infinity

Consider an undirected graph $G(V,E)$ with adjacency matrix $A$ and define the graph Laplacian as \begin{equation} L = D - A \end{equation} where $D$ is a diagonal matrix such that $D(i,i) = d_i$. ...
1
vote
2answers
89 views

Power series convergence of random walk transition matrix

I would like to find out if $$ \sum_{t=0}^\infty P^t = \left( I- P \right)^{-1} ~,$$ where $P = D^{-1}W ~ $ is a random walk transition matrix. $W$ is a matrix describing weights in a graph and ...
2
votes
1answer
75 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 ...
1
vote
0answers
96 views

Does any vertex transitive graph have a bounded eigenvector?

Following up on the negative answer to this question, I would be interested in knowing the answer to the following question, which I cannot seem to find an obvious contradiction to when testing for ...
3
votes
2answers
88 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$ ...
2
votes
0answers
62 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 ...
1
vote
0answers
78 views

Number of Nodes within a Given Distance from a Node

Suppose we are given a $d$-regular graph $G=(V,E)$ of order $n$. Let $\lambda_2$ be the second-largest eigenvalue of $G$'s adjacency matrix. Does this information help obtaining a lowerbound or ...
0
votes
0answers
33 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 ...
2
votes
0answers
50 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 ...
5
votes
1answer
98 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, ...
1
vote
0answers
44 views

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

I'm working with an infinite family of graphs that seem 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 ...
2
votes
0answers
52 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 ...
1
vote
0answers
44 views

pierre simon laplace and his knowledge of the (Laplacian) matrices

so as we all know, there is a graph matrix called the Laplacian that is used in some eigenvalue/eigenvector/graph theory/spectral theory problems. i'm wondering if the name of this matrix is ...
1
vote
0answers
29 views

How to show that the spectral radius of a binary tree approaches exp(1) as the N tends to infinity?

How can I prove mathematically that the spectral radius of a binary tree approaches e as the number of nodes tends to infinity? I mean it is true that the increase in nodes number is exponential but ...
0
votes
1answer
83 views

Compute eigenvalues of a regular graph.

I have a $(q^2+q)(q+1)$-regular graph. Is there some general method to compute the eigenvalues of the adjacency matrix of a $k$-regular graph explicitly? Or could we estimate its eigenvalues? Thank ...
0
votes
2answers
480 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?
0
votes
1answer
70 views

Are these equivalent representations (labelled graph and adjacency matrix)?

This is an example from Wikipedia's page on adjacency matrices, which from the site's format seems to be suggesting equivalence between the simple diagram below, left, and the abstractly represented ...
3
votes
0answers
100 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
42 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
137 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, ...
1
vote
1answer
77 views

cluster validation and determining number of clusters

I want to find number of cluster in the real world data set. So, I validate the spectral clustering by using some indexes as shown in figures below? But as you seen in figures the results are very ...
0
votes
0answers
133 views

Variance of the first return time of a simple random walk on an hypercube graph

I am trying to solve this problem.... I have a simple random walk on a $d$-cube (finite graph). At each vertex of the graph, the particle chooses one of $d$ edges equally likely. I need to calculate ...
1
vote
1answer
105 views

What does small eigenvalue gap imply for a graph?

Knowing a graph has good expansion has well-known implications. What can we say about graphs with $1-\lambda = O(\log n/n)$, where $1-\lambda$ is the difference between the two largest eigenvalues of ...
2
votes
1answer
96 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 ...
1
vote
0answers
98 views

Algebraic characterization of being $P_n$-free.

Is there an algebraic way to determine from the adjacency matrix $A$ of a simple graph $G$, whether $G$ contains an induced path of fixed length $n$? I am particularly interested in the case $n=6$. ...
1
vote
2answers
79 views

Upper bound on the difference between two elements of an eigenvector

Let $W$ be the non-negative, symmetric adjacency/affinity matrix for some connected graph. If $W_{ij}$ is large, then vertex $i$ and vertex $j$ have a heavily weighted edge between them. If $W_{ij} = ...
2
votes
0answers
64 views

when does a graph with normalized laplacian have a uniform degree distribution?

Consider the graph $G(A)$ with A as its adjacency matrix. Let $L$ be its Laplacian and $L_{sym} = D^{\frac{1}{2}}LD^{\frac{1}{2}}$ be the normalized Laplacian. Now let $A(L_{sym}) = I - L_{sym}$ ...
2
votes
0answers
167 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
1answer
109 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 ...
3
votes
2answers
62 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 ...
1
vote
1answer
89 views

Prove $MM^t=A+kI$ for matrices associated to graphs

How can I prove that $MM^t=A+kI$ for incidence matrix $M$ and adjacency matrix $A$ of a $k$-regular graph with $n$ vertices? It is easy to see that $MM^t$ is an $n\times n$-matrix (like $A$), ...