Graph Laplacians, Nodal Domains, and Hyperplane Arrangements

Biyikoglu, Türker and Hordijk, Wim and Leydold, Josef and Pisanski, Tomaz and Stadler, Peter F. (2002) Graph Laplacians, Nodal Domains, and Hyperplane Arrangements. Preprint Series / Department of Applied Statistics and Data Processing, 44. Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business, Vienna.

Preview

PDF document.pdf Download (962kB)

Abstract

Eigenvectors of the Laplacian of a graph G have received increasing attention in the recent past. Here we investigate their so-called nodal domains, i.e., the connected components of the maximal induced subgraphs of G on which an eigenvector \psi does not change sign. An analogue of Courant's nodal domain theorem provides upper bounds on the number of nodal domains depending on the location of \psi in the spectrum. This bound, however, is not sharp in general. In this contribution we consider the problem of computing minimal and maximal numbers of nodal domains for a particular graph. The class of Boolean Hypercubes is discussed in detail. We find that, despite the simplicity of this graph class, for which complete spectral information is available, the computations are still non-trivial. Nevertheless, we obtained some new results and a number of conjectures. (author's abstract)

Item Type:	Paper
Additional Information:	Published in: Linear Algebra and its Applications 390, pp. 155-174, 2004
Keywords:	graph / graph Laplacian / discrete nodal domain theorem / eigenvectors / hyperplane arrangement / hypercube
Classification Codes:	MSC 58-99, 05C99
Divisions:	Departments > Finance, Accounting and Statistics > Statistics and Mathematics
Depositing User:	Repository Administrator
Date Deposited:	10 Jul 2006 11:53
Last Modified:	22 Oct 2019 00:40
FIDES Link:	https://bach.wu.ac.at/d/research/results/27113/
URI:	https://epub.wu.ac.at/id/eprint/1036

Actions

View Item

Downloads