Laplacian Eigenvectors of Graphs: Perron-Frobenius and by Türker Biyikoğu, Josef Leydold, Peter F. Stadler (auth.)

By Türker Biyikoğu, Josef Leydold, Peter F. Stadler (auth.)

Eigenvectors of graph Laplacians haven't, thus far, been the topic of expository articles and therefore they might appear a shocking subject for a e-book. The authors suggest motivations for this new LNM quantity: (1) There are attention-grabbing sophisticated ameliorations among the houses of suggestions of Schrödinger equations on manifolds at the one hand, and their discrete analogs on graphs. (2) "Geometric" homes of (cost) features outlined at the vertex units of graphs are of sensible curiosity for heuristic optimization algorithms. The remark that the associated fee services of a variety of of the well-studied combinatorial optimization difficulties are eigenvectors of linked graph Laplacians has triggered the research of such eigenvectors.

The quantity investigates the constitution of eigenvectors and appears on the variety of their signal graphs ("nodal domains"), Perron parts, graphs with extremal houses with recognize to eigenvectors. The Rayleigh quotient and rearrangement of graphs shape the most methodology.

Show description

Read or Download Laplacian Eigenvectors of Graphs: Perron-Frobenius and Faber-Krahn Type Theorems PDF

Similar nonfiction_7 books

Collaborative Virtual Environments: Digital Places and Spaces for Interaction

Collaborative digital Environments (CVEs) are on-line electronic areas and areas the place we will be able to be in contact, play jointly and interact, even if we're, geographically talking, worlds aside. we will hang around, current replacement selves, have interaction with sensible and significant items and perform most unlikely manoeuvres.

Dissociative Recombination of Molecular Ions with Electrons

Dissociative Recombination of Molecular Ions with Electrons is a entire choice of refereed papers describing the most recent advancements in dissociative recombination study. The papers are written through the prime researchers within the box. the themes lined contain using microwave afterglows, merged beams and garage jewelry to degree expense coefficients and to spot the goods and their yields.

Extra resources for Laplacian Eigenvectors of Graphs: Perron-Frobenius and Faber-Krahn Type Theorems

Sample text

However, for convenience Fiedler [65] has set v(Kn ) = n − 1. 10. The bound in Thm. 8 can be improved. Kirkland gives a sharp upper bound for the algebraic connectivity in terms of the number n of vertices and the number of cutpoints of the graph, see [112, 116]. There is also a lower bound for the algebraic connectivity. The proof uses a result for symmetric doubly stochastic matrices, see [64]. 11 ([65]). For any graph G with n vertices λ2 (G) ≥ 2 1 − cos Equality holds if and only if G is a path.

There is also a lower bound for the algebraic connectivity. The proof uses a result for symmetric doubly stochastic matrices, see [64]. 11 ([65]). For any graph G with n vertices λ2 (G) ≥ 2 1 − cos Equality holds if and only if G is a path. π e(G) . 11 can be generalized for Laplacians on weighted graphs, see [68]. An eigenfunction affording the second smallest eigenvalue of a graph Laplacian is called a Fiedler vector of G. As mentioned in the introduction, Fiedler vectors have many applications in various fields of application, where they form the basis of heuristic approaches to solve hard combinatorial optimization problems including graph bi-partitioning [146] and spectral clustering [15].

5 The Courant-Herrmann Conjecture A footnote on p. 454 in [44] claims that the nodal domain theorem for manifolds (p. 29) can be generalized in the following way: Any linear combination of the first n eigenfunctions divides the domain, by means of its nodes, into no more than n subdomains. For a proof the reader is referred to Herrmann’s 1932 dissertation in G¨ ottingen. We will refer to this statement as the CourantHerrmann conjecture (CHC). Gladwell and Zhu [82] reported, however, that neither in this work nor in any of Herrmann’s subsequent publications such a result is stated, let alone proved.

Download PDF sample

Rated 4.92 of 5 – based on 15 votes