Spectral Radius of Graphs (eBook)

Dragan Stevanovic (Autor)

eBook Download: PDF | EPUB

2014 | 1. Auflage
166 Seiten
Elsevier Science (Verlag)
978-0-12-802097-5 (ISBN)

Infos

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

Inhalt

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

Textauszug

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 δ for G are defined as

=max?u∈Vdegu,δ=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)∩E, 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 α 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,ω,α,χ,γ,ν

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<j≤n. The complete bipartite graph n1,n2 consists of two disjoint sets of vertices V1, | V1 | = n1, and V2, | V2 | = n2, and all edges v1v2 for v1 ∈ V1 and v2 ∈ V2. The star Sn is a shortcut for the complete bipartite graph K1,n − 1. The complete multipartite graph n1,…,np consists of disjoint sets of vertices Vi, | Vi | = ni,i=1,…,p, and all edges vivj, vi ∈ Vi, vj ∈ Vj, for i ≠ j. The Turan graph n,p≅K⌈n/p⌉,…,⌈n/p⌉,⌊n/p⌋,…,⌊n/p⌋ is the (p + 1)-clique-free graph with the maximum number of edges [151]. The complete split graph CSnp = Kn− p,1,…,1 consists of an independent set of n − p vertices and a clique of p vertices, such that each vertex of the independent set is adjacent to each vertex of the clique.

The coalescence G · H of two graphs G and...

Produkt-Details

• Erscheint lt. Verlag: 13.10.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Algebra
• Themenwelt: Mathematik / Informatik ► Mathematik ► Graphentheorie
• Themenwelt: Technik
• ISBN-10: 0-12-802097-0 / 0128020970
• ISBN-13: 978-0-12-802097-5 / 9780128020975