Advanced Graph Theory and Combinatorics

Michel Rigo

• Publisher: Wiley-ISTE
• Year: 2016
• ISBN:
  9781119058649
• Edition: 1
• Topic: Computer Science
• Subtopic: Systems Architecture
• Index: Computer Science

Advanced Graph Theory focuses on some of the main notions arising in graph theory with an emphasis from the very start of the book on the possible applications of the theory and the fruitful links existing with linear algebra. The second part of the book covers basic material related to linear recurrence relations with application to counting and the asymptotic estimate of the rate of growth of a sequence satisfying a recurrence relation.

1
A First Encounter with Graphs

1.1. A few definitions

There is not much fun in listing basic definitions about graphs (this is quite a bad introduction to start with!) but if we seek a rigorous presentation of results and proofs, then we cannot avoid giving accurate definitions of the objects that we will manipulate, but hopefully nice examples will also come quickly. In this book, we assume that the reader has a basic (or, at least a naive) knowledge of sets and operations on them.

As usual in mathematics, a pair (u, v) made up of two elements is implicitly assumed to be ordered: it has a first component u and a second component v. It has to be compared with a set with two elements u and v denoted by {u, v}. A set does not carry any ordering information about its elements. In particular, if u ≠ v, then we can build two pairs but a single set: (u, v) ≠ (v, u) and {u, v} = {v, u}. If S is a finite set, we will write #S to denote the number of elements in S, i.e. the cardinality of S. We can also find the notation |S| but we will use it to denote lengths of paths.

1.1.1. Directed graphs

DEFINITION 1.1.– Let V be an arbitrary set. A directed graph, or digraph, is a pair G = (V, E) where E is a subset of the Cartesian product V × V, i.e. E is a set of pairs of elements in V. The elements of V are the vertices of G – some authors also use the term nodes – and the elements of E are the edges, also called oriented edges or arcs¹, of G. An edge of the form (v, v) is a loop on v. Another way to express that E is a subset of V × V is to say that E is a binary relation over V. If either (u, v) or (v, u) belongs to E, the vertices u and v are adjacent. If neither (u, v) nor (v, u) belong to E, then u and v are independent. Given a digraph G, the set of vertices (respectively of edges) of G is denoted by V(G) (respectively E(G)).

The vast majority of the graphs that we will encounter are finite meaning that the set V of vertices is finite, and thus E contains at most (#V)² edges.

REMARK 1.2.– It is common to speak of the order of G for #(V(G)) and the size of G for #(...

Table of contents

• Cover
• Table of Contents
• Dedication
• Title
• Copyright
• Foreword
• Introduction
• 1 A First Encounter with Graphs
• 2 A Glimpse at Complexity Theory
• 3 Hamiltonian Graphs
• 4 Topological Sort and Graph Traversals
• 5 Building New Graphs from Old Ones
• 6 Planar Graphs
• 7 Colorings
• 8 Algebraic Graph Theory
• 9 Perron–Frobenius Theory
• 10 Google’s Page Rank
• Bibliography
• Index
• End User Licence Agreement