Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2012 | Buch

Basic Results Kapitel lesen Erstes Kapitel lesen

A Textbook of Graph Theory

verfasst von: R. Balakrishnan, K. Ranganathan

Verlag: Springer New York

Buchreihe : Universitext

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Graph theory experienced a tremendous growth in 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 textbook provides a solid background in the basic topics of graph theory, and is intended for an advanced undergraduate or beginning graduate course in graph theory.

This second edition includes two new chapters: one on domination in graphs and the other on the spectral properties of graphs, the latter including a discussion on graph energy. The chapter on graph colorings has been enlarged, covering additional topics such as homomorphisms and colorings and the uniqueness of the Mycielskian up to isomorphism. This book also introduces several interesting topics such as 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.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Basic Results
Abstract
Graphs serve as mathematical models to analyze many concrete real-world problems successfully. Certain problems in physics, chemistry, communication 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 close connections with graph theory.
R. Balakrishnan, K. Ranganathan
Chapter 2. Directed Graphs
Abstract
Directed graphs arise in a natural way in many applications of graph theory. The street map of a city, an abstract representation of computer programs, and network flows can be represented only by directed graphs rather than by graphs. Directed graphs are also used in the study of sequential machines and system analysis in control theory.
R. Balakrishnan, K. Ranganathan
Chapter 3. 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 at the other extreme as well, such as the complete graphs K n , n ≥ 2, which remain connected after the removal of any k vertices, 1≤ k≤n − 1.
R. Balakrishnan, K. Ranganathan
Chapter 4. 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.
R. Balakrishnan, K. Ranganathan
Chapter 5. 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 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
Chapter 6. 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 structures; 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
Chapter 7. 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 Chap. 8 for details.)
R. Balakrishnan, K. Ranganathan
Chapter 8. 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 have been instrumental to the development of algebraic, topological, and computational techniques in graph theory.
R. Balakrishnan, K. Ranganathan
Chapter 9. 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
Chapter 10. Domination in Graphs
Abstract
“Domination in graphs” is an area of graph theory that has received a lot of attention in recent years. It is reasonable to believe that “domination in graphs” has its origin in “chessboard domination.” The “queen domination” problem asks: What is the minimum number of queens required to be placed on an 8 ×8 chessboard so that every square not occupied by any of these queens will be dominated (that is, can be attacked) by one of these queens? Recall that a queen can move horizontally, vertically, and diagonally on the chessboard. The answer to the above question is 5. Figure 10.1 gives one set of dominating locations for the five queens.
R. Balakrishnan, K. Ranganathan
Chapter 11. Spectral Properties of Graphs
Abstract
In this chapter, we look at the properties of graphs from our knowledge of their eigenvalues. The set of eigenvalues of a graph G is known as the spectrum of G and denoted by Sp(G). We compute the spectra of some well-known families of graphs—the family of complete graphs, the family of cycles etc. We present Sachs’ theorem on the spectrum of the line graph of a regular graph. We also obtain the spectra of product graphs—Cartesian product, direct product, and strong product. We introduce Cayley graphs and Ramanujan graphs and highlight their importance. Finally, as an application of graph spectra to chemistry, we discuss the “energy of a graph”—a graph invariant that is widely studied these days. All graphs considered in this chapter are finite, undirected, and simple.
R. Balakrishnan, K. Ranganathan
Backmatter
Metadaten
Titel
A Textbook of Graph Theory
verfasst von
R. Balakrishnan
K. Ranganathan
Copyright-Jahr
2012
Verlag
Springer New York
Electronic ISBN
978-1-4614-4529-6
Print ISBN
978-1-4614-4528-9
DOI
https://doi.org/10.1007/978-1-4614-4529-6