Search Results

According to my calculations in sage, 13 of the 156 graphs on six vertices have simple Laplacian eigenvalues but repeated adjacency eigenvalues. The first of the 13 is a tree with adjacency matrix: $$ …

If I use $\phi$ for characteristic polynomial, then $$ \phi(C_n,t) = \phi(P_n,t) - \phi(P_{n-2},t) - 2. $$ This follows from the formulas in Section 4.1 of "Algebraic Combinatorics" by yours truly, s …

View the vertices as elements of $\mathbb{Z}^n$. If $a\in\mathbb{Z}^n$, define a function $f_a$ on the vertices by $$ f_a(x) = (-1)^{a^Tx}. $$ This function is an eigenvectors and if $a$ has weight …

Suppose we have a set of unit vectors $x_1,\ldots,x_m$ in $\mathbb{R}^d$ such that (for $i=j$) either $x_i^Tx_j=0$ or $|x_i^Tx_j|=a$. The Gram matrix of these vectors can be written as $I+aS$, where $ …

For a start, there's the complements of the paths. (If the Laplacian eigenvalues of a graph are all simple, then so are the eigenvalues of its complement.) Most regular graphs have only simple eigenva …

I do not recall seeing such a characterization. However Neumaier has looked at some related stuff. In A. Neumaier, J. J. Seidel "Discrete hyperbolic geometry" they consider graphs where the second la …

Let $X$ and $Y$ be two cospectral graphs with maximum clique size $a$ and $b$ respectively. Then their $k$-fold strong powers $X(k)$ and $Y(k)$ are cospectral and the maximum size of a clique is $a^k$ …

No. One simple class of examples are Latin square graphs. If $L$ is an $n\times n$ Latin square with entries from $\{1,\ldots,n\}$, the vertices of Latin square graph are the $n^2$ triples; two triple …

One difficulty here is that you are asking a number of questions, none of which have short answers. It follows from results in Chapter 5 of my "Algebraic Combinatorics" that, if you add a loop of wei …

There does not seem to be a large overlap; the basic problem is that homomorphisms generally destroy nearly all spectral information. There are important exceptions though. Thus in https://arxiv.org/a …

These are graphs in the Grassmann scheme, and are the $q$-analogs of the Kneser graphs. A clique will be a collection of subspaces of dimension $k$, any two of which have non-trivial intersection. An …

The column space of $I-P$ is $A$-invariant and therefore there is a matrix $D$ such that $A(I-P)=(I-P)D$. The difficulty is that $D$ will generally not be non-negative and so it it less useful to inte …

Choose a graph $X$ with vertices $u$ and $v$ such that $X\backslash u$ and $X\backslash v$ are cospectral. (In this case I say that $u$ and $v$ are cospectral vertices.) Assume that there is no automo …

If graphs $X$ and $Y$ have adjacency matrices $A$ and $B$ respectively, then the composition of $X$ around $Y$ has adjacency matrix $$ A\otimes J + I\otimes B $$ Assume $B$ is $k$-regular. Then the …

Let $D$ be the Paley tournament on seven vertices. Its vertices are the integers mod seven and there is an arc from $i$ to $j$ is $j-i$ is a non-zero square mod seven. The characteristic polynomial of …