Elements of Graph Theory: From Basic Concepts to Modern Developments

Front cover
Front matter
About the authors
Preface
1 Basic concepts
1.1 Non-oriented graphs
1.2 Connected decomposition
1.3 Oriented graphs
1.4 Simple graphs
1.5 Operations on graphs
1.6 Representations of graphs
1.7 Algorithms and complexity theory
1.8 Definition of a graph starting from the incidence function
1.9 Isomorphisms of graphs. Automorphism groups
1.10 Complements: some basic structures
2 Some remarkable graphs
2.1 Bipartite graphs
2.2 Trees and arborescences
2.3 Digraphs with no circuits
2.4 Euler graphs and Hamiltonian graphs
3 (Di)graphs and data structures
3.1 Recursive procedures
3.2 The return of trees and arborescences
3.3 Time complexity of algorithms on binary arborescences
3.4 Back to graphs
3.5 Complements
4 Connectedness and flows in networks
4.1 Vertex-connectedness and edge-connectedness
4.2 2-vertex-connected graphs
4.3 2-edge-connected graphs
4.4 Flows in a network
4.5 Applications of flows in a network
4.6 Complements: Kirchhoff's laws
5 Planar graphs
5.1 Drawings
5.2 Planar graphs
5.3 Maximal planar graphs and polyhedra
5.4 Comparison of embeddings
5.5 Kuratowski's theorem and Wagner's theorem
5.6 Dual graphs
5.7 Crossings, thickness and genus of a graph
5.8 Elements of plane topology and geometry
6 Graphs and linear algebra
6.1 Graphs and matrices
6.2 Vector spaces and graphs
6.3 Circulation
6.4 Planar graphs
6.5 Background in linear algebra
7 Colouring
7.1 Vertex colourings
7.2 Edge colourings
7.3 Graph morphisms
7.4 Perfect graphs
7.5 List colourings
7.6 Chromatic polynomials
8 Matching and factorisation
8.1 Definitions and first properties
8.2 Matchings in bipartite graphs
8.3 Matchings in arbitrary graphs
8.4 Factorisation
8.5 Some applications of matchings
8.6 Generalisation of the notion of factor
9 Graphs and group theory
9.1 Permutation groups
9.2 The automorphism group of a graph and of its line-graph
9.3 Coloured Cayley graphs
9.4 König's problem
9.5 Group actions
9.6 Transitive graphs
10 Spectral theory and applications
10.1 The spectrum of a graph
10.2 The graph Laplacian
10.3 The spectra of regular graphs
10.4 Ramanujan graphs
10.5 Non-oriented Cayley graphs
11 Random graphs
11.1 Models of random graphs
11.2 Statistical properties of graphs
11.3 Properties asymptotically satisfied by almost all graphs
11.4 Main structural properties of random graphs
11.5 Phase transition
11.6 Summary of the steps of the evolution of $\mathcal{G}(n;p)$
11.7 Some remarks
11.8 Background in probability theory
12 Weighted graphs and their applications
12.1 Weighted graphs
12.2 The Laplacian in physics
12.3 From physics to graphs: the harmonic Laplacian
12.4 Dirichlet's problem
12.5 Random walks in graphs
12.6 Electrical networks
12.7 Cheeger's inequality
13 Other perspectives
13.1 Tutte polynomials
13.2 Ramsey theory
13.3 Matroids
13.4 Hypergraphs
References
Index
Symbols used
Back cover