Regular graphs with a cycle as a star complement

Abstract

Let G be an n-vertex graph having an eigenvalue µ of multiplicity k. A star complement for µ in G is an induced subgraph H with n − k vertices, such that µ is not its eigenvalue. In the case when H is a t-vertex cycle Ct with t ≥ 3, it is shown that G is regular if and only if µ ∈ {3, 1, 0, −1, −2}. For µ = 3 and µ = 1, G is the complete graph K4 and the Petersen graph, respectively. For µ ∈ {0, −1}, a structural characterization of infinite families of graphs that appear in the role of G is given,and their existence is shown. The obtained results, together with the result of [F. K. Bell, Linear Algebra Appl. 296 (1999) 15–25] concerning µ = −2, establish a complete characterization of regular graphs having Ct as a star complement for some eigenvalue