On simply structured bases of graph eigenspaces [Elektronische Ressource] / Torsten Sander

On Simply Structured Bases of GraphEigenspacesTorsten SanderHabilitationsschriftvorgelegt bei derFakult¨at fu¨r Mathematik/Informatik und Maschinenbauder Technischen Universit¨at ClausthalOktober 2008Contents IContents1 Introduction 12 Basics 73 General criteria 114 Trees 134.1 The FOX algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134.2 FOX on trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184.3 Storing FOX vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . 284.4 Gaussian elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.5 Partitioning trees by eigenvectors . . . . . . . . . . . . . . . . . . . . 324.5.1 Tree eigenvector decomposition . . . . . . . . . . . . . . . . . 334.5.2 Tree eigenvector composition. . . . . . . . . . . . . . . . . . . 434.5.3 Tree pattern matrices . . . . . . . . . . . . . . . . . . . . . . . 444.6 Eigenspace bases for eigenvalues 1 and−1 . . . . . . . . . . . . . . . 464.6.1 {1,−1} eigenvectors for eigenvalue 1 . . . . . . . . . . . . . . 474.6.2 {0,1,−1} eigenvectors for eigenvalue 1 . . . . . . . . . . . . . 485 Unicyclic graphs 515.1 Uncracked cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535.2 Cracked cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.3 Algorithmic, algebraic and structural characterisations . . . . . . . . 646 Distance powers of paths and circuits 676.1 Path distance powers . . . . . . .