# Tagged Questions

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

3k 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 ...
285 views

### All Ihara $\zeta$ functions for planar $k$-regular graphs with a given set of faces are equivalent

This sounds like a simple piece of math (which got a long story over time, thanks for reading!) and the consequence seems surprising. At least to me. Here it is: It boils down to comparing two ...
911 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?
6k views

### What do the eigenvectors of an adjacency matrix tell us?

The principal eigenvector of the adjacency matrix of a graph gives us some notion of vertex centrality. What do the second, third, etc. eigenvectors tell us? Motivation: A standard information ...
3k views

### Spectrum of adjacency matrix of complete graph

Fooling around in matlab, I did an eigenvalue decomposition of the adjacency matrix of $K_5$. ...
829 views

### On the invertibility of adjacency matrix

Which are the sufficient and necessary conditions for an undirected graph with no self edges (i.e. no loop of length 1) to have an invertible adjacency matrix? I recall that in this case the ...
296 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, ...
160 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$ ...
66 views

### ELI5: What is spectral graph theory?

I am aware that there is already a similar question here, but unfortunately I find the discussion there to be beyond my grasp. I am looking for an intuitive explanation of spectral graph theory, as ...
275 views

### Questions on fractional Laplacian graph spectra

Both the signed ($D-A$) and unsigned ($D+A$) Laplacian are of interest in spectral graph theory, see eg Cvetkovic: Bibliography on the signless Laplacian eigenvalues: first one hundred references. ...
484 views

### How adjacency matrix shows that the graph have no cycles?

Let $G$ a directed graph and $A$ the corresponding adjacency matrix. Let denote the identity matrix with $I$. I've read in a wikipedia article, that the following statement is true. Question. Is it ...
56 views

### On the eigenvalues of “almost” complete graph ?!

Preliminaries: Let $K_n$ be the complete graph on $n$ vertices. $|E(K_n)|=\frac{n(n-1)}{2}$. It's well known that the eigenvalues of $K_n$ are $n-1$ with multiplicity 1, and -1 with multiplicity $n-1$...
169 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$ ...
207 views

### Is each edge interpreted like a $2$-cycle?

Let $a_k$ a an eigenvalue of the adjacency matrix $A$ of a planar cubic graph with $n$ vertices. For the returning paths without backtracking we get the generating function of G(x,a)=\frac{1-x^2}{1-...
496 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 ...
51 views

### Spectrum of k-partite graph

For a given undirected graph, it is known that the signless Laplacian $Q=D+W$ is positive semidefinite, where $W$ is the adjacency matrix and $D$ is the degree matrix. In particular, the smallest ...
Let $G\times H$ be the Cartesian Product of $G$ and $H$. Determine $L(G\times H)$ in terms of $L(G)$ and $L(H)$ where $L(G)$ denotes Laplacian Matrix of $G$. Also find the eigen ...