Spectral Radius of Graphs

By Dragan Stevanovic

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

• Language: English
• Publisher: Academic Press
• Release date: Oct 13, 2014
• ISBN: 9780128020975

Book preview

Spectral Radius of Graphs

First Edition

Dragan Stevanović

Table of Contents

Cover image

Title page

Copyright

Dedication

Preface

Chapter 1: Introduction

1.1 Graphs and Their Invariants

1.2 Adjacency Matrix, its Eigenvalues, and its Characteristic Polynomial

1.3 Some Useful Tools from Matrix Theory

Chapter 2: Properties of the Principal Eigenvector

2.1 Proportionality Lemma and the Rooted Product

2.2 Principal Eigenvector Components Along a Path

2.3 Extremal Components of the Principal Eigenvector

2.4 Optimally Decreasing Spectral Radius By Deleting Vertices or Edges

2.5 Regular, Harmonic, and Semiharmonic Graphs

Chapter 3: Spectral Radius of Particular Types of Graph

3.1 Nonregular Graphs

3.2 Graphs with a Given Degree Sequence

3.3 Graphs with A Few Edges

3.4 Complete Multipartite Graphs

Chapter 4: Spectral Radius and Other Graph Invariants

4.1 Selected Autographix Conjectures

4.2 Clique Number

4.3 Chromatic Number

4.4 Independence Number

4.5 Matching Number

4.6 The Diameter

4.7 The Radius

4.8 The Domination Number

4.9 Nordhaus-Gaddum Inequality for the Spectral Radius

Bibliography

Index

Copyright

Academic Press is an imprint of Elsevier

32 Jamestown Road, London NW1 7BY, UK

525 B Street, Suite 1800, San Diego, CA 92101-4495, USA

225 Wyman Street, Waltham, MA 02451, USA

The Boulevard, Langford Lane, Kidlington, Oxford OX5 1GB, UK

Copyright © 2015 Elsevier Inc. All rights reserved.

No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or any information storage and retrieval system, without permission in writing from the publisher. Details on how to seek permission, further information about the Publisher's permissions policies and our arrangements with organizations such as the Copyright Clearance Center and the Copyright Licensing Agency, can be found at our website: www.elsevier.com/permissions.

This book and the individual contributions contained in it are protected under copyright by the Publisher (other than as may be noted herein).

Notices

Knowledge and best practice in this field are constantly changing. As new research and experience broaden our understanding, changes in research methods, professional practices, or medical treatment may become necessary.

Practitioners and researchers must always rely on their own experience and knowledge in evaluating and using any information, methods, compounds, or experiments described herein. In using such information or methods they should be mindful of their own safety and the safety of others, including parties for whom they have a professional responsibility.

To the fullest extent of the law, neither the Publisher nor the authors, contributors, or editors, assume any liability for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions, or ideas contained in the material herein.

British Library Cataloguing in Publication Data

A catalogue record for this book is available from the British Library

Library of Congress Cataloging-in-Publication Data

A catalog record for this book is available from the Library of Congress

ISBN: 978-0-12-802097-5

For information on all Academic Press publications visit our web site at store.elsevier.com

Dedication

To my wife Sanja and to my mentor Dragoš, both of whom, indepen-dently of each other, forced me to write this book

Preface

Dragan Stevanović, Niš & Leipzig

The aim of this book is to provide an overview of important developments on the spectral radius λ1 of adjacency matrix of simple graphs, obtained in the last 10 years or so. Most of the presented results are related to the Brualdi-Solheid problem [24], which asks to characterize graphs with extremal values of the spectral radius in a given class of graphs. As a careful reader will easily find out, this usually means characterizing graphs with the maximum spectral radius—prevailing reason being that the Rayleigh quotient, the basic building block of most proofs, allows one to check whether the spectral radius has increased after transforming a graph, but not whether it has decreased. Despite the scarcity of lemmas on the decrease of the spectral radius, increase of interest in graphs with the minimum spectral radius is motivated by the recently discovered relation [156]

between the epidemic threshold τc for the effective infection rate of a SIS-type network infection and the network's spectral radius. As the network becomes virus-free in the steady state if the effective infection rate is smaller than τc, the task of constructing a more resistant network obviously translates to the task of constructing a network with λ1 as small as possible, giving impetus to the minimum part of the Brualdi-Solheid problem.

The book is primarily intended for a fellow research mathematician, aiming to make new contributions to the spectral radius of graphs. The focus of presentation is not only on the overview of recent results, but also on proof techniques, conjectures, and open problems. For the impatient reader, perhaps the best starting points are the entries conjecture and open problem in the index at the end of the book. Otherwise, Chapter 2 is devoted to the study of properties of the components of the principal eigenvector corresponding to λ1 that will be used in several occasions later in the book. Chapters 3 and 4 deal with the instances of the Brualdi-Solheid problem. Chapters 3 presents the results on the spectral radius of graphs belonging to standard graph classes, such as graphs with a given degree sequence or planar graphs. On the other hand, graph classes in Chapters 4 are mostly defined as the set of graphs having the same value of an integer-valued graph invariant, such as the diameter or the domination number.

The book is reasonably self-contained, with necessary preliminary results collected in a short, introductory chapter, but do note that it assumes some prior familiarity with graph theory (more) and linear algebra (less). It could be used in teaching, as part of a beginning graduate course or an advanced undergraduate course, including also courses within the research experience for undergraduates programs, but do also note that it lacks exercises (unless you treat conjectures and open problems as exercises).

I hope it is understandable that in a book of this size, one cannot possibly cover all the interesting new developments in the theory of graph spectra (and not even everything that has been published on the spectral radius of graphs!) in the last 10 years or so. For the reader looking forward to expand his/her knowledge of graph spectra, some further reading may be suggested. Results on the spectral properties of directed graphs are well covered in a survey paper by Brualdi [22]. Nikiforov has surveyed his results on extremal spectral graph theory [114], although some of his results are covered here as well. Results on the spectral radius of weighted graphs are more oriented toward the spectral theory of nonnegative matrices than to graph theory; the reader is, thus, referred to Chapter 6 of Friedland's manuscript on matrices [63]. If the reader is looking for a textbook covering a wider array of topics in spectral graph theory, then good choices are the books by Cvetković et al. [47], by Van Mieghem [155], or by Brouwer and Haemers [21].

At the end, I would like to acknowledge kind hospitality of the Max Planck Institute for Mathematics in Sciences in Leipzig during the final stages of writing this book. I am grateful to Türker Biyikoğlu, Josef Leydold, Sebastian Cioabă, and Kelly Thomas for permissions to use some of the proofs from [17, 31, 33, 64] without significant change. I am also very much grateful to my family—Sanja, Djordje, and Milica—for all their love, support, and patience while this book was being materialized from an idea to a reality.

June 2014

References

[17] Biyikoğlu T, Leydold J. Graphs with given degree sequence and maximal spectral radius. Electron J Comb. 2008;15:#R119.

[21] Brouwer AE, Haemers WH. Spectra of graphs. New York: Springer; 2012.

[22] Brualdi RA. Spectra of digraphs. Linear Algebra Appl. 2010;432:2181–2213.

[24] Brualdi RA, Solheid ES. On the spectral radius of complementary acyclic matrices of zeros and ones. SIAM J Algebra Discrete Method. 1986;7:265–272.

[31] Cioabă SM. The spectral radius and the maximum degree of irregular graphs. Electron J Comb. 2007;14:#R38.

[33] Cioabă SM, Gregory DA. Principal eigenvectors of irregular graphs. Electron J Linear Algebra. 2007;16:366–379.

[47] Cvetković D, Rowlinson P, Simić S. An introduction to the theory of graph spectra. New York: Cambridge University Press; 2009.

[63] Friedland S. Matrices. http://homepages.math.uic.edu/~friedlan/bookm.pdf. Cited 26 June 2014.

[64] Friedman J. The spectra of infinite hypertrees. SIAM J Comput. 1991;20:951–961.

[114] Nikiforov V. Some new results in extremal graph theory. In: Chapman R, ed. Cambridge: Cambridge University Press; 2011:141–182. Surveys in combinatorics 2011.

[155] Van Mieghem P. Graph spectra for complex networks. New York: Cambridge University Press; 2011.

[156] Van Mieghem P, Omić J, Kooij RE. Virus spread in networks. IEEE/ACM Trans Netw. 2009;17:1–14.

---

"To view the full reference list for the book, click here"

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 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

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

Graph G is said to be d-regular graph, or just regular, if all of its vertices have degree equal to d.

of vertices from V , 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.,

The diameter D and the radius r of G are then defined as

is a subgraph of G = (V,E, we say that H is the spanning subgrah of G, 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, 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