Graph theory / J. A. Bondy, U. S. R. Murty.

Format:

Book

Author/Creator:

Bondy, J. A. (John Adrian)

Contributor:

Murty, U. S. R.

Series:

Graduate texts in mathematics ; 244.

Graduate texts in mathematics ; 244

Language:

English

Subjects (All):

Graph theory.

Physical Description:

xii, 651 pages : illustrations ; 25 cm.

Place of Publication:

New York ; London : Springer, 2008.

Summary:

Graph theory is a flourishing discipline containing a body of beautiful and powerful theorems of wide applicability. Its explosive growth in recent years is mainly due to its role as an essential structure underpinning modern applied mathematics - computer science, combinatorial optimization, and operations research in particular - but also to its increasing application in the more applied sciences. The versatility of graphs makes them indispensable tools in the design and analysis of communication networks, for instance.

The primary aim of this book is to present a coherent introduction to the subject, suitable as a textbook for advanced undergraduate and beginning graduate students in mathematics and computer science. It provides a systematic treatment of the theory of graphs without sacrificing its intuitive and aesthetic appeal. Commonly used proof techniques are described and illustrated, and a wealth of exercises - of varying levels of difficulty - are provided to help the reader master the techniques and reinforce their grasp of the material.

A second objective is to serve as an introduction to research in graph theory. To this end, sections on more advanced topics are included, and a number of interesting and challenging open problems are highlighted and discussed in some detail. Despite this more advanced material, the book has been organized in such a way that an introductory course on graph theory can be based on the first few sections of selected chapters.

Contents:

1 Graphs 1

2 Subgraphs 39

3 Connected Graphs 79

4 Trees 99

5 Nonseparable Graphs 117

6 Tree-Search Algorithms 135

7 Flows in Networks 157

8 Complexity of Algorithms 173

9 Connectivity 205

10 Planar Graphs 243

11 The Four-Colour Problem 287

12 Stable Sets and Cliques 295

13 The Probabilistic Method 329

14 Vertex Colourings 357

15 Colourings of Maps 391

16 Matchings 413

17 Edge Colourings 451

18 Hamilton Cycles 471

19 Coverings and Packings in Directed Graphs 503

20 Electrical Networks 527

21 Integer Flows and Coverings 557

Graph Parameters 625

Operations and Relations 627

Families of Graphs 629

Structures 631

Other Notation 633.

Notes:

Includes bibliographical references (pages [593]-622) and index.

ISBN:

1846289696

9781846289699

184628970X

9781846289705

OCLC:

176832832