For questions on spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial,...
0
votes
1answer
30 views
For which spectrum is the following result for?
I don't know if I am the only one that feels this, but damn Spectral Graph Theory needs some notation change... Maybe it is because I am not so experienced in the field yet, but man every time I read ...
0
votes
1answer
64 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$), ...
0
votes
1answer
50 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:
...
4
votes
0answers
70 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 ...
2
votes
0answers
39 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
303 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
0answers
38 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 ...
1
vote
0answers
26 views
spectral graph theory with “potentials”
Let G be an undirected graph with bounded degree and n vertices. Let L[G] be the corresponding graph Laplacian, which is a symmetric $n \times n$ matrix. Let V be an $n \times n$ diagonal matrix. I am ...
1
vote
0answers
58 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 ...
1
vote
0answers
102 views
Spielman. Spectral Graph Theory Proposition
Spielman says in Lecture 3: Laplacians and Adjacency Matrices
Fiedler’s Theorem will follow from an analysis of the eigenvalues of tri-diagonal matrices with zero row-sums. These may be viewed as ...
1
vote
0answers
63 views
algebraic connectivity of the giant component
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 ...
0
votes
0answers
8 views
What is the difference between k-means and k-medoids?
I need to partition some graphs by using spectral clustering. Those graphs can be symmetric or asymmetric with positive weights on edges.
As I know, both plus indicator vector are three methods for ...
0
votes
0answers
11 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}$ ...
0
votes
0answers
12 views
Spectra of composition of graphs (lexicographic product)
I would like to know how to relate the eigenvalues (eigenvectors) of the lexicographic product of two graphs in terms of the eigenvalues (eigenvectors) of the factors...I hope someone can help me...
0
votes
0answers
27 views
Spectral density of a directed graph?
I have two specific queries:
When computing spectral density function for undirected graphs, we have
\begin{equation}
\label{specdensity}
\rho(\lambda) = \frac{1}{n}{\sum_{j=0}^{n-1} ...
0
votes
0answers
82 views
Eigenvalues of weighted Laplacian matrix $L$ and $ML$, where $M$ is a diagonal matrix with positive entries
I have a weighted Laplacian matrix of a directed graph and a diagonal matrix $M$ with positive entries. Is it possible to establish a relation between the eigenvalues of $L$ and those of the product ...
