On graphs whose second largest eigenvalue equals 1 - the star complement technique

Abstract

The star complement technique is a spectral tool recently developed for constructing some bigger graphs from their smaller parts, called star complements. Here we first identify among trees and complete graphs those graphs which can be star complements for 1 as the second largest eigenvalue. Using the graphs just obtained, we next search for their maximal extensions, either by theoretical means, or by computer aided search. © 2006 Elsevier Inc. All rights reserved.