0
votes
0answers
45 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
22 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
110 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
15 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
73 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
0answers
112 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
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 ...
1
vote
2answers
75 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
26 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
72 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
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 ...
1
vote
0answers
91 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
79 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$ ...
2
votes
0answers
52 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
76 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
29 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
48 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
0answers
79 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
49 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
41 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
27 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
82 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
405 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
55 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
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
41 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
130 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
73 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
125 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
93 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
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 ...
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
78 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} = ...
1
vote
0answers
55 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
151 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
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 ...
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 ...
1
vote
1answer
88 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$), ...
1
vote
1answer
250 views

Adjacency matrix defines a distance metric

Let $A$ be adjacency matrix of a graph (perhaps weighted). Prove that \begin{equation} \sum_i \sum_j A_{ij} (f_i- f_j)^2 = \mathbf{f}^T L \mathbf{f} \end{equation} where $\mathbf{f}$ holds values of ...
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 ...
1
vote
1answer
362 views

Spectrum of the cycle graph $C_n$

I am trying to find out the spectrum (the collection of eigenvalues) with their multiplicities of the cycle graph $C_n$. Assuming that $X=\pmatrix{x_1\\x_2\\\vdots\\x_n}$ is the eigenvector, by ...
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 ...
1
vote
0answers
151 views

Is there a simple interpretation of the eigenvectors of a graph (visualizable?)?

I want to understand eigenvectors obtain from graphs (adjacency matrices) in an analogous way as they are interpreted from principal component analysis of a set of images, which is easy:Eigenfaces ...
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 ...
2
votes
1answer
275 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 ...
1
vote
1answer
200 views

Strongly connected graph associated with a matrix

This type of matrices $L$ is called Leslie type matrices in Population dynamics: $$L = \begin{pmatrix} f_{11} & f_{12} & f_{13} & \dotsm & f_{1,i-1} & f_{1,i}& \dotsm & ...
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 ...
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 ...