KPPY 70

Regular connected graphs with three distinct eigenvalues or equivalently strongly regular graphs have had a lot of consideration in the literature. The case of non-regular graphs has had much less attention. In this talk I will give some recent results on these graphs. This is based on joint work with Ximing Cheng, Gary Greaves and Alexander Gavrilyuk

Let $\tilde{K}_{2t}$ be the graph on $2t+1$ vertices consisting of a complete graph $K_{2t}$ and a vertex which is adjacent to exactly $t$ vertices of the $K_{2t}$. It is easy to show that if the smallest eigenvalue of a graph $G$ is at least a fixed real number $\lambda$, then there exists a positive integer $t$ such that $G$ does not contain both $\tilde{K}_{2t}$ and $K_{1,t}$. In this talk, we obtain a structure theory for graphs with fixed smallest eigenvalue by using this property.

A connected regular graph $\Gamma$ is a Deza graph, if there exist integers $\lambda$ and $\mu$ such that any two distinct vertices of $\Gamma$ have either $\lambda$ or $\mu$ common neighbours. A circulant is a graph that admits a cyclic group of automorphisms, i.e., it is a Cayley graph of a cyclic group. In this talk, we report on our attempt (in progress) to classify circulants that are Deza graphs. This is joint work with Sergey Goryainov and Leonid Shalaginov.

We characterize the weakly regular $p$-ary bent functions (from $\mathbb{Z}^n_p$ to $\mathbb{Z}_p$) for constructing strongly regular graphs, where $p$ is a prime number. Our work is motivated by interesting results by Chee et al and Tan et al. We, however, use completely different approach, and our parameters of strongly regular graphs include their parameters.

An orthogonal coloring of the two-dimensional sphere is a partition into parts such that no part contains a pair of orthogonal points. It is a well-known result that an orthogonal coloring of the 2-sphere requires at least four parts, and orthogonal colorings with exactly four parts can easily be constructed from a regular octahedron centered at the origin. An intriguing question is whether or not every orthogonal 4-coloring of the 2-sphere is such an octahedral coloring. I will show that if every color class has a non-empty interior, then the coloring is octahedral. Some consequences and related results are also given. This is joint work with Seunghun Lee.