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

0
votes
0answers
15 views

Spectral properties of certain weighted adjacency matrices

I would like to know if anyone has ever studied the spectral properties of the weighted adjacency matrix of a digraph where if $w(u,v)$ is the weight of edge $(u,v)$, then $w(v,u) = w(u,v)^{-1}$. ...
1
vote
1answer
40 views

Which cubic graphs have an eigenvalue of $\sqrt{6}$?

Which cubic graphs have an eigenvalue of $\sqrt{6}$? Can these graphs be constructed? The question is related to this one...
1
vote
3answers
41 views

Are isomorphic graphs also isospectral?

Two graphs are isomorphic if they just have a different labeling for their vertices i.e. if $A$ and $B$ are their adjacency matrices, then, for some permutation matrix $P$, $PAP^T = B$. Two graphs ...
0
votes
1answer
15 views

Value of the Eigenfunction at a point

I'm reading "Laplace-Beltrami Eigenfunctions for Deformation Invariant Shape Representation" http://www.cs.jhu.edu/~misha/Fall07/Papers/Rustamov07.pdf At a certain point the author states "where ...
1
vote
3answers
35 views

The eigenvalues of $A=E-I$, where $E$ is a square matrix made up entirely of $1$'s and where $I$ is the appropriate identity matrix.

Let $A=E-I$, where $E$ is a square matrix made up entirely of $1$'s and where $I$ is the appropriate identity matrix. The following regarding $A$ is stated in my notes, but I am not sure how to show ...
0
votes
0answers
25 views

How can I prove the assertion for a Graph G?

Let G be a graph and A be the adjacency matrix of G. Let $ \delta(G)$ be the minimum degree of G and $\lambda_{min} $ be the least eigen value of A. Show that $\lambda_{min} \leq \delta(G)$.
5
votes
1answer
153 views

Which graphs do have invertible adjacency matrices?

I would like to know if there is any class of graphs for which the adjacency matrices are invertible. At this moment I am aware of only the class of graphs $n K_2$ which is the disjoint union of $n$ ...
0
votes
0answers
99 views

Hashimoto Matrix (Non-backtracking operator) and the Graph Laplacian

The question is: how can we recover the graph Laplacian or its spectrum from the Hashimoto Matrix (also commonly called the Non-backtracking operator)? To make the question as self-contained as ...
3
votes
0answers
37 views

Possible lower Bound of radius of a graph

First of all I would like to ask people to forgive me because the question that I am about to ask is based on results of a study that I was involved in this year. The project was about designing ...
1
vote
0answers
37 views

Graph having bounded degree

A graph is said to have bounded degree if there exists $N \in \mathbb{N}$ such that, for every $x \in V$, one has $\sum\limits_{y \in V} A_{x,y} \le N$. Show that, in this case, for any $f \in ...
1
vote
1answer
32 views

Do you need to know a lot of (regular?) graph theory to get into spectral graph theory?

Do you need to know a lot of (regular?) graph theory to get into spectral graph theory? What are the prerequisites?
0
votes
0answers
27 views

Perron vector of the distance matrix of a tree

Increasing properties of perron vector of distance matrix from the vertex corresponding to which row sum is minimum
0
votes
0answers
48 views

Number of connected components in a graph.

$\newcommand{\R}{\mathbb R}$ Let $G=(V,E,W:E\mapsto\R)$ be an undirected weighted graph with node set $V=(v_1,\dots,v_n)$, edge set $E\subseteq V\times V$ and weights over the edges $W_{ij}$. The ...
2
votes
1answer
49 views

Ball in a $k$-regular tree

Let $X$ be a finite k-regular graph. Fix a vertex $x_0$ and, for $r <\frac{g(X)}{2}$, consider the ball centered at $x_0$ and of radius r in X. Show that it is isometric to any ball with the same ...
1
vote
1answer
26 views

Creating a Hermitian matrix that is also positive semi-definite

Given some measurements on empirical data (in the form of a multigraph with two weighted edges between every pair of vertices), I would like to place the measurements in a Hermitian matrix that also ...
1
vote
1answer
72 views

eigenvalues of cycle graph and its complement graph

I am trying to find the eigenvalue of cycle graph and its complement. How to simplify.Suppose $\omega^{1}+\omega^{n-1}=2\cos (2\pi/n) $, then, $\omega^{\frac{n-1}{2}}+\omega^{\frac{n+1}{2}}=\ ?$ Is ...
1
vote
0answers
37 views

A question about minimizing the $\lambda_{max}$ over a set of diagonal perturbations

Say I have an off-diagonal symmetric $0,1,-1$ entry matrix $B$ and a set of $2k$ diagonal matrices, $D_{11}, D_{12}, D_{21}, D_{22},..,D_{k1},D_{k2}$. (if it helps you can assume that $(1)$ all the ...
0
votes
1answer
20 views

What Laplacian should we use for spectral clustering?

The second eigenvector of the normalized Laplacian $I-D^{-1}W$ or the symmetric normalized Laplacian $I-D^{-1/2}WD^{-1/2}$ can be used to approximate a minmizer of the normalized cut problem. Which ...
5
votes
1answer
129 views

Bounding 2nd-smallest eigenvalue of the Laplacian of the binary tree

I am reading on my own the notes of this lecture series from 2012: http://www.cs.yale.edu/homes/spielman/561/2012/lect04-12.pdf. In section 4.7.2 (page 8) it's mentioned that we can prove a lower ...
0
votes
1answer
29 views

Optimal partitioning of a planar graph

Consider a planar graph, where each node is associated with a weight. I would like to partition the graph such that the sum of the node weights in each group satisfy a minimum requirement. However, I ...
0
votes
0answers
22 views

Spectrum of the circulant graph

How to prove that the eigenvalue of cycle $C_n=\lambda_r=2 cos(2\pi r/n)$?where $r=0,1,...n-1$, which is proved for the circulant matrix with first row $(v_0=0,v_1=1,v_2=0, ...v_{n-2}=0,v_{n-1}=1)$, ...
1
vote
0answers
74 views

Eigenvectors of graph laplacian

Let $L$ be the laplacian matrix of a graph $G$, i.e. $L = D - A$, where $D$ is the degree matrix, and $A$ the adjacency matrix. Let $v_i$ be an eigenvector of $L$. Let $x,y$ be two vertices of the ...
2
votes
0answers
26 views

Integral roots of a circulant matrix

When does the circulant matrix have only integral roots? For example: adjacency matrix for $K_n$ has all the roots integral which is circulant, but in case of Cycle on $n>3$ it is circulant but it ...
4
votes
2answers
79 views

Determinant of $ n \times n$ matrix and its characteristic polynomial.

Suppose, $M_4, M_5,..M_n$ is as follows then determinant and characteristic polynomial of $M_n$. $M_4=\left( \begin{array}{cccc} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 ...
0
votes
0answers
56 views

Who are the mathematicians in US who are working on expander graphs right now?

I am familiar with only the "big" names doing this research like Gharan, Nikhil Srivastava, Dan Spielman, Jean Bourgain, Luca Trevisan, Elina Fuchs, Peter Sarnak , Amin Saberi and Terence Tao. I would ...
1
vote
0answers
34 views

What is the adjacency matrix of a squared (or k^th power) d-regular graph

If $A$ is the adjacency matrix of a $d$-regular graph, then I suppose $A'$(the adjacency matrix of the squared graph) should be $A^2 + A - dI$ (to remove self-loops). What about higher powers? How do ...
4
votes
0answers
59 views

Lower bound for spectral gap for graph on $n$ vertices

Let $G = (V,E)$ be a graph on the vertex set $V$ with edges $E$. Let $A$ be the adjacency matrix for $G$ (so $A_{ij} = 1$ if vertices $v_i$ and $v_j$ are connected by an edge), and $D$ be the ...
3
votes
1answer
142 views

Construction of a Strongly Regular Graph which has regular Neighbourhood graphs in all iteration.

Notation and Definition: $G$ is a Strongly Regular Graph (not complete or a cycle) and is denoted by $\mathrm{SRG}(n,r, \lambda, \mu)$ if it has the following properties: Every two adjacent ...
1
vote
1answer
97 views

Computing eigenvalue of the adjacency matrix of a path

Let $A\in \{0,1\}^{n \times n}$ be the adjacency matrix of a path of length $n$, i.e. having ones on the two off-diagonals, and zeros elsewhere. How does one compute the eigenvalues of this? I know ...
2
votes
0answers
81 views

Eigenvalue of Block matrix: Adjacency of complete bipartite Graph

Let $A\in \{0,1\}^{mn \times mn}$ be the adjacency matrix of a complete bipartite graph with $m$ and $n$ vertices each, i.e. let $A$ be the matrix consisting of two blocks $A_1\in \{0,1\}^{m \times ...
2
votes
2answers
92 views

Confusion between spectral radius of matrix and spectral radius of the operator

The adjacency matrix $A(G)$ of an infinite undirected graph $G$ is considered as a bounded self-adjoint linear operator $A$ on the Hilbert Space $l^2(G)$ (last section of ...
-2
votes
1answer
85 views

Characteristic polynomial of a block matrix

Let $A$ be an $n\times n$ symmetric matrix whose diagonal are is covered by zero blocks (square, but not of a fixed size) and all other entries are $1$ (one). How can I find its Characteristic ...
1
vote
0answers
46 views

Highest eigenvalues/vectors of graph laplacian

In page 8 of the paper Laplacian Eigenmaps for dimensionality reduction and Data Representation it reads: Standard methods show that the solution is provided by the matrix of eigenvectors ...
1
vote
0answers
17 views

Size of intersection of balls on non-ameanable graphs

Let $G$ be a vertex-transitive non-ameanable graph and let $B(x,n)$ be the ball of radius $n$ centered on the vertex $x$. I am interested in estimates on the cardinality of the following set, ...
3
votes
1answer
29 views

How to perturb an adjacecny matrix in order to have the highest increase in spectral radius?

Let's suppose I have a generic directed graph $G$ and it's adjacency matrix $A$. I can add an arc wherever I want in the graph. (i.e. perturb the matrix A changing a single 0 into a 1). Where should ...
0
votes
1answer
35 views

Relation between edge expansion of graph and sparsity

I was going through the lectures of Graph Partitioning and Expanders - Stanford Online. In lecture 1, near the end of page 5, I came across this inequality for regular graphs: $$\phi(S) \leq h(S) \leq ...
0
votes
0answers
16 views

The image of a a vector in the edge space when multiplied by it's incidence matrix.

Consider a graph $G=(V,E)$ and it's incidence matrix $M$. Let $\textbf{x}$ be the characteristic vector for a standard basis vector in $\mathcal{E}$ (a vector corresponding to the one element edges ...
3
votes
0answers
39 views

What do we know about inverses of matrices which are “like” Laplacians of graphs?

Consider the Laplacian $L$ of a bipartite graph. Is there any generic understanding we have about what $1/(z-L)$ looks like? [say $z > \lambda_\max(L)$)] You can consider variations of $L$ like ...
0
votes
0answers
4 views

PageRank metaphor as suspended unlimited capacity pools

What do you think about my metaphor of the centrality measure PageRank? PageRank is an algorithm for evaluating node centrality: it's a function $f:G \to R^n$ where $n$ is the number of nodes in the ...
3
votes
0answers
29 views

How networks with high largest eigenvalues are more robust?

In the literature, it sometimes indicates that network with high value of largest eigenvalue (either adjacency matrix or its Laplacian counterpart) are more robust. Robustness here is relevant to ...
0
votes
1answer
33 views

Construction of graph Laplacian

I have a weighted undirected graph, and all the edge-weights are non-negative. According to the definition of the graph Laplacian matrix, $L=D-W$. In literature, I found that $D$ is known as degree ...
2
votes
0answers
46 views

When do a Regular graph has an odd eigenvalue?

Merely looking at adjacency matrix of a regular graph, without explicit calculation, can we decide that graph will have an odd eigenvalue or not? If regularity is odd, we are sure that it will be an ...
1
vote
1answer
50 views

spectrum of complete p-partite graphs

I need to determine the spectrum of the complete p-partite graph ( in which each partite set has m vertices) using the complement. How can i show this? I know the spectrum of the adjacency matrix of ...
2
votes
0answers
62 views

Interpretations of a weighted adjacency matrix's eigenvectors and eigenvalues?

Suppose that I have weighted undirected graph $G$, and the corresponding adjacency matrix which is a symmetric matrix $A$. Suppose that the edge between node $i$ and $j$ has weight $w_{ij}$, then $$ ...
0
votes
0answers
25 views

Algebraic connectivity (normalized Laplacian): does the non-weighted instance define the upper bound for the weighted graphs with the same topology?

I am not a mathematician but I use a lot of maths. I came across some empirical evidence that the algebraic connectivity (2nd smallest eigenvalue of the random walk normalized laplacian matrix) of ...
2
votes
1answer
90 views

Eigen value and Regular Graph (not Strongly Regular graph).

$A,B$ are 2 adjacency matrices of $d$ Regular graphs(not Strongly Regular graphs). I would like to know- 1.Results/ information related to Eigen values of A,B. There is a formula for ...
1
vote
1answer
67 views

Triangles incident to a node i

I'm trying to use some fragment-based measures for a network. Given an adjacency matrix representing a (large) network how do you calculate the number of triangles that are incident to every node i? ...
2
votes
1answer
89 views

Eigen value of principal submatrix.

I was studying "interlacing property" and trying to find out the below fact- $A$ is an adjacency matrix of a $r$ regular graph $G$. $u,v \in G $;$u,v$ are not similar vertices. $B$ is the ...
3
votes
0answers
79 views

Is there an easy way to realize a graph (i.e. get adjacency matrix) from a fundamental cut-set or loop matrix?

I am looking to realize a graph (i.e. write down its adjacency or incidence matrix) given a fundamental cut-set matrix or loop matrix (with respect to an arbitrary spanning tree). Is there some ...
0
votes
0answers
78 views

Graph Combinatorics: How many such Graphs are there?

How many $4$-regular graphs exist on $8$ vertices? I found that such a graph can't be disconnectd since if so, then graph can be written as disjoint union of atleast two graphs. $4$ regularity ...