Graph Therory with Applications

This page

intentionally left

blank

Copyright © 2006 New Age International (P) Ltd., Publishers

Published by New Age International (P) Ltd., Publishers

All rights reserved.

No part of this ebook may be reproduced in any form, by photostat, microfilm,

xerography, or any other means, or incorporated into any information retrieval

system, electronic or mechanical, without the written permission of the publisher.

All inquiries should be emailed to [email protected]

ISBN : 978-81-224-2413-3

PUBLISHING FOR ONE WORLD

NEW AGE INTERNATIONAL (P) LIMITED, PUBLISHERS

4835/24, Ansari Road, Daryaganj, New Delhi - 110002

Visit us at www.newagepublishers.com

I

Dedicated this book Dedicated this book

to

‘Maha Kaali Maata’ ‘Maha Kaali Maata’ ‘Maha Kaali Maata’

This page

intentionally left

blank

PREFACE

This text has been carefully designed for flexible use. It is primarily designed to provide an

introduction to some fundamental concepts in Graph Theory, for under-graduate and post-graduate

students.

Each topic is divided into sections of approximately the same length, and each section is divided

into subsections that form natural blocks of material for teaching. Instructors can easily pace their

lectures using these blocks.

All definitions and theorems in this text are stated extremely carefully so that students will ap￾preciate the precision of language and rigor needed in mathematical sciences. Proofs are motivated and

developed slowly ; their steps are all carefully justified.

The writing style in this book is direct and pragmatic. Precise mathematical language is used

without excessive formalism and abstraction. Care has been taken to balance the mix of notation and

words in mathematical statements.

Over 1500 problems are used to illustrate concepts, related to different topics, and introduce

applications. In most examples, a question is first posed, then its solution is presented with appropriate

details. The applications included in this text demonstrate the utility of Graph Theory, in the solution of

real-world problem. This text includes applications to a wide-variety of areas, including computer

science and engineering.

There are over 1000 exercises in the text with many different types of questions posed. There is

an ample supply of straightforward exercises that develop basic skills, a large number of intermediate

exercises and many challenging exercise sets. Problem sets are stated clearly and unambiguously, and

all are carefully graded for various levels of difficulty.

It will be honest on my part to accept that it is not possible to include everything in one book.

Many people contributed directly or indirectly to the completion of this book. Thanks are due to

my friends who were able to convince me that I should write this book.

I am grateful to my students, who always encouraged me and many times thanked me for writing

this book.

Special thanks to my teachers, who made me realize that I can indeed write a book on “Graph

Theory”. Some pulled me down, some encouraged me and some gave me constructive suggestions. I am

grateful to all of them.

I specially thank my parents, elder brothers, elder sister and maternal uncle, who tolerated me

all along while I devoted my time to completing this book.

I experess my sincere thanks to the Chairman Mr. R.K. Gupta, the Managing Director Mr. Saumya

Gupta, the Marketing Manager Mr. V.R. Babu and Mr. Vincent D. Souza, M/s New Age International (P)

Ltd. Publishers, New Delhi, for their responsible work-done at every level in the publication of the book

with high production standards.

Healthy criticism and suggestions to improve the quality and standards of the text are most

welcome.

Bangalore C. Vasudev

This page

intentionally left

blank

This page

intentionally left

blank

This page

intentionally left

blank

1.10.1 Union 42

1.10.2 Intersection 43

1.10.3 Sum of two graphs 43

1.10.4 Ring sum 43

1.10.5 Product of graphs 44

1.10.6 Composition 44

1.10.7 Complement 45

1.10.8 Fusion 45

1.11 The problem of ramsey 46

1.12 Connected and disconnected graphs 49

1.12.1 Path graphs and cycle graphs 50

1.12.2 Rank and nullity 51

1.13 Walks, paths and circuits 56

1.13.1 Walk 56

1.13.2 Path 57

1.13.3 Circuit 57

1.13.4 Length 58

1.14 Eulerian graphs 62

1.14.1 Euler path 62

1.14.2 Euler circuit 62

1.15 Fleury’s algorithm 72

1.16 Hamiltonian graphs 75

1.17 Dirac’s theorem 76

1.18 Ore’s theorem 78

1.19 Problem of seating arrangement 87

1.20 Traveling salesman problem 88

1.21 K
nigsberg’s bridge problem 90

1.22 Representation of graphs 90

1.22.1 Matrix representation 90

1.22.2 Adjacency matrix 91

1.22.2(a) Representation of undirected graph 91

1.22.2(b) Representation of directed graph 91

1.22.3 Incidence matrix 92

1.22.3(a) Representation of undirected graph 92

1.22.3(b) Representation of directed graph 92

1.22.4 Linked representation 92

Problem Set 1.1 99

(xii)

2. Planar Graphs 108

Introduction 108

2.1 Combinatorial and geometric graphs (representation) 108

2.2 Planar graphs 109

2.3 Kurotowski’s graphs 110

2.4 Homeomorphic graphs 110

2.5 Region 111

2.6 Maximal planar graphs 112

2.7 Subdivision graphs 112

2.8 Inner vertex set 112

2.9 Outer planar graphs 113

2.9.1 Maximal outer planar graph 113

2.9.2 Minimally non-outer planar graph 113

2.10 Crossing number 113

2.11 Bipartite graph 114

2.11.1. Complete bipartite graph 114

2.12 Euler’s formula 116

2.12.1 Three utility problem 126

2.12.2 Kuratowski’s theorem 137

2.13 Detection of planarity of a graph 138

2.14 Dual of a planar graph 144

2.14.1 Uniqueness of the dual 145

2.14.2 Double dual 145

2.14.3 Self-dual graphs 145

2.14.4 Dual of a subgraph 146

2.14.5 Dual of a homeomorphic graph 146

2.14.6 Abstract dual 147

2.14.6 Combinatorial dual 147

2.15 Graph coloring 153

2.15.1 Partitioning problem 153

2.15.2 Properly coloring of a graph 154

2.15.3 Chromatic number 154

2.15.4 K-critical graph 155

2.16 Chromatic polynomial 155

2.16.1 Decomposition theorem 157

2.16.2 Scheduling final exams 164

2.16.3 Frequency assignments 164

(xiii)

2.16.4 Index resisters 165

2.17 Four colour problem 182

2.17.1 The four colour theorem 183

2.17.2 The five colour theorem 185

Problem Set 2.1 186

3. Trees 192

Introduction 192

3.1 Trees 192

3.1.1 Acyclic graph 192

3.1.2 Tree 192

3.1.3 Forest 192

3.2 Spanning tree 193

3.2.1 Branch of tree 193

3.2.2 Chord 193

3.3 Rooted tree 193

3.3.1 Co tree 193

3.4 Binary tree 194

3.4.1 Path length of a binary tree 195

3.4.2 Binary tree representation of general trees 196

3.5 Counting trees 215

3.5.1 Cayley theorem 217

3.6 Tree traversal 222

3.6.1 Preorder traversal 222

3.6.2 Postorder traversal 222

3.6.3 Inorder traversal 222

3.7 Complete binary tree 222

3.7.1 Almost complete binary tree 223

3.7.2 Representation of algebraic structure of binary trees 224

3.8 Infix, prefix and postfix notation of an arithmetic expression 224

3.8.1 Infix notation 224

3.8.2 Prefix notation 225

3.8.3 Postfix notation 225

3.8.4 Evaluating prefix and postfix form of an expression 225

3.9 Binary search trees 226

3.9.1 Creating a binary search tree 227

3.10 Storage representation of binary tree 227

(xiv)