## Star sets and related aspects of algebraic graph theory

Let Î¼ be an eigenvalue of the graph G with multiplicity k. A star set corresponding to Î¼ in G is a subset of V(G) such that [x] = k and Î¼ is not an eigenvalue of G – X. It is always the case that the vertex set of G can be partitioned into star sets corresponding to the distinct eigenvalues of G. Such a partition is called a star partition. We give some examples of star partitions and investigate the dominating properties of the set V (G) \ X when Î¼ Îµ {-I, a}.

The induced subgraph H = G – X is called a star complement for Î¼ in G. The Reconstruction Theorem states that for a given eigenvalue Î¼ of G, knowledge of a star complement corresponding to Î¼, together with knowledge of the edge set between X and its complement X, is sufficient to reconstruct G. Pursuant to this we explore the idea that the adjacencies of pairs of vertices in X is determined by the relationship between the H-neighbourhoods of these vertices. We give some new examples of cubic graphs in this context.

For a given star complement H the range of possible values for the corresponding eigenvalue Î¼ is constrained by the condition that Î¼ must be a simple eigenvalue of some one-vertex extension of H, and a double eigenvalue of some two-vertex extension of H. We apply the Reconstruction Theorem to the generic form of a two-vertex extension of H, thereby obtaining sufficient information to construct a graph containing H as a star complement for one of the possible eigenvalues. We give examples of graph characterizations arising in the case where the star complement is (to within isolated vertices) a complete bipartite graph.

http://dspace.stir.ac.uk/bitstream/1893/26690/1/Jackson-thesis.pdf