Stevanovic Spectral Radius of Graphs

1. Auflage 2014
ISBN: 978-0-12-802097-5
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: 6 - ePub Watermark

E-Book, Englisch, 166 Seiten

Spectral Radius of Graphs provides a thorough overview of important results on the spectral radius of adjacency matrix of graphs that have appeared in the literature in the preceding ten years, most of them with proofs, and including some previously unpublished results of the author. The primer begins with a brief classical review, in order to provide the reader with a foundation for the subsequent chapters. Topics covered include spectral decomposition, the Perron-Frobenius theorem, the Rayleigh quotient, the Weyl inequalities, and the Interlacing theorem. From this introduction, the book delves deeper into the properties of the principal eigenvector; a critical subject as many of the results on the spectral radius of graphs rely on the properties of the principal eigenvector for their proofs. A following chapter surveys spectral radius of special graphs, covering multipartite graphs, non-regular graphs, planar graphs, threshold graphs, and others. Finally, the work explores results on the structure of graphs having extreme spectral radius in classes of graphs defined by fixing the value of a particular, integer-valued graph invariant, such as: the diameter, the radius, the domination number, the matching number, the clique number, the independence number, the chromatic number or the sequence of vertex degrees. Throughout, the text includes the valuable addition of proofs to accompany the majority of presented results. This enables the reader to learn tricks of the trade and easily see if some of the techniques apply to a current research problem, without having to spend time on searching for the original articles. The book also contains a handful of open problems on the topic that might provide initiative for the reader's research. - Dedicated coverage to one of the most prominent graph eigenvalues - Proofs and open problems included for further study - Overview of classical topics such as spectral decomposition, the Perron-Frobenius theorem, the Rayleigh quotient, the Weyl inequalities, and the Interlacing theorem

Autoren/Hrsg.

Stevanovic, Dragan

Inhaltsverzeichnis

1;Front Cover;1
2;Spectral Radius of Graphs;4
3;Copyright;5
4;Dedication;6
5;Contents;8
6;Preface;10
7;Chapter 1: Introduction;12
7.1;1.1 Graphs and Their Invariants;12
7.2;1.2 Adjacency Matrix, Its Eigenvalues, and Its Characteristic Polynomial;15
7.3;1.3 Some Useful Tools from Matrix Theory;19
8;Chapter 2: Properties of the Principal Eigenvector;26
8.1;2.1 Proportionality Lemma and the Rooted Product;26
8.2;2.2 Principal Eigenvector Components Along a Path;32
8.3;2.3 Extremal Components of the Principal Eigenvector;39
8.4;2.4 Optimally Decreasing Spectral Radius by Deleting Vertices or Edges;46
8.4.1;2.4.1 Vertex Removal;51
8.4.2;2.4.2 Edge Removal;55
8.5;2.5 Regular, Harmonic, and Semiharmonic Graphs;58
9;Chapter 3: Spectral Radius of Particular Types of Graphs;64
9.1;3.1 Nonregular Graphs;64
9.2;3.2 Graphs with a Given Degree Sequence;73
9.3;3.3 Graphs with a Few Edges;79
9.3.1;3.3.1 Trees;79
9.3.2;3.3.2 Planar Graphs;84
9.4;3.4 Complete Multipartite Graphs;88
10;Chapter 4: Spectral Radius and Other Graph Invariants;98
10.1;4.1 Selected AutoGraphiX Conjectures;98
10.2;4.2 Clique Number;100
10.3;4.3 Chromatic Number;104
10.4;4.4 Independence Number;106
10.5;4.5 Matching Number;109
10.6;4.6 The Diameter;112
10.7;4.7 The Radius;128
10.8;4.8 The Domination Number;136
10.9;4.9 Nordhaus-Gaddum Inequality for the Spectral Radius;151
11;Bibliography;158
12;Index;166

Leseproben

Chapter 1 Introduction
This short, introductory chapter contains definitions and tools necessary to follow the results presented in the forthcoming chapters. We will cover various graph notions and invariants, adjacency matrix, its eigenvalues and its characteristic polynomial, and some standard matrix theory tools that will be used later in proofs. 1.1 Graphs and Their Invariants
A simple graph is the pair G = (V,E) consisting of the vertex set V with n = | V | vertices and the edge set  ?(V2) with m =| E | edges. Often in the literature, n is called the order and m the size of G. Simple graphs contain neither directed nor parallel edges, so that an edge e ? E may be identified with the pair {u, v} of its distinct endvertices u,v ? V. We will write shortly uv for the set {u, v}. We will also use V(G) and E(G) to denote the vertex set and the edge set of G, if they have not been named already. To simplify notation, we will omit graph name (usually G), whenever it can be understood from the context. For a vertex u ? V, the set of its neighbors in G is denoted as u={v?V:uv?E}. The degree of u is the number of its neighbors, i.e., degu = | Nu|. The maximum vertex degree ? and the minimum vertex degree d for G are defined as =max?u?Vdegu,d=minu?Vdegu. Graph G is said to be d-regular graph, or just regular, if all of its vertices have degree equal to d. A sequence :u=u0,u1,…,uk=v of vertices from V such that iui+1 ?E, i=0,…,k-1, is called a walk between u and v in G of length k. Two vertices u,v ? V are connected in G if there exists a walk between them in G, and the whole graph G is connected if there exists a walk between any two of its vertices. The distance d(u,v) between two vertices u, v of a connected graph G is the length of the shortest walk between u and v in G. The eccentricity eccu of a vertex u ? V is the maximum distance from u to other vertices of G,i.e., u=max?v?Vd(u,v). The diameter D and the radius r of G are then defined as =max?u?Veccu,r=min?u?Veccu. Graph =(V',E') is a subgraph of G = (V,E) if '?V and '?E. If '=V, we say that H is the spanning subgrah of G. On the other hand, if '=(V'2)nE, i.e., if H contains all edges of G whose both endpoints are in H, we say that H is the induced subgraph of G. If U is a subset of vertices of G = (V,E), we will use G - U (or just G - u if U = {u}) to denote the subgraph of G induced by V \ U. If F is a subset of edges of G, we will use G - F (or just G - e if F ={e}) to denote the subgraph (V, E \ F). A subset C ? V is said to be a clique in G if uv ? E holds for any two distinct vertices u,v ? C. The clique number ? of G is the maximum cardinality of a clique in G. A subset S ? V is said to be an independent set in G if uv ? E holds for any two distinct vertices u,v ? S. The independence number a of G is the maximum cardinality of an independent set in G. A function f: V ? Z, for arbitrary set Z, is said to be a coloring of G if f(u) ? f(v) whenever u,v ? E. The chromatic number ? is the smallest cardinality of a set Z for which there exists a coloring f: V ? Z. Alternatively, as -1(z),?z ???Z, is necessarily an independent set, the chromatic number ? may be equivalently defined as the smallest number of parts into which V can be partitioned such that any two adjacent vertices belong to distinct parts. A set D of vertices of a graph G is a dominating set if every vertex of V(G) \ D is adjacent to a vertex of S. The domination number ? of G is the minimum cardinality of a dominating set in G. A set M of disjoint edges of G is a matching in G. The matching number v of G is the maximum cardinality of a matching in G. Given two graphs G = (V,E) and '=(V',E'), the function :?V?V' is an isomorphism between G and G' if f is bijection and for each u,v ? Vholds {u,v} ? E if and only if { f(u),f(v)} ? E'. If there is an isomorphism between G and G', we say that G and G' are isomorphic and denote it as G?G'. In case G and G' are the one and the same graph, then we have an automorphism. Further, a function i: G ? is a graph invariant if i(G) = i(G') holds whenever G?G'. In other words, the value of i depends on the structure of a graph, and not on the way its vertices are labeled. All the values mentioned above ,m,?,?,D,?,a,?,?,? are examples of graph invariants. Graph theory, actually, represents a study of graph invariants and in this book the focus will be on yet another graph invariant—the spectral radius of a graph, which is defined in the next section. We will now define several types of graphs that will appear throughout the book. The path Pn has vertices 1,…, n and edges of the form {i, i + 1} for i = 1,…, n - 1. The cycle Cn is the graph obtained from Pn by adding edge {n,1} to it. The complete graph Kn has vertices 1,…, n and contains all edges ij for =i