On Regular Graphs with Complete Tripartite Star Complements

Abstract

Let $G$ be a graph of order $n$ and let $\mu$ be an eigenvalue of multiplicity $m$. A star complement for $\mu$ in $G$ is an induced subgraph of $G$ of order $n-m$ with no eigenvalue $\mu$. Some general observations concerning graphs with the complete tripartite graph $K_{r,s,t}$ as a star complement are made. We study the maximal regular graphs which have $K_{r,s,t}$ as a star complement for eigenvalue $\mu$. The results include a complete analysis of the regular graphs which have $K_{n,n,n}$ as a star complement for $\mu =1$. It turns out that some well-known strongly regular graphs are uniquely determined by such a star complement.