John Wiley - Advanced Graph Theory and Combinatorics

1. 1 A First Encounter with Graphs
2. 3 Hamiltonian Graphs
3. 4 Topological Sort and Graph Traversals
4. 6 Planar Graphs
5. 7 Colorings
6. 10 Googles Page Rank

1. 1 A First Encounter with Graphs
2. 2 A Glimpse at Complexity Theory
3. 3 Hamiltonian Graphs
4. 4 Topological Sort and Graph Traversals
5. 5 Building New Graphs from Old Ones
6. 6 Planar Graphs
7. 7 Colorings
8. 8 Algebraic Graph Theory
9. 9 PerronFrobenius Theory
10. 10 Googles Page Rank

Series Editor

Valrie Berth

Michel Rigo

First published 2016 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd
27-37 St Georges Road
London SW19 4EU
UK

www.iste.co.uk

John Wiley & Sons, Inc.
111 River Street
Hoboken, NJ 07030
USA

www.wiley.com

ISTE Ltd 2016

The rights of Michel Rigo to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2016953238

British Library Cataloguing-in-Publication Data

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

ISBN 978-1-84821-616-7

To Christelle, Aurore and Maxime

The book content reflects the (good) taste of the author for solid mathematical concepts and results that have exciting practical applications. It is an excellent textbook that should appeal to students and instructors for its very clear presentation of both classical and more recent concepts in graph theory.

Vincent BLONDEL

Professor of Applied Mathematics, University of Louvain
September 2016

This book is a result of lecture notes from a graph theory course taught at the University of Lige since 2005. Through the years, this course evolved and lectures were given at different levels ranging from second-year undergraduates in mathematics to students in computer science entering masters studies. It was therefore quite challenging to find a suitable title for this book.

I hope that the reader will not feel cheated by the title (which is always tricky to choose). In some aspects, the material is rather elementary: we will start from scratch and present basic results on graphs such as connectedness or Eulerian graphs. In the second part of the book, we will analyze in great detail the strongly connected components of a digraph and make use of PerronFrobenius theory and formal power series to estimate asymptotics on the number of walks of a given length between two vertices. Topics with an algebraic or a combinatorial flavor such as Ramsey numbers, introduction to RobertsonSeymour theorem or PageRank can be considered as more advanced.

In the history of mathematics, we often mention the seven bridges of Knigsberg problem as the very first problem in graph theory. It was studied by the famous mathematician L. Euler in 1736. It took two centuries to develop and build a complete theory from a few scattered results. Probably the first book on graphs is Theorie der endlichen und unendlichen Graphen [KN 90] written by the Hungarian mathematician D. Knig in 1936, a student of J. Krschk and H. Minkowski. In the middle of the 20th Century, graph theory matured into a well-defined branch of discrete mathematics and combinatorics. We observe many mathematicians turning their attention to graph theory with books by C. Berge, N. Biggs, P. Erds, C. Kuratowski, W. T. Tutte, K. Wagner, etc. We have seen an important growth during the past decades in combinatorics because of the particular interactions existing with optimization, randomized algorithms, dynamical programming, ergodic or number theory, theoretical computer science, computational geometry, molecular biology, etc. On MathSciNet, if you look for research papers with a Primary Mathematics Subject Classification equal to 05C (which stands for graph theory and is divided into 38 subfields ranging from planar graphs to connectivity, random walks or hypergraphs), then we find for the period 20112015 between 3, 300 and 3, 700 papers published every single year.

In less than a century, many scientists and entrepreneurs have seen the importance of graph theory in real-life applications. In a recent issue of Wired magazine (March 2014), we can read an article entitled Is graph theory a key to understanding big data? by R. Marsten. Let us quote his conclusion: The data that we have today, and often the ways we look at data, are already steeped in the theory of graphs. In the future, our ability to understand data with graphs will take us beyond searching for an answer. Creating and analyzing graphs will bring us to answers automatically. Later, in the same magazine (May 2014), E. Eifrem wrote: Were all well aware of how Facebook and Twitter have used the social graph to dominate their markets, and how Facebook and Google are now using their Graph Search and Knowledge Graph, respectively, to gear up for the next wave of hyper-accurate and hyper-personal recommendations, but graphs are becoming very widely deployed in a host of other industries.

This book reflects the tastes of the author but also includes some important applications such as Googles PageRank. It is only assumed that the reader has a working knowledge of linear algebra. Nevertheless, all the definitions and important results are given for the sake of completeness. The aim of the book is to provide the reader with the necessary theoretical background to tackle new problems or to easily understand new concepts in graph theory. Algorithms and complexity theory occupy a very small portion of the book (mostly in the first chapters).

Many other books on graphs do exist and the reader should not limit himself or herself to a single source. The Internet is also a formidable resource. Even if we have to be cautious when looking for information on the Web, Wikipedia contains a wealth of relevant information (but keep a critical eye). The present book starts with some unavoidable general material, then moves on to some particular topics with a combinatorial flavor. Powers of the adjacency matrix and Perron theory have a predominant role. The reader could probably start with this book and then move to [BRU 11] as a good companion to get a deeper knowledge of the links between linear algebra and graphs. See also [BAP 14] or the classical [GOD 01] in algebraic graph theory. Similarly, a comprehensive presentation of PageRank techniques can be found in [LAN 06]. The authors of that book, A. Langville and C. D. Meyer, also specialized in ranking techniques (see [LAN 12]). Another general reference discussing partially the same topics as here and I do hope, with the same philosophy is by R. Diestel where much more material and a particular emphasis on infinite graphs may be found. The present book is smaller and is thus well suited for readers who do not want to spend too much time on a specialized topic.