Star Sets in Regular Graphs

Abstract

Let $G$ be a finite graph and let $\mu$ be an eigenvalue of $G$ of multiplicity $k$. A star set for $\mu$ may be characterized as a set $X$ of $k$ vertices of $G$ such that $\mu$ is not an eigenvalue of $G–X$. It is shown that if $G$ is regular then $G$ is determined by $\mu$ and $G–X$ in some cases. The results include characterizations of the Clebsch graph and the Higman-Sims graph.