Articles of spectral graph theory

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 […]

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 they must be important. I always assumed that spectral graph theory extends graph theory by providing tools to prove things we couldn’t otherwise, somewhat […]