Graph and Network Theory: An Applied Approach using Mathematica®

Contents
Preface
	About this book
	Organisation of material in the book
		Part 1: Topics in network optimisation
		Part 2: Topics in classical graph theory
		Part 3: Topics in modern graph theory
	The intended audience
	Notation
	Acknowledgements
	Invitation
List of Algorithms
List of Biographical Notes
PART 1 Topics in network optimisation
	Chapter 1 An introduction to graphs
		1.1 Introduction
		1.2 What is a graph?
		1.3 Special graphs
		1.4 Operations on graphs
		1.5 Degree sequences
		1.6 Isomorphisms
		1.7 Directed graphs
		1.8 Representing a (di)graph on a computer
		1.9 Multigraphs and pseudographs
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 2 Graph connectedness
		2.1 Introduction
		2.2 Connected graphs
		2.3 Distance in graphs
		2.4 Cut-vertices and bridges
		2.5 Directed graphs
		2.6 Further study of connectivity in graphs
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 3 Algorithmic complexity
		3.1 Introduction
		3.2 "Big O" notation
		3.3 A classification scheme for decision problems
		3.4 Polynomial-time reducibility and ness
		3.5 Decision problems vs. computation problems
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 4 Optimal paths
		4.1 Introduction
		4.2 Distance in weighted graphs
		4.3 Shortest paths in weighted graphs
			4.3.1 Dijkstra's algorithm
			4.3.2 Floyd’s algorithm
		4.4 Longest paths in weighted digraphs
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 5 Trees
		5.1 Introduction
		5.2 Properties of trees
		5.3 Constructing minimum spanning trees
			5.3.1 Kruskal's algorithm
			5.3.2 Prim's algorithm
		5.4 Rooted trees
		5.5 Depth-first tree searches
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 6 Location problems
		6.1 Introduction
		6.2 The centre of a graph
		6.3 The median of a graph
		6.4 General centres and medians
		6.5 Absolute centres and medians
		6.6 General absolute centres and medians
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 7 Maximum flow networks
		7.1 Introduction
		7.2 Preliminary concepts
		7.3 The max-flow min-cut theorem
		7.4 The max-flow min-cut algorithm
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 8 Minimum-cost network flows
		8.1 Introduction
		8.2 Network flow and linear programming theory
		8.3 Basic feasible solutions
		8.4 The network simplex algorithm
		Exercises
		Computer exercises
		Projects
		Further reading
PART 2 Topics in classical graph theory
	Chapter 9 Matchings
		9.1 Introduction
		9.2 Maximum matchings
		9.3 Vertex covers
		9.4 Tutte's theorem
		9.5 The Tutte-Berge formula
		9.6 The binding number of a graph
		9.7 Matching algorithms for bipartite graphs
			9.7.1 Method I: Network flows
			9.7.2 Method II: Augmenting paths
		9.8 A matching algorithm for general graphs
		9.9 A weighted matching algorithm
			9.9.1 Linear programming background
			9.9.2 The maximum weight matching problem
			9.9.3 Outline of the maximum weight matching algorithm
			9.9.4 A worked example
		Exercises
		Computer exercises
		Projects
		Suggestions for further background reading
		Further reading
	Chapter 10 Eulerian graphs
		10.1 Introduction
		10.2 Finding eulerian circuits and trails
		10.3 The Chinese postman problem
		10.4 Other postman problems
		10.5 Eulerian digraphs
		10.6 Fleury's algorithm for digraphs
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 11 Hamiltonian graphs
		11.1 Introduction
		11.2 Which graphs are hamiltonian?
		11.3 The closure function
		11.4 The travelling salesman problem
			11.4.1 The nearest-neighbour heuristic
			11.4.2 A lower bound on TSP solutions
			11.4.3 Instances of the TSP satisfying the triangle inequality
			11.4.4 Christofides' algorithm
		11.5 Almost traceability and almost hamiltonicity
			11.5.1 Hypotraceability of graphs
			11.5.2 Hypohamiltonicity of graphs
			11.5.3 Hypotraceability and hypohamiltonicity of digraphs
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 12 Graph connectivity
		12.1 Introduction
		12.2 Cuts and separating sets
		12.3 Blocks
		12.4 Connectivity and edge connectivity
		12.5 Menger's Theorem
			12.5.1 The vertex form of Menger's Theorem
			12.5.2 The edge form of Menger’s Theorem
		12.6 Computing the connectivity of a graph
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 13 Planarity
		13.1 Introduction
		13.2 Properties of planar graphs
		13.3 Which graphs are planar?
			13.3.1 Contractions, subdivisions and graph minors
			13.3.2 Kuratowski's characterisation of planar graphs
			13.3.3 Wagner's characterisation of planar graphs
			13.3.4 A planarity testing algorithm
		13.4 The crossing number of a graph
		13.5 Other parameters related to planarity
			13.5.1 The rectilinear crossing number
			13.5.2 The thickness of a graph
			13.5.3 The coarseness of a graph
		13.6 Embedding on surfaces other than the plane
			13.6.1 The genus of a surface
			13.6.2 The generalised crossing number of a graph
			13.6.3 The genus of a graph
		13.7 The Robertson-Seymour theorems
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 14 Graph colouring
		14.1 Introduction
		14.2 Vertex colouring
			14.2.1 k-Colourability
			14.2.2 Criticality and the chromatic number of a graph
			14.2.3 Other bounds on the chromatic number of a graph
			14.2.4 Computing good vertex colourings heuristically
			14.2.5 An exact algorithm for vertex colouring
		14.3 Edge colouring
			14.3.1 The chromatic index of a graph
			14.3.2 Criticality with respect to X'(G)
			14.3.3 Computing the chromatic index of a graph
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 15 Oriented graphs
		15.1 Introduction
		15.2 Strong orientations
		15.3 Tournaments
		15.4 Higher-order rankings in tournaments
		15.5 Almost traceable and almost hamiltonian orient digraphs
		Exercises
		Computer exercises
		Projects
		Further reading
PART 3 Topics in modern graph theory
	Chapter 16 Domination in graphs
		16.1 Introduction
		16.2 The domination number
			16.2.1 Minimal dominating sets
			16.2.2 Bounds on the domination number
			16.2.3 Vizing's Conjecture
			16.2.4 Nordhaus-Gaddum type bounds
			16.2.5 NP-completeness of the domination problem
			16.2.6 A polynomial-time tree domination algorithm
			16.2.7 The upper domination number
		16.3 The independent domination number
			16.3.1 The domination inequality chain
			16.3.2 <γ,i>-graphs
			16.3.3 Domination-perfect graphs
			16.3.4 -graphs
			16.3.5 Bounds for K(1, k)-free graphs
			16.3.6 Bounds in terms of maximum degree
			16.3.7 Bounds relating i and γ
			16.3.8 Bounds relating i and n
			16.3.9 Bounds for bipartite graphs
			16.3.10 Bounds for trees
			16.3.11 Bounds for cubic graphs
			16.3.12 Bounds for regular graphs
			16.3.13 Bounds for triangle-free graphs
			16.3.14 Nordhaus-Gaddum type bounds
		16.4 The irredundance number
			16.4.1 Maximal irredundant sets
			16.4.2 The domination inequality chain revisited
			16.4.3 Irredundance perfect graphs
			16.4.4 Bounds involving the minimum and maximum degrees
		16.5 Total domination
			16.5.1 Minimal total dominating sets
			16.5.2 Bounds on the total domination number
			16.5.3 Bounds for graphs with minimum degree at least two
			16.5.4 Bounds for graphs with minimum degree at least three
			16.5.5 Bounds for graphs with minimum degree at least four
			16.5.6 A heuristic bound
			16.5.7 Summary of bounds
			16.5.8 The upper total domination number
			16.5.9 Total domination edge critical graphs
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 17 Ramsey theory
		17.1 Introduction
		17.2 The classical two-colour Ramsey problem
		17.3 Two-colour extensions
		17.4 The multi-colour Ramsey problem
		17.5 Multipartite Ramsey theory
		17.6 Requirements other than that of a subgraph
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 18 Extremal graph theory
		18.1 Introduction
		18.2 Cycles in graphs
		18.3 Turán's theorem
		18.4 Zarankiewicz numbers
		18.5 Framing numbers
			18.5.1 On cliques and independent sets
			18.5.2 On cliques and bicliques
		18.6 Diameter two graphs of minimum size
		18.7 Diameter two critical graphs of maximum size
		Exercises
		Further reading
	Chapter 19 Graph enumeration
		19.1 Counting labelled graphs
			19.1.1 Labelled simple graphs of specified order and size
			19.1.2 Labelled trees and rooted labelled trees
			19.1.3 Genealogical registers
		19.2 Counting unlabelled trees
			19.2.1 Rooted trees
			19.2.2 Trees that are not rooted
		19.3 Pólya's enumeration theorem
			19.3.1 Permutations
			19.3.2 Permutation groups and (ordered) pair groups
			19.3.3 The cycle index of a permutation group
			19.3.4 The theorem in the context of graph enumeration
		19.4 Using Pólya's theorem to enumerate graphs
			19.4.1 Unlabelled graphs of specified order and size
			19.4.2 Multigraphs of specified order, size and multiplicity
			19.4.3 Unlabelled digraphs of specified order and size
		Exercises
		Computer exercises
		Projects
		Further reading
	Chapter 20 The probabilistic method
		20.1 Introduction
		20.2 Ramsey theory
		20.3 Linearity of expectation
			20.3.1 Bipartite subgraphs
			20.3.2 Hamiltonian paths
			20.3.3 Independent sets
			20.3.4 Dominating sets
		20.4 Random graphs
			20.4.1 Colourings
			20.4.2 Lovász Local Lemma
		Exercises
		Projects
		Further reading
Index
	Subject index
	Author index