7 - Star partitions

Summary

In this chapter we consider two important concepts: star bases and their combinatorial counterpart star partitions. These concepts were introduced recently in [CvRSl] as a means of extending spectral methods in graph theory, and they provide a strong link between graphs and linear algebra. This connection is promising in that it not only reflects the geometry of eigenspaces but also extends to combinatorial aspects such as matching theory. Star bases were originally introduced as a means of investigating the complexity of the graph isomorphism problem (Chapter 8), but it turned out that the direct relation between graph structure and the underlying star partitions could be exploited to advantage. In particular, there are connections with dominating sets and implications for cubic graphs, and these are two of the topics discussed here.

Introduction

A graph is determined by its eigenvalues and eigenspaces, but not in general by its eigenvalues and angles. In seeking further algebraic invariants we may look to bases of eigenspaces, but of course for eigenspaces of dimension greater than 1 there is not a natural choice of basis. We can however focus our attention on star bases, which as we shall see are related to the geometry of finite-dimensional Euclidean spaces. The key notion which underlines star bases, and which is of wider interest as well, is that of a star partition. In this section we introduce both star partitions and star bases, and prove that they exist for any graph (indeed, for any real symmetric matrix).