Eigenvectors of Graph-Laplace-Operators


Type Research Project

Funding Bodies
  • Austrian Science Fund

Duration May 1, 2000 - April 30, 2003

  • Mathematical Methods in Statistics AE (Former organization)

Tags

Press 'enter' for creating the tag
  • Biyikoglu, Türker (Former researcher)
  • Gleiss, Petra (Former researcher)
  • Hordijk, Wim (Former researcher)
  • Leydold, Josef (Details) Project Head
 

Abstract (German)

Die Grundlagen der spektralen Graphentheorie wurden bereits in den 1950er und 1960er Jahren gelegt. Seit damals gehoeren spektrale Methoden zu den Standardtechniken der (algebraischen) Graphentheorie. Die Eigenwerte von Graphen, meist definiert als die Eigenwerte der Adiazenzmatrix, haben waehrend der letzten 30 Jahre gewisse Aufmerksamkeit zum Charakterisieren von Graphenklassen und zur Herleitung von Schranken von Graphparametern wie Durchmesser, chromatische Zahl, Zusammenhang, etc. erhalten.<BR>
In letzter Zeit hat sich das Interesse weg vom Spektrum der Adiazenzmatrix hin zum Spektrum des eng verwandten Laplace-Operators verschoben. Die Eigenvektoren von Graphen allerdings wurden nur selten untersucht. Im Rahmen des Projekts sollen daher die geometrischen Eigenschaften von Eigenfunktionen des diskreten Laplace-Operators in Abhaengigkeit von deren Lage im Spektrum und in Abhaengigkeit von der Struktur des zugrundeliegenden Graphen untersucht werden.


Abstract (English)

The foundations of spectral graph theory were laid in the fifties and sixties. Since then, spectral methods have become standard techniques in (algebraic) graph theory.
The eigenvalues of graphs, most often defined as the eigenvalues of the adjacency matrix, have received much attention over the last thirty years as a means of characterizing classes of graphs and for obtaining bounds on properties such as the diameter, girth, chromatic number, connectivity, etc. More recently, the interest has shifted somewhat from the adjacency spectrum to the spectrum of the closely related graph Laplacian. The eigenvectors of graphs, however, have received only sporadic attention on their own. We investigate the geometric features of the eigenfunctions of discrete Laplacian operators depending on their location in the spectrum and depending on the structure of the underlying graph.

Partners

Publications

Book (monograph)

2007 Biyikoglu, Türker, Leydold, Josef, Stadler, Peter F. 2007. Laplacian Eigenvectors of Graphs: Perron-Frobenius and Faber-Krahn Type Theorems. Berlin: Springer. (Details)

Journal article

2004 Biyikogu, T., Hordijk, W., Leydold, J., Pisanski, T., Stadler, P. F.. 2004. Graph Laplacians, Nodal Domains, and Hyperplane Arrangements. Linear Algebra and its Applications, 390: 155-174 open access (Details)
2003 Biyikoglu, T.. 2003. A Discrete Nodal Domain Theorem for Trees. Linear Algebra and its Applications, 360, 197-205 (Details)
  Gleiss, P. M., Leydold, J., Stadler, P. F.. 2003. Circuit Bases of Strongly Connected Digraphs. Discussiones Mathematicae: Graph Theory 23: 41-260 (Details)
2002 Leydold, J.. 2002. The Geometry of Regular Trees with the Faber-Krahn Property. Discrete Mathematics 245 (1-3): 155-172 (Details)

Paper presented at an academic conference or symposium

2004 Leydold, J.. 2004. Faber-Krahn Type Inequalities for Trees. 19th MATH/CHEM/COMP 2004, Dubrovnik, Croatia, 21.06.- 26.06.2004 (Details)
  Leydold, J.. 2004. The Klobürsteltheorem. 19th TBI Winterseminar, ''Computational Mathematics and Theoretical Biology'', Bled, Slovenia, 22.02.-28.02.2004 (Details)
2003 Leydold, J.. 2003. Discrete Schrödinger Operators and Nodal Domain Theorems. MATH/CHEM/COMP, Dubrovnik, Croatia, 23.06.-28.06.2003 (Details)
2002 Leydold, J.. 2002. Sign Pattern of Graph Eigenvectors and Hyperplane Arrangements. 16th LL-Seminar on Graph Theory, Vienna, Austria, 25.04. -28.04.2002 (Details)
2001 Biyikoglu, T.. 2001. The number of sign graphs of an eigenvector of a tree. Recent Trends in Graph Theory, Bled, September (Details)

Working/discussion paper, preprint

2003 Biyikoglu, T.. 2003. Rank and number of nodal domains of cographs. Institut für Statistik, WU Wien (Details)
2002 Biyikoglu, T., Hordijk, W., Leydold, J., Pisanski, T., Stadler, P. F.. 2002. Graph Laplacians, Nodal Domains, and Hyperplane Arrangements. Institut für Statistik, WU Wien (Details)
2001 T. Biyikoglu. 2001. Forcibly cograph-graphic sequences. Preprint (Details)

Dissertation

2003 Biyikoglu, T.. 2003. Graph Laplacians and Nodal Domains. Dissertation, Universität Wien (Details)

Unpublished lecture

2003 Leydold, J.. 2003. A Faber-Krahn-type inequality for regular trees. Max Planck Institut für Mathematik in den Naturwissenschaften, Leipzig, Germany, February (Details)

Classification

  • 1104 Applied mathematics (Details)

Expertise

  • Graph Laplacian
  • graph theory