Regular and Maximal Graphs with Prescribed Tripartite Graph as a Star Complement.

Let G be a graph of order n and μ be an adjacency eigenvalue of G with multiplicity k ≥ 1. A star complement H for μ in G is an induced subgraph of G of order n − k with no eigenvalue μ, and the subset X = V(G − H) is called a star set for μ in G. The star complement provides a strong link between graph structure and linear algebra. In this paper, the authors characterize the regular graphs with K2,2,s (s ≥ 2) as a star complement for all possible eigenvalues, the maximal graphs with K2,2,s as a star complement for the eigenvalue μ = 1, and propose some questions for further research. [ABSTRACT FROM AUTHOR]