A Textbook of Graph Theory | springerprofessional.de

Springer Professional

nach oben

2000 | Buch

Kapitel lesen Erstes Kapitel lesen

A Textbook of Graph Theory

verfasst von: R. Balakrishnan, K. Ranganathan

Verlag: Springer New York

Buchreihe : Universitext

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Über dieses Buch

Graph theory has experienced a tremendous growth during the 20th century. One of the main reasons for this phenomenon is the applicability of graph theory in other disciplines such as physics, chemistry, psychology, sociology, and theoretical computer science. This book aims to provide a solid background in the basic topics of graph theory. It covers Dirac's theorem on k-connected graphs, Harary-Nashwilliam's theorem on the hamiltonicity of line graphs, Toida-McKee's characterization of Eulerian graphs, the Tutte matrix of a graph, Fournier's proof of Kuratowski's theorem on planar graphs, the proof of the nonhamiltonicity of the Tutte graph on 46 vertices and a concrete application of triangulated graphs. The book does not presuppose deep knowledge of any branch of mathematics, but requires only the basics of mathematics. It can be used in an advanced undergraduate course or a beginning graduate course in graph theory.

Anzeige

Inhaltsverzeichnis

Frontmatter

I. Basic Results

Abstract

Graphs serve as mathematical models to analize successfully many concrete real-world problems. Certain problems in physics, chemistry, communications science, computer technology, genetics, psychology, sociology, and linguistics can be formulated as problems in graph theory. Also many branches of mathematics, such as group theory, matrix theory, probability, and topology, have interactions with graph theory.

R. Balakrishnan, K. Ranganathan

II. Directed Graphs

Abstract

Directed graphs arise in a natural way in many applications of graph theory. The street map of a city, abstract representation of computer programs, and network flows can be represented only by directed graphs rather than by graphs. Directed graphs also are used in the study of sequential machines and system analysis in control theory.

R. Balakrishnan, K. Ranganathan

III. Connectivity

Abstract

The connectivity of a graph is a “measure” of its connectedness. Some connected graphs are connected rather “loosely” in the sense that the deletion of a vertex or an edge from the graph destroys the connectedness of the graph. There are graphs in the other extreme as well, such as the complete graphs K_n, n ≥ 2, which remain connected even after removal of all but one vertex.

R. Balakrishnan, K. Ranganathan

IV. Trees

Abstract

“Trees” form an important class of graphs. Of late, their importance has grown considerably in view of their wide applicability in theoretical computer science. In this chapter, we present the basic structural properties of trees, their centers and centroids. In addition, we present two interesting consequences of the Tutte-Nashwilliams theorem on the existence of k pairwise edge-disjoint spanning trees in a simple connected graph. We also present Cay ley’s formula for the number of spanning trees in the labeled complete graph K_n.

R. Balakrishnan, K. Ranganathan

V. Independent Sets and Matchings

Abstract

Vertex-independent sets and vertex coverings as also edge-independent sets and edge coverings of graphs occur very naturally in many practical situations and hence have several potential applications. In this chapter, we study the properties of these sets. In addition, we also discuss matchings in graphs and, in particular, in bipartite graphs. Matchings in bipartite graphs have varied applications in operations research. We also present two celebrated theorems of graph theory, namely, Tutte’s 1-factor theorem and Hall’s matching theorem. All graphs considered in this chapter are loopless.

R. Balakrishnan, K. Ranganathan

VI. Eulerian and Hamiltonian Graphs

Abstract

The study of Eulerian graphs was initiated in the 18th century, and that of Hamiltonian graphs in the 19th century. These graphs possess rich structure, and hence their study is a very fertile field of research for graph theorists. In this chapter, we present several structure theorems for these graphs.

R. Balakrishnan, K. Ranganathan

VII. Graph Colorings

Abstract

Graph theory would not be what it is today if there had been no coloring problems. In fact, a major portion of the 20th-century research in graph theory has its origin in the four-color problem. (See Chapter VIII for details.)

R. Balakrishnan, K. Ranganathan

VIII. Planarity

Abstract

The study of planar and nonplanar graphs, and, in particular, the several attempts to solve the four-color conjecture have contributed a great deal to the growth of graph theory. Actually, these efforts had been instrumental to the development of algebraic, topological, and computational techniques in graph theory.

R. Balakrishnan, K. Ranganathan

IX. Triangulated Graphs

Abstract

Triangulated graphs form an important class of graphs. They are a subclass of the class of perfect graphs and contain the class of interval graphs. They possess a wide range of applications. We describe later in this chapter an application of interval graphs in phasing the traffic lights at a road junction.

R. Balakrishnan, K. Ranganathan

X. Applications

Abstract

In this chapter, we consider some immediate applications of certain graph theoretic results to day-to-day life problems.

R. Balakrishnan, K. Ranganathan

Backmatter

Titel: A Textbook of Graph Theory
verfasst von: R. Balakrishnan
K. Ranganathan
Copyright-Jahr: 2000
Verlag: Springer New York
Electronic ISBN: 978-1-4419-8505-7
Print ISBN: 978-1-4612-6422-4
DOI: https://doi.org/10.1007/978-1-4419-8505-7