Search Results

Let $D$ be a Steiner triple system on $v$ points. (So $v\equiv1,3$ mod 6). The incidence graph is the bipartite graph with the $v$ points as one colour class and the $v(v-1)/6$ blocks as the second; a …

Since the Johnson graphs are regular, the Laplacian eigenvectors are the eigenvectors of the adjacency matrix. The Johnson graphs belong to an association scheme, the Johnson scheme, and explicit expr …

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 …

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 …

Let $C$ be circulant of order $n\times n$. The first row of $C$ defines a complex function from the cyclic group $\mathbb{Z}_n$; denote its value on $i$ by $\rho(i)$. Define two elements $a$ and $b$ o …

Start with the unweighted case. We have $L=BB^T$ where $B$ is (what I call) the incidence matrix of an orientation of $G$. So $B$ has one 1 and one $-1$ in each column with all other entries zero. The …

You'll find a different looking approach in my paper: C. D. Godsil, Matchings and walks in graphs, J. Graph Theory, 5, (1981) 285–297. The argument there shows that if $G$ is a graph with maximum vale …

Let $M$ be a $d\times m$ matrix over $GF(2)$ and let $X(M)$ be the graph on the binary vectors of length $d$, where two vectors are adjacent in their difference is a column of $M$. (This is a Cayley g …

One approach that goes some way to explaining this is through the path-tree of a graph. This is defined as follows. Choose a vertex $u$ in the graph $G$, The vertices of the path-tree $T(G,u)$ are the …

There's MR1186756: Godsil, C. D.; Hensel, A. D. Distance regular covers of the complete graph. J. Combin. Theory Ser. B 56 (1992), no. 2, 205–238. This only considers covers of complete graphs, but mu …

If $Y$ is a 2-lift of $X$, there is a partition $\pi$ of $V(Y)$ into pairs, such that vertices in a pair are not adjacent and two distinct pairs are joined by a 2-matching, or by no edges at all. Assu …

I show that in some cases, the condition $A^k\textbf{1}=B^k\textbf{1}$ for all $k$ implies the graphs are isomorphic. For an $n$-vertex graph with adjacency matrix $A$ define its walk matrix to be the …

These are usually known as the Laplacian, the normalized Laplacian and the unsigned Laplaian. All three are positive semidefinite. If the graph is regular, they all provide the same information. If t …

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 …

Since the eigenvalues are real, and since their sum is the trace of $A$, which is zero, we see that either all eigenvalues are zero, or there are both positive and negative eigenvalues. So no non-empt …