# Tagged Questions

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

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 ...
35 views

95 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 ...
75 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? ...
98 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 ...
81 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 ...
79 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 ...
57 views

134 views

75 views

### The second smallest eigenvalue of a complete binary tree

Apparently it is true that the second smallest eigenvalue of a complete binary tree is $\theta(\frac{1}{n})$. Can someone point out a reference which proves this?
91 views

### Is this graph and its spectrum understood?

Consider the graph whose vertices are labelled by the binary representation of the integers from $0$ to $2^{d}-1$ for some $d \in \mathbb{N}$. So its a graph with $2^d$ vertices. An edge exists ...
80 views

### Properties of non-negative non-symmetric square matrices

I've done some searching but couldn't get much from the web. I am looking for some pointers regarding the properties of non-negative non-symmetric square matrices. The elements within the matrix are ...
204 views

### Spectral gap vs. algebraic connectivity

Can someone please clarify how the spectral gap of a graph relates to its algebraic connectivity (aka Fiedler value) and whether these use the adjacency matrix or laplacian matrix?
103 views

### Is there such a notion of “expansion” in groups?

Given a subset of elements of a finite group $G$, I would like it to be such that the set of all distinct words (as elements of $G$) that can be formed from this set is exponentially large in the size ...
53 views

### Reference for the proof of interlacing of eigenvalues of submatrices

If one has a $n \times n$ Hermitian matrix $A$ and one removes $k$ of the rows and their corresponding columns then the eigenvalues of the remnant interlace the eigenvalues of the full matrix. Can ...
1k 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 ...
47 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 ...
36 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 $n$...
73 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? ...
952 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?
46 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 ...
38 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 ...
146 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.
35 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$ ...
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 ...