Narsingh Deo - Graph Theory with Applications to Engineering and Computer Science

Millican Chair Professor, Dept. of Computer Science

Director, Center for Parallel Computation,

University of Central Florida

Copyright

Copyright 1974 by Narsingh Deo

All rights reserved.

Bibliographical Note

This Dover edition, first published in 2016, is an unabridged republication of the work originally published in 1974 by Prentice-Hall, Inc., Englewood Cliffs, New Jersey.

Library of Congress Cataloging-in-Publication Data

Names: Deo, Narsingh 1936

Title: Graph theory with applications to engineering and computer science / Narsingh Deo.

Description: Dover edition. | Mineola, New York: Dover Publications, 2016. Originally published: Englewood Cliffs, New Jersey: Prentice-Hall, Inc., 1974. | Includes bibliographical references and index.

Identifiers: LCCN 2016008025 | ISBN 9780486807935 | ISBN 0486807932

Subjects: LCSH: Graphy theory. | Engineering mathematics.

Classification: LCC TA338.G7 D46 2016 | DDC 511/.5dc23 LC record available at http://lccn.loc.gov/2016008025

Manufactured in the United States by RR Donnelley

80793201 2016

www.doverpublications.com

To the memory of my father,

who did not live to realize his greatest ambition

that of witnessing his eldest son matriculate.

The last two decades have witnessed an upsurge of interest and activity in graph theory, particularly among applied mathematicians and engineers. Clear evidence of this is to be found in an unprecedented growth in the number of papers and books being published in the field. In 1957 there was exactly one book on the subject (namely, Knigs Thorie der Endlichen und Unendlichen Graphen). Now, sixteen years later, there are over two dozen textbooks on graph theory, and almost an equal number of proceedings of various seminars and conferences.

Each book has its own strength and points of emphasis, depending on the axe (or the pen) the author has to grind. I have emphasized the computational and algorithmic aspects of graphs. This emphasis arises from the experience and conviction that whenever graph theory is applied to solving any practical problem (be it in electrical network analysis, in circuit layout, in data structures, in operations research, or in social sciences), it almost always leads to large graphsgraphs that are virtually impossible to analyze without the aid of the computer. An engineer often finds that those real-life problems that can be modeled into graphs small enough to be worked on by hand are also small enough to be solved by means other than graph theory. (In this respect graph theory is different from college algebra, elementary calculus, or complex variables.) In fact, the high-speed digital computer is one of the reasons for the recent growth of interest in graph theory.

Convinced that a student of applied graph theory must learn to enlist the help of a digital computer for handling large graphs, I have emphasized algorithms and their efficiencies. In proving theorems, constructive proofs have been given preference over nonconstructive existence proofs. and in many sections from other chapters is appearing for the first time in any textbook.

Yet the applied and algorithmic aspect of this book has not been allowed to spoil the rigor and mathematical elegance of graph theory. Indeed, the book contains enough material for a course in pure graph theory. The book has been made as much self-contained as was possible.

The level of presentation is appropriate for advanced undergraduate and first-year graduate students in all disciplines requiring graph theory. The book is organized so that the first half () serves as essential and introductory material on graph theory. This portion requires no special background, except some elementary concepts from set theory and matrix algebra and, of course, a certain amount of mathematical maturity. Although the illustrations of applications are interwoven with the theory even in this portion, the examples selected are short and mostly of the nature of puzzles and games. This is done so that a student in almost any field can read and grasp the first half.

The second half of the book is more advanced, and different chapters require different backgrounds as they deal with applications to nontrivial, real-world, complex problems in different fields. Keeping this in mind, have been made independent of each other. One could study a later chapter without going through the earlier ones, provided the first nine chapters have been covered.

Since there is more material here than what can be covered in a one-semester course, it is suggested that the contents be tailored to suit the requirements of the students in different disciplines, for example:

Electrical Engineering: .

Computer Science: .

Operations Research: .

Applied Mathematics: .

Introductory pure graph theory: .

In fact, the book grew out of a number of such courses and lecture-series given by the author at the Jet Propulsion Laboratory, California State University at Los Angeles, the Indian Institute of Technology at Kanpur, and the University of Illinois at Urbana-Champaign.

It is a pleasure to acknowledge the help I have received from different individuals and institutions. I am particularly indebted to Mr. David K. Rubin, a dear friend and former colleague at the Jet Propulsion Laboratory; Mr. Mateti Prabhaker, a former graduate student of mine at the Indian Institute of Technology, Kanpur; and Professor Jurg Nievergelt of the University of Illinois at Urbana-Champaign for having read the entire manuscript and made numerous suggestions for improvements throughout the book.

Other friends, colleagues, and students who read parts of the manuscript and made helpful suggestions are: Professor Harry Lass and Mr. Marvin Perlman of the Jet Propulsion Laboratory, Professor Nandlal Jhunjhunwala of California State University at Los Angeles, Dr. George Shuraym of Texas Instruments, Mr. Jean A, DeBeule of Xerox Data Systems, Mr. Nicholas Karpov of Bell & Howell, Professor C. L. Liu of the University of Illinois at Urbana-Champaign, Messrs. M. S. Krishnamoorthy, K. G. Ramakrishnan, and Professors C. R. Muthukrishnan and S. K. Basu of the Indian Institute of Technology at Kanpur.

I am also grateful to the late Professor George E. Forsythe of Stanford University for his encouragement at the very outset of this project.

Support in writing this book was received from the Jet Propulsion Laboratory, the Indian Institute of Technology at Kanpur, and the Computer Science Department of the University of Illinois at Urbana-Champaign.

Just as one does not thank himself, expressing gratitude to ones wife in public is not a Hindu custom. For the wife is considered a part of the husband, and her coauthorship is tacitly assumed in any book her husband writes. There is little doubt that without Kirans help this book would not have been possible.

NARSINGH DEO

Kanpur

A linear, for instance, is a graph.

Observe that this definition permits an edge to be associated with a vertex pair (vi, vi). Such an edge having the same vertex as both its end vertices is called a self-loop (or simply a loop. The word loop, however, has a different meaning in electrical network theory; we shall therefore use the term self-loop to avoid confusion). Edge