A textbook of Graph Theory
Graph theory has witnessed an unprecedented growth in the 20th century. The best indicator for this growth is the explosion in MSC2010, field 05: Combinatorics. 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 Second Edition is a revised and enlarged edition with two new chapters—one on domination in graphs (Chap. 10) and another on spectral properties of graphs (Chap. 11)—and an enlarged chapter on graph coloring (Chap. 7). Chapter 10 presents the basic properties of the domination number of a graph and also deals with Vizing’s conjecture on the domination number of the Cartesian product of two graphs. Chapter 11 contains several results on the eigenvalues of graphs and includes a section on the Ramanujan graphs, and another on the energy of graphs.
The new additions in Chap. 7 include the introduction of b-coloring in graphs and an extension of the discussion of the Myceilskian of a graph over what was given in the First Edition. The sections of Chap. 10 of the First Edition that contained some applications of graph theory have been shifted in the Second Edition to the relevant chapters: “The Connector Problems” to Chap. 4, “The Timetable Problem” to Chap. 5 and the “Application to Social Psychology” to Chap. 1.
The book goes from the basics to the frontiers of research in graph theory, with newly ideas emergent, in mathematics or computer science. For the reader is suitable solving some of the many exercises proposed.
I feel sure that it will be of great use both to students of graph theory and mathematics, or computer science, and provide a solid background in the basic topics of graph theory, and is intended both for a graduate or advanced undergraduate in mathematics, or computer science as reference for the researcher.
The book can also be adapted for an undergraduate course in graph theory by selecting some sections: 1.1–1.6, 2.1–2.3, 3.1–3.4, 4.1–4.5, 5.1–5.4, 5.5 (omitting consequences of Hall’s theorem), 5.5 (omitting the Tutte matrix), 6.1–6.3, 7.1, 7.2, 7.5 (omitting Vizing’s theorem), 7.8, 8.1–8.4, and Chap. 10.
The authors are well-known: R. Balakrishnan, Department of Mathematics, Bharathidasan University, Sir C.V. Raman Road, Tiruchirappalli, 620 024, Tamil Nadu, India, and K. Ranganathan, (Deceased, in 2002). The Professor Balakrishnan welcomes any comments, suggestions, and corrections from readers. They can be sent to his at the email address: email@example.com.
An ambitious teacher can cover the entire book in a one-year (equivalent to two semesters) master’s course in graph theory, or mathematics, or computer science. However, a teacher who wants to proceed at leisurely pace can omit the sections that are starred. Exercises that are starred are non-routine.
The book contains preface to both editions, list of figures (p. i-xii), eleven chapters: 1 Basic Results.- 2 Directed Graphs.- 3 Connectivity.- 4 Trees.- 5 Independent Sets and Matchings.- 6 Eulerian and Hamiltonian Graphs.- 7 Graph Colorings.- 8 Planarity.- 9 Triangulated Graphs.- 10 Domination in Graphs.- 11 Spectral Properties of Graphs.- Bibliography.- Index, in 292 pages.
The first chapter, Basic Results, (p. 1-35), on consider graphs that 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.
In this chapter, on study the basics of theory of graphs, for example, a little introduction with the mention of the main topics historical problems: the famous Königsberg bridge problem; the challenging hamiltonian graph; the theory of acyclic graph; the study of trees; the well-known four-color problem; planar graphs; problems of linear programming and operations research; the Kirkman´s school girl problem and scheduling problems, and many more such problems can be added to the list. Then basic concepts; subgraphs; degrees of vertices, with the famous Euler´s theorem and their corollaries; paths and connectedness; automorphism of a simple graph; line graphs, Whitney´s theorem (1932); operations on graphs; graph products; an application to chemistry; application to Social Psychology; miscellaneous exercises, with 21 proposed exercises, and notes, a good account of references. In each above item there are quite easy simple, exercises, and examples, for the reader.
In the chapter two, Directed Graphs, (p. 37-47), these 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, and are also used in the study of sequential machines and system analysis in control theory.
The chapter is dedicated to basic concepts; tournaments, with Rédei (1934) and Moon (1968) theorems; k-partite tournaments; included five proposed exercises, and a brief notes about related references.
In the chapter 3, Connectivity, (p. 49-71), on analyzed it as 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 Kn, n ≥ 2, which remain connected after the removal of any k vertices, 1≤ k ≤ n − 1.
The chapter is totally devoted to connectedness, first, questions related to vertex cuts and edges cuts, then connectivity and edge connectivity, with outstanding Whitney´s theorem (1932); blocks; cyclical edge connectivity of a graph; the great Menger´s theorem (1927), more general that Whitney´s theorem, with applications to the theory of flows, the celebrated max-flow min-cut theorem due to Ford and Fulkerson (1956), and Dirac´s theorem (1960), on k-connected graphs. The chapter included fourteen proposed exercises, and notes with the associated bibliography, i.e., that chronologically, Menger´s theorem appeared, in the literature, the first, followed Whitney´s generalizations of Menger´s theorem.
The chapter 4, Trees, (p. 73-95), these 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 completely devoted to the basic structural properties of trees, their characterization and simple properties; their centers and centroids, Jordan´s theorem (1869); counting the number of spanning trees, on presented interesting consequences, expressed in form of corollaries, of the Tutte (1961)-Nash-Williams (1961) theorem on the existence of k pairwise edge-disjoint spanning trees in a simple connected graph. If k=2, obtained the result of Kundu (1974), about the bounds on the number of disjoint spanning trees; also, on presented Cayley´s formula (1857) for the number of spanning trees in the labeled complete graphs Kn; Helly property in the sense that any family of sub-trees of a tree satisfies the property; then some immediate applications of trees, in everyday life problems, as the connector problem, the Kruskal´s algorithm (1956) and Prim´s algorithm (1957), which determine a minimum-weight spanning tree in a connected weighted graph, and discussed the shortest path problems and Dijkstra´s algorithm (1959), which determines a minimum-weight shortest path between two specified vertices of a connected weighted graph. To end, the chapter included sixteen proposed exercises, and notes with historical references to intriguing problems on trees.
The chapter 5, Independent Sets and Matchings, (p. 97-115), deals 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, on study the properties of these sets. In addition, on discuss matchings in graphs and, in particular, in bipartite graphs. Matchings in bipartite graphs have varied applications in operations research. Moreover, two celebrated theorems of graph theory, namely, Tutte’s 1-factor theorem and famous Hall’s matching theorem. All graphs considered in this chapter are loopless.
In this chapter look deals vertex-independent sets and vertex coverings, the definition of the independence number or the stability number, and the covering number; matchings and factors, with applications in crystal physics, and in crystallography, interested in obtaining an analytical expression for certain surfaces properties of crystals consisting of diatomic molecules; matchings in bipartite graphs, the König´s theorem, the matrix version of König theorem, the Hall´s theorem (1935) on the existence of an system of distinct representatives, the Tutte´1-factor theorem (1947), and three corollaries, one due to Petersen (1981) about that every connected 3-regular graph no cut edges has a 1-factor, and the corollary two due Cunningham that, the edge set of a simple 2-edge-connected cubic graph can be partitioned into paths of length 3, and finally, the corollary three, that a (p-1) regular connected simple graph on 2p vertices has a 1-factor, then the Sumner (1974) theorem that shows that there is another special family of graphs for which can conclude that all graphs of the family have a 1-factor, i.e., let a connected graph of even order, if is claw-free (i. e., contains no K1,3 as an induced sub-graph), then the graph has a 1-factor. To the end the chapter, on analyzed perfect matchings and the Tutte matrix, and a bibliographical note.
In the chapter 6, Eulerian and Hamiltonian Graphs, (p. 117-142), on deals with Eulerian graphs that 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, on present several structure theorems for these graphs.
The chapter considered Eulerian graphs, which admit, among others, two elegant characterizations, the first one is that, for a nontrivial connected graph, the following statements are equivalent: 1) G is Eulerian; 2) The degree of each vertex is an even positive integer, and 3) G is an edge-disjoint union of cycles, and the second one is Toida (1973) -McKee's, (1984), characterization of Eulerian graphs: a graph is Eulerian if and only if each edge e of G belongs to an odd number of cycles of G and, the third is the result of Bondy and Halberstan (1986), a graph is Eulerian if and only if it has an odd number of cycle decompositions; Hamiltonian graphs, and the icosian game, introduced in 1859, no decent characterization of Hamiltonian graphs is known as yet. In fact it is one of the most difficult unsolved problems in graph theory. Many sufficient conditions are known, however, none of them happens to be a necessary condition. It is interesting note that if G is Hamiltonian, then every nonempty proper subset S of V, that is, w (G-S) ≤ card(S), being w (G-S), the number of components of the graph G-S, and the Ore´s theorem (1960) is a basic result which gives a sufficient condition for a graph to be Hamiltonian. The Dirac´s result (1952) is also very interesting. Other intriguing result for Hamiltonian graphs is due to Chvátal and Erdös (1972), if, for a simple 2-connected graph G, α≤κ, then G is Hamiltonian. (α is the independence number of G and κ is the connectivity of G); pancyclic graphs, a graph of order n (≥3) is pancyclic if G contains cycles of all lengths from 3 to n. G is called vertex-pancyclic if each vertex v of G belongs to a cycle of every length l, 3≤l≤n. The study of these was initiated by Bondy (1971), who showed that Ore´s condition actually implies much more. Note that if δ ≥ n2/2, then m≥ n2/4; Hamilton cycles in Line Graphs, on study the existence of Hamilton cycles in line graph, Harary and Nash-William's theorem (1965) on the hamiltonicity of line graphs, and others interesting theorems and corollaries; 2-Factorable Graphs, it is clear that if a graph is r-factorable with k, r-factors, then the degree of each vertex is rk. In concrete, if G is 2-factorable, then is regular of even degree, say 2k. The converse is also true, is a result due a Petersen (1891). To end, the chapter included eighteen proposed exercises, and notes with historical references to the nice survey of Hamiltonian problems given by Lesniak (1991), and others references of interest.
In the chapter 7, related to the study Graph Colorings, (p. 143-174). This is very important because the 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.
This chapter presents the basic results concerning vertex and edge colorings of graphs. In this second edition, is an enlarged chapter on graph coloring, the new additions include the introduction of b-coloring in graphs and an detailed extension of the description of the Myceilskian of a graph over what was given in the first edition.
In particular, contains the following aspects: applications of graph coloring to the storage problem about incompatible chemicals, and to the examination schedule; critical graphs with the great Brooks´s theorem (1941), other coloring parameters, and the important concept of b-colorings, introduced by Irving and Manlove (1999), i.e., a proper coloring with the additional property that each color class contains a color dominating vertex, that is, a vertex that has a neighbor in all the other color classes; homomorphisms and colorings, quotient graphs; triangle-free graphs, a graph is triangle-free if the graph contains no K3. The construction of triangle-free k-chromatic graphs, k ≥ 3, was raised and answered by Mycielski (1955), who developed an interesting graph transformation known as the Mycielskian of a graph; edge colorings graphs, with an application, the timetable problem, draw up a timetable for the day that requires only minimum number of periods, that r teachers to teach in s classes, König´s theorem, and other important theorem on graph coloring, the Vizing (1964)-Gupta (1966) theorem, one of the major result in edge coloring of graphs; a brief discussion of snarks (unusual creature, described by Martin Gardner, in Lewis Caroll´s poem, the Hunting of the snark), as a consequence of the Vizing-Gupta´s theorem. A snark is a cyclically 4-edge-connected cubic graph of girth at least 5 that has chromatic index 4. The Petersen graph is the smallest snark and it is the unique snark on 10 vertices. The construction of snarks is not easy. In 1975, Isaacs constructed two infinite classes of snarks. Prior to that, only four kinds of snarks were known: the Petersen graph, Blanusǎ´s graphs on 18 vertices, Szekeres´s graph on 50 vertices, and the Blanche-Descartes´s graph on 210 vertices; then the celebrated Kirkman´s schoolgirl problem (1850), and finally chromatic polynomials. A brief bibliographical note closed the chapter.
The chapter 8, Planarity, (p. 175-205), deals with the study of planar and nonplanar graphs, and the several attempts to solve the four-color conjecture that 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.
This chapter deals the basic results on planar graphs, and also two important characterizations theorems for planar graphs, Wagner´s theorem (1937), (same as the Harary-Tutte theorem (1965), and as a consequence, Kuratowski´s theorem (1930), whose proofs, in this book, following to Fournier (1980). Also the classical Euler Formula and its consequences; the fact that K5 and K3,3 are nonplanar graphs; the dual of a plane graph; the four-color theorem and the Heawood five-color theorem, after the conjecture first published in 1852, the solution found, Appel, Haken and Koch (1977), established the validity of the conjecture in 1976 with the aid of computer, 1200 hours of computer time on a high speed computer; Hamiltonian plane graphs; the Tait coloring (1880), unfortunately, Tait´s proof of the four color theorem was based in wrong assumption that any 2-edge-connected cubic planar graph is Hamiltonian, the counterexample is due a Tutte (1946), 65 years later, because the Tutte graph is not Hamiltonian, and a brief note ends the chapter.
The chapter 9, Triangulated Graphs, (p. 207-220), these 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, for example, in phasing the traffic lights at a road junction.
Behind the definition of perfect graphs, on introduce the triangulated and interval graphs. Then continue bipartite graph of a graph; circular arc graphs; twenty two proposed exercises, and the application to phasing the traffic lights. Notes about Berge´s graphs, and the strong perfect graph Berge´s conjecture (1960), ends the chapter.
In the chapter 10, Domination in Graphs, (p. 221-239), it is a new chapter in this second edition. It 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 pieces domination had positive answers, for example, in queens problem, the number of domination of queens in the standard chessboard is 5.
The chapter analyzed the following questions: bounds for the domination number; bounds for the size m in terms of order n and domination number, the basic result of Vizing (1965); independent domination and irredundance; thirteen proposed exercises; the extensive Vizing´s conjecture, with delicious lemmas and theorems; the interesting Barcalkin-German´s theorem (1979) for decomposable graphs in the sense that G is decomposable, then G satisfies Vizing´s conjecture; domination in direct graphs, and notes.
In the chapter 11, Spectral Properties of Graphs, (p. 241-273), 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). All graphs considered in this chapter are finite, undirected, and simple. The spectra of some well-known families of graphs—the family of complete graphs, the family of cycles etc., are calculated. Then present Sach’s theorem (1967), on the spectrum of the line graph of a regular graph, and also obtain the spectra of product graphs—Cartesian product, direct product, and strong product. On introduce Cayley graphs and Ramanujan graphs and highlight their importance. Finally, it analyzed an application of graph spectra to chemistry, the “energy of a graph”—a graph invariant that is widely studied these days.
The chapter deals with details the spectrum of a graph, and the characteristic polynomial; the spectrum of different graphs, as the complete graph, the cycle, regular graphs, the complement of a regular graph, line graphs of regular graphs (Sach´s theorem (1967)), the complete bipartite graph, and the product graphs; the Cayley graphs and their spectra; Ramanujan Graphs and their spectra; and to finish the newly energy of a graph, a concept borrowed from chemistry, molecular graph, maximum energy of k regular graphs, hyperenergetic graphs, Cayley graphs, the Mycielskian of a regular graph, and an application of the Balakrishnan-Kavaskar-So´s theorem (2012) about the energy of the Mycielskian of a k-regular G in terms of the energy of G. To ends the chapter and the book, on present twenty five proposed exercises, and a brief historical note.
List of Symbols (p.275-278)
Bibliography (p. 279-285). They are an extensive bibliography, 195 up-date references.
Index, (p. 287-292)
Definitely the book is high recommended and is of much interest. It provides a solid background in the basic topics of graph theory, and is an excellent guide for graduate. I feel sure that it will be of great use to students, teachers and researchers.