Articles of spectral graph theory

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$ number of $K_2$ matrices where the adjacency matrices are self-inverse. Are there any other classes?

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$. Let $E’=\{e_1,\ldots,e_l\}\subset E(K_n)$, where $l\leq \frac{n}{2}$ Let $G’$ be the graph obtain from $K_n$ in the following way: -$V(G’)=V(K_n)$ -$E(G’)=E(K_n)-\{E’\}$ That means $G’$ is the graph […]

How can I prove that $\left|\sum_{i=0}^r (-1)^i \binom{a}{i} \binom{n-a}{r-i}\right| \leq \binom{n}{r}$?

This is a conjecture: How can I prove that \begin{equation} \left|\sum_{i=0}^r (-1)^i \binom{a}{i} \binom{n-a}{r-i}\right| \leq \binom{n}{r} \end{equation} for $0\leq a \leq n$, $0\leq r \leq n$ and $n,r,a \in \mathbb{N}$ ?

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 not connected. Now A can be block diagonalized, $A=diag(A_1,A_2\cdots A_t)$ where each $A_i$ is the adjacency matrix […]

Integral identity graphs — smallest example

From Paulus Graphs. “The (25,2)-, (25,4)-, and (26,10)-Paulus graphs have the apparently rather unusual property of being both integral graphs (or asymmetric) and identity graphs (a graph spectrum consisting entirely of integers).” I once quietly conjectured this was impossible, but I was proven wrong. Very wrong. Eric Weisstein was amused enough by my reaction that […]

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 true, that $I-A$ matrix is invertible if and only if there is no directed cycle in $G$?

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, then they have similar adjacency matrices, $A_1$ and $A_2$. In fact, they are similar in an even stronger sense: they satisfy $A_1=PA_2P^{-1}$, where $P$ […]

Spectrum of adjacency matrix of complete graph

Fooling around in matlab, I did an eigenvalue decomposition of the adjacency matrix of $K_5$. A = [0 1 1 1 1; 1 0 1 1 1; 1 1 0 1 1; 1 1 1 0 1; 1 1 1 1 0]; The eigenvalues are $4, -1, -1, -1, -1$. It now seems obvious that […]

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 retrieval technique (LSI) uses a truncated SVD as a low-rank approximation of a matrix. If we truncate to rank 1, then we essentially have a […]

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_k)=\frac{1-x^2}{1-a_kx+2x^2} \tag{1} $$ Now multiply each of the $n$ expressions $G(x,a_k)$ and compare it with Ihara’s $\zeta$ function for cubic graphs. Using $\chi-1=F-2$$\;=E-n$, there seems […]