## Recent book reviews

Five recent book reviews

## A primer on mapping class groups

Author(s):
Benson Farb, Dan Margalit
Publisher:
Princeton University Press
Year:
2011
ISBN:
978-0-691-14794-9
Short description:

This book is a first course in mapping class groups. It presents a wide variety of results of this beautiful theory which lies in the intersection of geometry, topology and group theory. It is suitable for graduate students and researches interested in this area.

MSC main category:
57 Manifolds and cell complexes
MSC category:
57M50
Other MSC categories:
20F36, 20F65, 57M07, 57N05
Reviewer:
Raquel Díaz, Álvaro Martínez
Affiliation:

## MAGIC GRAPHS

Author(s):
ALISON M. MARR, W.D. WALLIS
Publisher:
SPRINGER SCIENCE + BUSINESS MEDIA.BIRKHÄUSER. NEW YORK.2013. Second Edition, XVI, 186 p. 34 Illus., Hardcover.
Year:
2013
ISBN:
978-0-8176-8390-0; 978-0-8176-8391-7 (eBook); DOI 10.1007/978-0-8176-8391-7.
Price (tentative):
From 41.84$(eBook) to 51.95$ (Hardcover).
Short description:

The book begins with a survey of the main topics. Magic properties are introduced by a discussion of magic squares, also the related Latin squares and on Latin rectangles, and the basics of graph theory.

This concise, self-contained text-book is the only book of its kind in the area of magic graphs/labeling, it contains numerous exercises, and their solutions, and includes updates on new research in the field. A labeling is a mapping whose domain is some set of graph elements—the set of vertices, for example, or the set of all vertices and edges—and whose range was a set of positive integers. Various restrictions can be placed on the mapping.

Recently there has been a resurgence of interest to magic labeling due to a number of results that have applications to the problem of decomposing graphs into trees.

In this second edition includes: a new chapter on magic labeling of directed graphs, applications of theorems from graph theory and interesting counting arguments, this is why a new edition seemed appropriate, a good collection of new research problems and exercises covering a range of difficulties, and a fully updated bibliography and index. The book is a beautiful collection of recent results on the topic of magic labeling.

Some knowledge of groups and fields is assumed in the preliminary chapter, in the discussion of magic squares and Latin squares, and the basics of graph theory. Subsequent chapters explore the three main types of magic labeling—edge-magic, vertex-magic, and totally magic—in turn. Finally, magic labeling of directed graphs are discussed.

This book is a good guide for graduate students beginning research in graph labeling. They can see how new mathematics comes into existence. It may serve as a graduate or advanced undergraduate text for courses in mathematics or computer science, and as reference for the researcher.

URL for publisher, author, or book:
www.birkhauser-science.com
MSC main category:
05 Combinatorics
MSC category:
05C78, 68R10, 05C30.
Other MSC categories:
05B15, 68RXX, 90B15, 90B18, 90C35.
Review:

The book begins with a survey of the main topics. Magic properties are introduced by a discussion of magic squares, also the related Latin squares and on Latin rectangles, and the basics of graph theory.

The book Magic Graphs, is self-contained, good, admirably clear, and a stimulating and very well written. This concise text-book is the only book of its kind in the area of magic graphs/labeling, it contains numerous exercises, and their solutions, and includes updates on new research in the field.

A labeling is a mapping whose domain is some set of graph elements—the set of vertices, for example, or the set of all vertices and edges—and whose range was a set of positive integers. Various restrictions can be placed on the mapping.

The introductory chapter covers briefly the basics of graph theory and introduces various kinds of magic labeling of graphs. The main three chapters that follow are devoted to the three main types of magic labeling: edge magic, vertex-magic, and totally magic labeling, respectively. Each main topic is treated in depth. Not many mathematical prerequisites are needed to read this book although the reader should have some mathematical maturity. The mathematical material is sufficiently closed.

The aim of the present book is to describe the main concepts of magic graphs and labeling, together with full proofs that would be both accessible to beginners and useful for graduate and advanced undergraduate in mathematics or computer science, or recreational mathematical, and as reference for the researcher. The chapter five, added to the second edition, is devoted to rapidly developing areas of magic graphs, as newly magic type labeling of digraphs.

It goes from the basics to the frontiers of research in magic labeling of digraphs, with newly ideas emergent, in mathematics or computer science. For the reader is suitable solving some of the many exercises and research problems. ¡Good experience for share seriously the problems!

I feel sure that it will be of great use both to students of graph theory, magic graphs, Latin squares and Latin rectangles, design of experiments, graceful graphs, and mathematics, in general, and captivate to students, instructors, puzzle devotees, and to those intervening in recreational mathematics.

The book contains preface, table of contents, list de figures (pp. i-xvi), and five chapters, comments on the research problems, references, answers to selected exercises, and an index, in 186 pp.

The first chapter, preliminaries, (pp. 1-14), introduces the basic, definitions and notions, devoted to present the main topics in the subject. The book begins with a survey of main items. Magic properties with a discussion of magic squares, related Latin squares and on Latin rectangles are presented. The basics of graph theory are covered. A labeling (or valuation) of a graph is a map that carries graph elements to numbers. The most common choices of domain are the set of all vertices and edges (named total-labeling), the vertex-set alone (vertex-labeling), or the edge-set alone (edge-labeling).

Then define graph labeling, in general and magic labeling, in particular. In many cases, it is interesting to consider the sum of all labels associated with a graph label. It is conceivable that the same labeling could be both vertex-magic and edge-magic for a given graph, in this case the labeling, and the graph are called totally magic. There are also a number of interesting types of magic labeling of digraphs. The chapter also includes some applications of magic labeling to efficient addressing systems and to ruler models.

This preliminary chapter considered three theorems, and one lemma, and one corollary. Also ten exercises, very quite easy. The proofs of theorems and lemmas are given, and also the majority of exercises are solved with their respective solutions.

In the chapter two, (pp. 15-70), on define an edge-magic total labeling on a graph G as a one-to-one map λ form V(G) U E(G) onto the integers 1,2, …, v+e, where v=card(V(G)) and e=card(E(G)), with the property that, given any edge xy, λ(x) + λ(xy) + λ(y) = k, for some constant k, that is, wt(xy) =k for any choice of edge xy. Then k is called the magic sum of G.

Any graph with an edge-magic total labeling will be called edge magic. Examples of edge magic total labeling are given.

The remainder is full dedicated to Edge-Magic Total Labeling: Basic ideas, definitions, some elementary counting, and duality; then Graphs with no edge magic total labeling, main theorem, forest, regular graphs; Cliques and complete graphs, the Sidon sequences and labeling, complete graphs, all edge-magic total labeling of complete graphs, complete and split sub-graphs and graphs; Cycles, small and generalizations; Complete Bipartite Graphs, small cases and stars; Wheels, the constructions for n, distinct of ≡2 (mod.4), and n≡ 2 (mod.4); Trees; Disconnected Graphs, some easy cases, union of complete graphs, union of stars, tri-chromatic graphs; Super edge-magic total labeling; A cycle with a chord, odd and even cycles, and some general constructions; to end edge magic injections.

This chapter considered 37 theorems, and ten lemmas, and seven corollaries. For stimulating to reader and the beginner researcher on proposed 24 exercises, and 21 research problems. The proofs of theorems and lemmas are given, and also the majority of exercises are solved with their respective solutions. Respect the research problems are given hints for their statement that are solved in the Notes on Research Problems, pages 159 to 162, because the most requires very little work.

In the chapter 3, (pp.71-109), on define a vertex-magic total labeling on a graph G as a one-to-one map λ form V(G) U E(G) onto the integers {1,2, …, v+e}, where v=card(V(G)) and e=card(E(G)), if there is a constant h so that for every vertex x, λ(x) + ∑ λ(xy) = h, where the sum is over all vertices y adjacent to x. So the magic requirement is wt(x) =h for all x. The constant h is called the magic constant for λ. Again, a graph with a vertex-magic total labeling will be called vertex-magic. It is not hard to find examples of vertex-magic total labeling for some graphs.

The chapter is totally devoted to vertex-magic total labeling, and analyze basic ideas, definitions and basic counting; the case of regular graphs, cycles and paths; the interesting case of vertex-magic total labeling of wheels and its generalizations, because the large wheels cannot be labeled, and the small wheels can have many labeling; the vertex-magic total labeling of complete bipartite graphs, construction for Km,n, the spectrum, joins, unions of stars; the vertex-magic total labeling of complete tripartite graphs; graphs with vertices of degree one; complete graphs; disconnected graphs, multiples of regular graphs; super vertex-magic total labeling, and vertex-magic injections.

This chapter considered 30 theorems, and two lemmas, and eight corollaries. Fifteen exercises, and five research problems, are proposed. The proofs of theorems and lemmas are given, and also the majority of exercises are solved with their respective solutions. Respect the research problems are given hints for their statement.

In this chapter 4, investigate the question: for a graph G does there exist, a total labeling λ, that is, both edge-magic and vertex-magic? λ is called a totally magic labeling and G is a totally graph. The constants h and k are the magic constant and magic sum, respectively. Not require that h=k. Because the totally magic graphs are very rare, is adequate, to study totally magic injections. If a graph posses such a mapping, is called total magic injections (TMI) graph.

The chapter is completely devoted to totally magic labeling (pp. 111-134), and study basic ideas, definitions and examples. Then isolates and stars; forbidden configurations; unions of triangles; small graphs; totally magic injections; totally magic equation matrix, and the survivors on seven vertices.

This chapter considered 18 theorems, and four lemmas, and eleven exercises. The proofs of theorems and lemmas are given, and also the majority of exercises are solved with their respective solutions. Moreover, eight exercises and five interesting research problems are proposed.

The chapter 5, (pp. 135-157), new in this second edition, respect to the original book of Wallis, in this case, in collaboration with Alison Marr, deals with magic type labeling of digraphs. Early labeling results were all on undirected graphs. However, in mid-1980s, in the literature appeared the graceful labeling on directed graphs, in general, this is very important due to a number of interesting results that have applications and are related to the problems of decomposing graphs into trees.

A magic labeling of a digraph D is a one-to-one map λ from V(D)UE(D) onto the set of integers {1,2,…,v+e}, in which all the sums mA= λ (x) + ∑x→y λ(x,y), and all sums mB= λ (x) + ∑z→x λ(z,y), are constant, independent of the choice of x. A digraph with a magic labeling is a magic digraph.

The chapter is completely devoted to magic type labeling of digraphs, and study magic labeling, with definitions, basic counting, small examples, complete digraphs, double cycles, and magic digraphs with two magic constants; locally magic labeling with digraphs such as no locally magic labeling, cycles, wheels, complete graphs, and complete bipartite digraphs; vertex-magic edge labeling; arc-magic labeling with definitions, paths and cycles, labeling for arc-magic digraphs, and to end, different items on in/out magic total labeling, basic ideas, small digraphs, forbidden configurations, and regular graphs.

This chapter considered 25 theorems, and two lemmas, and ten exercises. The proofs of theorems and lemmas are given, and also the majority of exercises are solved with their respective solutions. Moreover, six interesting research problems are proposed.

Notes on Research Problems, (pp. 159-162). Different kinds on research problems are mentioned throughout the text. The most required very little work. An brief comment is included in the volume, related to research problems on the three main topics (about edge-magic labeling, 21 stated problems; on vertex magic labeling, 5 posed problems; on totally magic labeling, with five research problems) and the other topic, added in this second edition, on magic type labeling of digraphs, on considered six proposed problems. The last three problems, in this chapter about notes on research problems, all ask for more general results for some classes of digraphs or to find more infinite families of digraph with the given property.

References, (pp. 163-169). They are an extensive bibliography, 99 up-date references.

Answers to Selected exercises, (pp. 171-182). The exercises are designed to aid understanding. Some are quite easy, a few are quite difficult, and the others for works particular graph or labeling. There are worked solutions, to the majority of the exercises.

Index (pp. 183-186)

In this second edition includes: a new chapter on magic labeling of directed graphs, applications of theorems from graph theory and interesting counting arguments, a good collection of new research problems and exercises covering a range of difficulties, and a fully updated bibliography and index. The book is a beautiful collection of recent results on the topic of magic labeling.

Definitely the book is high recommended and is of much interest. This book is a good guide for graduate students beginning research in graph labeling. They can see how new mathematics comes into existence. It may serve as a graduate or advanced undergraduate text for courses in mathematics or computer science, and as reference for the researcher. I feel sure that it will be of great use both to students and researchers.

Reviewer:
Francisco José Cano Sevilla.
Affiliation:

## ACROSS THE BOARD: THE MATHEMATICS OF CHESSBOARD PROBLEMS

Author(s):
JOHN J. WATKINS
Publisher:
PRINCETON UNIVERSITY PRESS. SERIES: PRINCETON PUZZLERS: Paradoxes, perplexities, and mathematical conundrums, for the serious head scratcher.
Year:
2012
ISBN:
978-0-691-15498-5
Price (tentative):
From 14.78$to 18.95$.
Short description:

This book is a stimulating and very well written. It is admirably clear. It explains not only methods and results but the motives for choosing, in each moment, various procedures. The material used in the book, is supplemented by excellently chosen exercises, questions or problems, some of which give an insight into other aspects of the proposed chapters. There is a good collection of problems and worked examples, with variations extending to boards of different sizes and shapes.

Across the board is a concise, good, cleared, and indeed, definitive book about questions and problems on chessboard. It is not simply about chess but the chessboard itself, in particular, the intriguing and challenging mathematics behind it. John Watkins, a well-known mathematician, surveys all the problems of interest in this promising area of recreational mathematics. Each main topic is treated in depth from its historical creation through to its status today.

The book contains thirteen chapters, references and an index, in 257 pp. It goes from the basics, classical and variants of the knight´s tour problem, queens domination, magic squares, etc., to the frontiers of research in recreational mathematics, because Watkins uses the visual language of graph theory, and guides perfectly the reader to the frontiers of current research, in news ideas emergent in mathematics, such that, the shape Klein bottle, three-dimensional chessboards and even chessboards on unusual surfaces, toruses and cylinders.
Definitely the book is high recommended and is of much interest. This book is, no doubt, the newly best exposition of the interconnection between recreational mathematics and the interesting chessboard problems. I feel sure that it will be of great use both to students of graph theory, geometry, topology and mathematics, in general, and captivate to scholars, instructors, chess enthusiasts, puzzle devotees, and to those intervening in recreational mathematics.

URL for publisher, author, or book:
www.press.princeton.edu
MSC main category:
00 General
MSC category:
00A08, 97A20, 97K30, 05C30
Other MSC categories:
05B15, 94C15, 68R10, 82B20
Review:

This remarkable book is the first systematic work on chessboard problems and full-length book on the chessboard itself, devoted to an intriguing and comprehensive study from the knight´s tour problem and Queens Domination problems, in their many variations. Such earlier problems, including those involving other particular considerations, have now extended to three-dimensional chessboards, torus-shaped boards, a shape called Klein bottle, cylinders, etc.

The book is a stimulating and very well written. It is admirably clear. It explains not only methods and results but the motives for choosing, in each moment, various procedures. The material used in the book, is supplemented by excellently chosen exercises, questions or problems, some of which give an insight into other aspects of the proposed chapters. There is a good collection of problems and worked examples, with variations extending to boards of different sizes and shapes.

Across the board, is a concise, good, cleared, and indeed, definitive book on chessboard questions and problems. It is not simply about chess but the chessboard itself, in particular, the intriguing and challenging mathematics behind it. John Watkins, a well-known mathematician, surveys all the problems of interest in this promising area of recreational mathematics. Each main topic is treated in depth from its historical creation through to its status today.

The book is self-contained. The mathematical material is sufficiently closed, and contains up-to-date exposition of the key aspect of recreational mathematics. The book is quite accessible for undergraduate students of low courses, thus it can be used as a basic course book on recreational mathematics. This book can also be useful for professional and amateur mathematicians, because it contains the newest and the most significant scientific developments in this area.

The aim of the present book is to describe the main concepts of modern recreational mathematics together with full proofs that would be both accessible to beginners and useful for amateur and professional in chess problems. A large part of the present title is devoted to rapidly developing areas of recreational mathematics, such that, toruses, cylinders, others three-dimensional chessboards, etc.

The book contains thirteen chapters, references and an index, in 257 pp. It goes from the basics, classical and variants of the knight´s tour problems, domination in the queens problems, magic squares, etc., to the frontiers of research, because Watkins uses the visual language of graph theory, and guides perfectly the reader to the frontiers of current research, in news ideas emergent in mathematics. For the reader is suitable solving some of the many exercises. ¡Good experience for share seriously the problems! In short, the great resource to Professor Watkins´s proper tone ensures total attention from the audience to recreational mathematics.

The first chapter, untitled Introduction, (pp. 1-24), introduces the basic, definitions and notions, devoted to present the main topics in the subject. The chessboard provides the field of play for any number of games. Beginning with the Guarini´s problem, the earliest puzzle dated from 1512, in graph theory, and, then, one extension of Guarini´s problem to six knights, three white and three black, appeared in Scientific American in the December 1979 issue. We have just studied the famous problem of Knight´s Tour Problem, dates in the sixth century in India, with a long and rich history, from the beginnings to the frontiers of research. It is one of the main topics considered in this book.

This chapter is a compendium, remarkable and fascinating encyclopedic treatment of basics, and the main topics in the area of recreational mathematics. The main topics considered and studied in the following chapters are: Knights Tour, it follows the Euler´s work in 1759, the impossibility of an knight´s tour on 4x4 board; Domination problems, first originated when the people began asking covering questions about chess pieces, i.e., the minimum number of pieces of a given type needed to cover or control the entire board; Independence problems, what is the maximum number of pieces that you can place on chessboard, so that no two pieces attack one another?; Coloring, this is a theme of high recurrence, because using coloring to see how find infinitely many chessboards that can´t possibly have knight´s tours!; Geometric Problems, covering problems in the board; Chessboards on other surfaces, and even covering chessboards with ominoes in all manner of sizes: polyominoes, i.e., monominoes, dominoes, trominoes, tetraminoes, pentominoes, and so on, for example, the domino puzzle (Gomory´s theorem) for covering the chessboard.

Moreover, another interesting topic inside in a large number and not particularly easy to categorize is a puzzle that was popular in the eighteenth century, called Ozanam´s Problem, the study of the creation a Graeco-Latin square.

This chapter contains, moreover, six interesting problems, stated and solved, that cover the different relevant questions.

Chapter 2, (pp. 25-38) is full dedicated to Knight´s Tours, from the early work to actually: de Moivre, Legendre, Euler that provide a powerful and flexible technique, known Euler strategy, similar to actual backtracking algorithm, Hamilton, and other outstanding mathematicians. In other words, when we are looking for a knight´s tour we are actually trying to find a Hamiltonian cycle in the associated graph. It is possible consider also another tours, for example the rook´s tour for proved the Gomory´s theorem; the queen tour, in particular Dudeney´s puzzle, bishop´s tour problem, and the king´s tour.

This chapter contains, moreover, six interesting problems, stated and solved, that cover the different relevant questions.

In chapter 3 (pp.39-52) on consider the Knight´s Tour Problem. On prove the impossibility of such tour for a number of other chessboards. It mentioned that a 3x10 board was the smallest such board for which a knight´s tour is possible. A knight´s tour is impossible on the 4x4 chessboard, and also on any board both of whose dimensions are odd. There are no tours for the 3x4, 3x6 or 3x8 boards.

In this chapter on present two proofs of the impossibility of knight´s tours for 4xn boards, one due to Pósa and another one to Golomb, the inventor of polyominoes and then the Schwenk´s theorem, that reads: “An m x n chessboard with m ≤ n has a knight´s tour unless one or more of the following three conditions hold: a) m and n are both odd; b)m = 1,2, or 4, or c) m= 3 and n= 4, 6, or 8”.

To end the chapter, the case 3 x n, with an approach that works, as an inductive one, start with a tour of a small board and slowly but steadily build larger and larger tours from small tours. Any 3xn board has a knight´s tour for n≥10 and n even, that is, all the boards 3x10, 3x12, 3x14, 3x16, 3x18, etc., have tours.

The chapter contains, moreover, five interesting problems, stated and solved, that cover the different relevant questions.

Chapter 4 does magic squares (pp. 53-63). Claudia Zaslavsky described Muhammad ibn Muhammad´s work on magic squares, dated in 1732, in her book on African mathematics, Africa Counts. He made use of the knight´s move in order to construct magic squares of odd order, squares of size 3x3, 5x5, 7x7, etc. In magic squares, the sum of the numbers in each row, each column, and each of the main diagonals, for 3x3 will be 15; for 5x5 will be 65; and, for 7x7 the sum will be 175. This very same construction was discovered by Bachet en the early 1600s and a nearly identical construction was brought, by de la Loubère. In this chapter, on considered also, semi-magic squares, studied by Euler, Jaenisch, Wenzelides, Mrignac, and others famous mathematicians; and is possible using kings (Ghersi. 1921), and rooks (Rabinoff, 1925) tours, to construct magic squares.

The chapter contains, four interesting problems, stated and solved, that cover the different relevant questions.

In Chapter 5 (pp. 65-77), in the present book, will look many variations on the consideration of chessboards on two surfaces: the torus and the cylinder. On proves that on a torus: “Every rectangular chessboard has a knight´s tour”. As earlier, a knight has significantly more mobility on a torus, and so the knight´s graph for the 4x4 chessboard on a torus is highly richer that on 4x4 chessboard. On a torus each square is now completely equivalent, and so the degree of each vertex will be 4.Moreover, it turns out that the 4x4 toroidal knight´s graph is identical to an extremely famous graph called the 4-cube, or hypercube.

Then we explored the relation between the 4-cube and the Gray codes, invented by Frank Gray in the 1940s, as a way to transmit strings of data so that a small error occurring during transmission will result in only a small error in the received message. Gray listed all the strings in a sequence so that adjacent strings differ in only one position. This Gray code, in fact, corresponds to a Hamiltonian cycle in the hypercube.

To end the chapter, the following theorem (Watkins) solved an exact description of which rectangular chessboards have knight´s tour on cylinders: “An mxn cylindrical chessboard with m rows and n columns, the rows wrapped around the cylinder, has a knight´s tour unless one of the following two conditions hold: a) m= 1 and n>1; or b) m =2 or 4 and n is even”.

This chapter considered six problems and their respective solutions.

Chapter 6, (pp.79-94), deals with the Klein bottle and other variations. The different interesting ways to identify edges, that is, to look at a rectangular chessboard, produced a new surface, called Klein bottle, for example identify the top and bottom edges of the rectangle just as we did for the torus; and also identify the left and the right edges, but in reverse order. The following theorem due to Watkins solved completely the question: “On a Klein bottle, every rectangular chessboard has a knight´s tour”.

The Möbius strip is the most famous example of a one-sided surface. It is also, another way to identify edges in a rectangular chessboard, just one pair of opposite edges as we did for the cylindrical board, but this time to add a half twist just we did for the Klein bottle. Similarly, the following theorem (Watkins) solved the question: “An m x n chessboard on a Möbius strip, with m rows and n columns, the rows wrapped around the Möbius strip, has a knight´s tour unless one or more of the following three conditions hold: a) m= 1 and n>1; or n=1 and m=3, 4, or 5; b) m =2 and n is even, or m=4 and n is odd; c) n=4 and m =3”.

Since about the middle of the nineteenth century mathematician have had a complete list of all possible surfaces. This list is fully described as the Classification Theorem. Surfaces such as the sphere, the torus and the Klein bottle are called closed, that they are finite, also called two-manifolds, and each of these surfaces has a number assigned to it, the Euler characteristic of the surface. Surface such as the plane is infinite or open.

Other variations, such as, the Euler characteristic of the surface, Klein bottle, torus, etc.; the third dimension; boxes; camel piece, a chess piece used in Persian chess (fourteenth century); triangular honeycombs (1997); three dimensional torus, and so on, are also discussed.

Moreover, this chapter considered four problems and their respective solutions.

Chapter 7, (pp.95-111), is related with the classical and interesting, well-known domination problem. The concept of domination is one of the central ideas in graph theory, and is especially important in the applications of the theory to the real world. A set S of vertices in a graph G is called a dominating set if every vertex in the graph is either in the set S or is adjacent to a vertex in the set S. The domination number if a graph is, then, the minimum size of a dominating set in the graph.

In this chapter on analyzed the covering problem. This problem is defined as follows: for each chess piece: how many chess pieces of an individual type are required to cover an nxn chessboard? It is among the oldest and most studied problems related to the chessboard, and it and its many variations, for example: knights, rooks, bishops, and kings.

The chapter contains, moreover, five interesting problems, stated and solved, that cover the different relevant questions.

The chapter 8, (pp.113-137), is devoted to the intriguing and challenging queens domination problem and other variants. The chapter presents the Spencer-Cockatyne construction, upper and lower bound for the number of queens needed to cover an nxn board, Spencer´s remarkable lower bound, Weakley´s new improved lower bound, etc.

The chapter contains, moreover, three interesting problems, stated and solved, that cover the different relevant questions.

The Chapter 9, (pp. 139-162), is related with domination on other surfaces. In this chapter on take another look at the domination problem for each of the chess pieces and consider what happens on the torus and the Klein bottle for the queen, the knight, the rook, the bishop, and the king. More general result about pieces dominating rectangular toroidal chessboards and on a Klein bottle on presented.

The chapter contains, moreover, seven interesting problems, stated and solved.

In the chapter 10, (pp. 163-189), devoted to the independence problem, on analyzed the concept of independence, closely related to that of domination. The concept of independence is also one of the central ideas in graph theory, and is especially important in the applications of the theory to the real world. Two vertices in a graph are independent if there is no edge joining them. A set of vertices in a graph G is said to be an independent set if no two vertices in S are adjacent. The independence number of a graph G is the cardinal of the maximum independence set. An independent set with this maximum size is called a maximum independent set. The 8-queens problem with all solutions; the n-queens problem, and the Ahrens theorem with the proof given by Yaglom and Yaglom, and Pólya´s doubly periodic solutions; independent rooks; independent knights; independent bishops, and independent kings, on presented.

The chapter contains, moreover, seven interesting problems, stated and solved.

The chapter 11, (pp. 191-212), is related to other surfaces and other variations. In this chapter on treated the independence number for each of the chess pieces on a variety of other surfaces, such as the torus and the Klein bottle. It is interesting the following statements: the 8-queens problem on a cylinder; independent kings on a torus; independent kings on a Klein bottle; combinations of two notions of domination and independence: the covering problem; the upper domination number; the irredundance numbers, and the total domination number.

The chapter is illustrated with five problems, stated and solved.

In the chapter 12, (pp. 211-222), is devoted to the study of Latin squares, a classical problem. A Latin square is an nxn array of the integers 0, 1, 2, ... , n-1, or equivalently, a labeling of the squares of an nxn chessboard with these integers, such that each integer appears once and only once in each row, and once and only once in each column. The constructing Latin squares using the Ball´s method; Eulerian squares, that is, two Latin squares of the same size such that the resulting combination by combining their entries and forming ordered pairs, is such that each the possible n2 ordered pairs occurs exactly once, then the two Latin squares are said to be orthogonal, and the new combined square is called an Eulerian square, or sometimes Graeco-Latin square, because Latin letters might be used for one square and Greek letters for the other; Euler´s conjecture impossibility to construct a pair of orthogonal Latin squares, accordingly with the dimensions of boards, in particular 6x6, is wrong. Beyond n=6, that is, n= 10,14,18,22, and so on, there always exists a pair of orthogonal nxn Latin squares for any n.

The chapter is illustrated with three problems, stated and solved.

Finally, chapter 13, (pp. 223-246) is related with two problems concerning geometric dissection problems in recreational mathematics. The first problem is referred to divide the land into four identical pieces with restrictions, and the second problem is to reconstruct the entire chessboard, breaking into eight pieces.

Then analyzed dominoes; dissecting rectangles into dominoes (the bricklayer´s problem); the De Bruijn´s theorem; trominoes; polyominoes; pentominoes; the remarkable three scaling problems involving pentominoes; hexominoes and beyond; the amazing figure of the final chessboard 51x58, that was covered with the 369 octominoes, that 6 of those have holes in the middle.

The chapter is illustrated with seven problems, stated and solved.

References, (pp. 247-249). They are 41 references.

Index (pp. 251-257)

Definitely the book is high recommended and is of much interest. This book is, no doubt, the newly best exposition of the interconnection between amusing recreational mathematics and the interesting chessboard problems.

I feel sure that it will be of great use both to students of graph theory, geometry, topology and mathematics, in general, and captivate to scholars, instructors, chess enthusiasts, puzzle devotees, and to those intervening in amusing and recreational mathematics.

Finally, in short, the great resource to Professor Watkins´s proper tone ensures total attention from the audience to amusing and recreational mathematics, into the adventure proposed, by this challenging and remarkable book.

Reviewer:
Francisco José Cano Sevilla
Affiliation:

## A textbook of Graph Theory

Author(s):
R. Balakrishnan and K. Ranganathan
Publisher:
Springer. Springer Science + Business Media. Universitext. Springer. New York- Heidelberg- Dordrecht-London.2012. Second Edition, xii, 292 p. 204 illustrations. Hardcover
Year:
2012
ISBN:
: 978-1-4614-4528-9; 978-1-4614-4529-6 (eBook); DOI 10.1007/978-1-4614-4529-6;ISSN 0172-5939 (print); 2191-6675(electronic, online)
Price (tentative):
From 49.86$(eBook) to 60.95$ (Hardcover).
Short description:

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 new extensively revised and updated, also includes two new chapters, one on domination in graphs and another on spectral properties of graphs: a discussion on graph energy, a topic of current interest in spectral graph theory. It does not presuppose deep knowledge of any branch of mathematics

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-Nash-Williams 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 non-hamiltonicity of the Tutte graph on 46 vertices, and a concrete application of triangulated graphs.

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.

This textbook provides a solid background in the basic topics of graph theory, and is intended for a graduated or advanced undergraduate or beginning graduate course in graph theory, or mathematics, or computer science, and as reference for the researcher.

URL for publisher, author, or book:
www.springer.com/series/223
MSC main category:
05 Combinatorics
MSC category:
05CXX, 68R10, 05C30, 81Q30, 81T15
Other MSC categories:
05B15, 68RXX, 90B15, 90B18, 90C35, 92E10, 94C15.
Review:

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: mathbala@sify.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.

Reviewer:
Francisco José Cano Sevilla
Affiliation:

## Graphs, networks and algorithms

Author(s):
Dieter Jungnickel
Publisher:
SPRINGER SCIENCE + BUSINESS MEDIA.BIRKHÄUSER. Springer Heidelberg New York Dordrecht London.2013. 4th edition, XX, 675 p. 211 Illustrations.Hardcover.
Year:
2013
ISBN:
: 978-3-642-32277-8 (Print), 978-3-642-32278-5 (eBook-Online) ISSN 1431-1550, Algorithms and Computation in Mathematics, volume 5.
Price (tentative):
From 59.49€ (eBook) to 72.75€ (Hardcover).
Short description:

This new edition has been thoroughly revised and updated, even though the changes are less extensive than above editions. Of course, the general aims of the book have remained the same. In particular, some material has been added: more on NP-completeness (especially on dominating sets), a section on the Gallai-Edmonds structure theory for matchings, and about a dozen additional exercises—as always, with solutions. Moreover, the 1-factor theorem has been completely rewritten: contains a short direct proof for the more general Berge-Tutte formula. Several recent research developments are discussed and quite a few references have been added.

With update material, additional exercises and new references, this thoroughly revised new edition of this book retains the excellent attributes yet considered: it is clear writing, understandable, well-written, good organization, comprehensive coverage of essential theory, self-contained, highly recommended and well-chosen applications, that it convert in an excellent, challenging, intriguing, and powerful textbook, due to the substantial development effort.

The book contains 15 chapters. This standard book beginning from the very basic definitions of graph theory, quickly creating and building an account of theorems, lemmas, and finally, a complete collection of algorithms on graphs and networks. There are many exercises and examples, and the list of references is extensive.

This book is a first course or class on graphs, networks and algorithms, and is indispensable for everybody who has to teach combinatorial optimization. The well-worked solutions to the exercises, or hints for some, are indispensable for the students, or readers, does not remain helpless. It is very helpful and suitable for graduate courses in combinatorics, as well as for independent study and research by students, teachers, professionals and researcher in this area.

URL for publisher, author, or book:
www.springer.com. For further volumes: http://www.springer.com/series/3339
MSC main category:
05 Combinatorics
MSC category:
: 05CXX, 11TXX, 11Y40, 11Y16, 11E12, 11R29, 34B45, 49MXX, 65KXX
Other MSC categories:
65K05, 68R10, 90B18, 90 CXX, 90C27, 90C35, 94C15.
Review:

This new edition has been thoroughly revised and updated, even though the changes are less extensive than above editions. Of course, the general aims of the book have remained the same. In particular, some material has been added: more on NP-completeness (especially on dominating sets), a section on the Gallai-Edmonds structure theory for matchings, and about a dozen additional exercises—as always, with solutions. Moreover, the 1-factor theorem has been completely rewritten: contains a short direct proof for the more general Berge-Tutte formula. Several recent research developments are discussed and quite a few references have been added.

With update material, additional exercises and new references, this thoroughly revised new edition of this book retains the excellent attributes yet considered: it is clear writing, understandable, well-written, good organization, comprehensive coverage of essential theory, self-contained, highly recommended and well-chosen applications, that it convert in an excellent, challenging, intriguing, and powerful textbook, due to the substantial development effort.

This standard book beginning from the very basic definitions of graph theory, quickly creating and building an account of theorems, lemmas, and finally, a complete collection of algorithms on graphs and networks. There are many exercises and examples, and the list of references is extensive. Here, a call to the reader, for to work on the exercises to get a better idea of what the terms really mean.

This book is a first course or class on graphs, networks and algorithms, and is indispensable for everybody who has to teach combinatorial optimization. The well-worked solutions to the exercises, or hints for some, are indispensable for the students, or readers, does not remain helpless. It is very helpful and suitable for graduate courses in combinatorics, as well as for independent study and research by students, teachers, professionals and researcher in this area. In short, the excellent book of Jungnickel, ought to available for reference.

The book contains preface to above editions, list of figures (p. i-xx), fifteen chapters: 1.-Basic Graph Theory 2.-Algorithms and Complexity 3.- Shortest Paths 4.-Spanning Trees 5.-The Greedy Algorithm 6.-Flows 7.-Combinatorial Applications 8.-Connectivity and Depth First Search 9.-Colorings 10.-Circulations 11.-The Network Simplex Algorithm 12.-Synthesis of Networks 13.-Matchings 13.- Weighted Matchings, 15.-A Hard Problem: The TSP-Appendices on some NP-Complete Problems, on the solutions for chapter 1 to 15, and on the list of Symbols – Bibliography - Index, in 675 pages.

The first chapter, Basic Graph Theory, (pages 1-33), contains a lot of definitions, and began with an introduction to the well-known Königsberg bridge problem, solved by Leonard Euler in 1736, who established that the solvability depends only on their connection properties. This led to the abstract notion of a graph. Actually, Euler proved much more: he gave a necessary and sufficient condition for an arbitrary graph to admit such a circular walk. His theorem is one of the highlights in the introductory Chap. 1, where we deal with some of the most fundamental notions in graph theory: paths, cycles, connectedness, 1-factors, trees, Euler tours and Hamiltonian cycles, the travelling salesman problem, drawing graphs in the plane, and directed graphs. Then also see a first application, namely setting up a schedule for a tournament, say in soccer or basketball, where each of the 2n participating teams should play against each of the other teams exactly twice, once at home and once away.
In the second chapter, Algorithms and Complexity, (pages 35-63), on study in an intuitive manner what an algorithm is and develop a way to measure the quality of algorithms. In particular, on consider some basic aspects of graph theoretic algorithms such as, for example, the problem of how to represent a graph. The different kinds of representation: edges, incidence, adjacency, matrices, and so on, are given. On formulate with more detail the Hierholzer´s algorithm, in Pascal-like language which allows this book to be used in courses to both on graph theory, combinatorial optimization, or computer science algorithms. Moreover, on introduce some rules for how algorithms are to be described, and on need a way to formulate the algorithms deal with. On illustrate and study these concepts quite thoroughly using two specific examples, namely Euler tours and acyclic digraphs. At the end of the chapter on consider a class of apparently very difficult problems (the so-called NP-complete problems) which plays a central role in complexity theory; on will meet this type of problem over and over again in this book. On deal with five NP-complete problems as the vertex cover, independent set, clique problem, dominating set and the Hamiltonian circuit.
In the third chapter, Shortest Paths, (pages 65-102), on know that one of the most common applications of graphs in everyday life is representing networks for traffic or for data communication. The schematic map of the any motorway system in the official guide, the railroad or bus lines in a public transportation system, and the network of routes an airline offers are routinely represented by graphs. Therefore, it is obviously of great practical interest to study paths in such graphs. In particular, on often look for paths which are good or even best in some respect: sometimes the shortest or the fastest route is required, sometimes on want the cheapest path or the one which is safest—for example, on want the route where on are least likely to encounter a speed-control installation. Thus on study shortest paths in graphs and digraphs in this chapter, i.e., this is a topic whose interest extends far beyond traffic networks. On present some useful theoretical concepts (e.g., the Bellman equations, shortest path threes, acyclic networks and path algebras) as well as the most important algorithms for finding shortest paths (in particular, breadth first search, Dijkstra´s algorithm, and Floyd and Warshall´s algorithm). On also discuss two applications, namely to project scheduling and to finding optimal connections in a public transportation system.
In the fourth chapter, Spanning Trees, (pages 103-134), on obtained some basic results on trees, including the number of trees on n vertices. In this chapter, on study this important class of graphs, the spanning trees, in considerably more detail. After some further characterizations of trees, on study another way of determining the number of trees on n vertices which actually applies more generally: it allows one to compute the number of spanning trees in any given connected graph. Following these theoretical results, the major part of the chapter will be devoted to a network optimization problem, namely to finding a spanning tree for which the sum of all edge lengths is minimal. This problem has many applications; for example, the vertices might represent cities we want to connect to a system supplying electricity; then the edges represent the possible connections and the length of an edge states how much it would cost to build that connection. Other possible interpretations are tasks like establishing traffic connections (for cars, trains or planes) or designing a network for TV broadcasts. On present an interesting characterization of minimal spanning trees and use this criterion to establish the most important algorithms for determining such a tree, namely those of Prim, Kruskal, and Boruvka. Following this, on discuss several further applications (e.g., the bottleneck problem) and spanning trees with additional restrictions. Also on consider Steiner trees (these are trees where it is allowed to add some new vertices) and arborescences (directed trees).
The fifth chapter, The Greedy Algorithm, (pages 135-161), study a method for optimizing over certain set systems, the so-called greedy algorithm. More precisely, it is used for maximizing a weight function on so-called independence systems, the classical instance being the system of spanning forests of a graph. The greedy strategy is rather short-sighted: one always selects the element which seems best at the moment. In other words, among all the admissible elements, one chooses that with maximal weight and adds it to the solution being constructed. In general, this simple-minded strategy will not work, but for a certain class of structures playing a very important part in combinatorial optimization, the so-called matroids, it indeed leads to optimal solutions. Actually, matroids may even be characterized by the fact that the greedy algorithm works for them, but there are other possible definitions. On look at various other characterizations of matroids and also consider the notion of matroid duality. Following this, on establish the greedy algorithm as an approximation method for maximization on independence systems which are not matroids. On examine the efficiency of this approach, that is, on derive bounds for the ratio between the solution given by the greedy algorithm and the optimal solution, and also look at the problem of minimization on independence systems. Finally, in the last section, on discuss some further generalizations of matroids and their relationship to the greedy algorithm.
In the sixth chapter, Flows, (pages 163-218), on investigate flows in networks: how much can be transported in a network from a given source s to a specified sink t if the capacities of the connections are prescribed? Such a network might model a system of pipelines, a water supply system, or a system of roads. With its many applications, the theory of flows is one of the most important parts of combinatorial optimization. In Chap. 7 on encountered several applications of the theory of flows within combinatorics, and flows and related notions will appear again and again throughout the book. Because of their fundamental importance, on discuss network flows in considerable depth. In particular, on give detailed presentations of four of the most important algorithms solving this problem, namely the Ford and Fulkerson´s labeling algorithm, a modification of this algorithm by Edmonds and Karp, Dinic´s algorithm, the Malhotra, Kumar and Mahaswari´s (MKM) algorithm, for constructing blocking flows, and the preflow-push of Goldberg and Tarjan´s algorithm, surely the algorithm most widely currently.
In the seventh chapter, Combinatorial Applications, (pages 219-249), on use the theorems of Ford and Fulkerson about maximal flows to prove some central results in combinatorics. More precisely, on use flow theory to study disjoint paths in graphs (Menger´s theorem), matchings in bipartite graphs (König´s theorem), transversals of set families (the marriage theorem), the combinatorics of matrices, partitions of directed graphs (Dilworth´s theorem), partially ordered sets, parallelisms of complete designs (Baranyai´s theorem), and the supply and demand, the Gale-Ryser´s theorem. In particular, transversal theory can be developed from the theory of flows on networks; this approach was first suggested in 1962 in the book by Ford and Fulkerson. Compared with the usual alternative approach, of taking Philip Hall’s marriage theorem—which we will treat in Sect. 7.3—as the starting point of transversal theory, this way of proceeding, has a distinct advantage: it also yields algorithms allowing explicit constructions for the objects in question.
The eighth chapter, Connectivity and Depth First Search, (pages 251-273), treat algorithmic questions concerning k-connectivity and strong connectivity. To this end, on introduce a further important strategy for searching graphs and digraphs (besides BFS), namely depth first search—which may also be thought of as a strategy for traversing a maze. In addition, on present various theoretical results, such as characterizations of 2-connected graphs and of edge connectivity.
In the ninth chapter, Colorings, (pages 275-293), on look at a subject occurring quite often in graph theory: colorings. The two fundamental major results in this area, namely the theorem of Brooks on vertex colorings and the theorem of Vizing on edge colorings, are given. As an aside, on explain the relationship between colorings and partial orderings, and briefly discuss perfect graphs. Moreover, on consider edge colorings of Cayley graphs; these are graphs which are defined using groups. Finally, on turn to map colorings: the Heawood’s five color theorem and report on the famous four color theorem are presented.
The tenth chapter, Circulations, (pages 295-358), considered the simplest kind of flow problems, namely the determination of maximal flows in a network, in considerable detail. The present chapter deals with generalizations of the flows that worked with so far. For example, quite often there are also lower bounds on the capacities of the edges given; or one may seek a maximal flow which is optimal with respect to a given cost function on the edges. To solve these (and even more general) problems, it proves helpful to remove the exceptional role of the source and sink vertices s and t by requiring the flow preservation condition for all vertices, including s and t. This leads to the notion of circulations on directed graphs. There are many interesting applications of this more general concept. To a large part, these cannot be treated using the theory of maximal flows as presented before; nevertheless, the methods of Chap. 6 will serve as fundamental tools for the more general setting. On shall begin with a rather thorough theoretical investigation of circulations and then develop efficient algorithms for finding an optimal circulation (or showing that no such circulation can exist), Klein´s algorithm, Busacker and Gowen´s algorithm, and the OPT´s algorithm, a modification of Ford-Fulkerson´s algorithm; this turns out to be considerably more difficult than determining an ordinary maximal flow. Finally, as an application of circulations, also consider the construction of rather good codes (a mathematical concept used to deal with data corruption by allowing the correction of errors) using the cycle spaces of graphs.
In the eleventh chapter, The Network Simplex Algorithm, (pages 359-378), for practical applications, by far the most useful optimization algorithm for solving linear programs is the celebrated simplex algorithm. This suggests trying to apply this algorithm also to problems from graph theory. Indeed, the most important network optimization problems may be formulated in terms of linear programs; this holds, for instance, for the determination of shortest paths, maximal flows, optimal flows, and optimal circulations. Nevertheless, a direct application of the usual simplex algorithm would make no sense, as the resulting linear programs would be unwieldy and highly degenerate. These two problems are avoided by using a suitable graph theoretic specialization of the simplex algorithm, the so-called network simplex algorithm. This algorithm is usually formulated in terms of a standard problem which we will introduce in the first section; all other problems of practical interest admit easy transformations to this problem. Throughout this book, on emphasize the graph theoretical aspects of combinatorial optimization while avoiding the theory of linear programming as much as possible. In view of this philosophy, it is very fortunate that the network simplex algorithm may be dealt with entirely in graph theoretic terms, with no need to appeal to linear programming; such a presentation will be given here.
The twelfth chapter, Synthesis of Networks, (pages 379-403), on worth that up to now on have considered flows or circulations only on a given network. But it is also quite interesting to study the reverse problem of designing a network—as economically as possible—on which a flow meeting given requirements can be realized. In practical terms, one might think of planning a system of roads. In the present chapter, on mainly study two types of network design problems. On the one hand, the case where all edges may be built with the same cost, and where we are looking for an undirected network with lower bounds on the maximal values of the flows between any two vertices. Both the analysis and design of such symmetric networks use so-called equivalent flow trees; this technique also has an interesting application for the construction of certain communication networks which will be the topic of section 12.4, cut trees, pages 395-399). On the other hand, addressed the question of how one may increase the maximal value of the flow for a given flow network by increasing the capacities of some edges by the smallest possible amount.
The thirteenth chapter, Matchings, (pages 405-439), deals with the problem of finding maximal matchings in arbitrary graphs; for the bipartite case, an efficient algorithms was already given in Sect. 7.2, (König´s theorem). In contrast to this case, it is not at all easy to reduce the general case to a flow problem, though this is possible (but beyond the scope of the present book). Nevertheless, the notion of an augmenting path can be modified appropriately to help enlarge a given matching. On present the best known efficient algorithm, which rests on this concept and is due to Edmonds; this turns out to be much more difficult than in the bipartite case. Also on present the most important theoretical results on matchings in general graphs: the 1-factor theorem of Tutte characterizing the graphs with a prefect matching, the more general Berge-Tutte formula giving the size of a maximal matching, and the Gallai-Edmonds structure theory.
In the fourteenth chapter, Weighted Matchings, (pages 441-479), on consider matchings of maximal cardinality. The present chapter discusses the more general case of weighted matchings, that is, the problem of finding a matching of maximal weight (with respect to a given weight function on the edges). In the bipartite case, this problem is equivalent to the assignment problem considered before, so that the methods discussed in chapter 10 apply. Nevertheless, on give a further algorithm for the bipartite case, the so-called Hungarian algorithm, as this is one of the best known and most important combinatorial algorithms. Then on proceed by explaining the connection between matching problems and the theory of linear programming, even though generally avoid linear programs in this book. On need this to see the deeper reason why the approach used in the Hungarian algorithm works: its success is due to the particularly simple structure of the corresponding polytope, and ultimately to the total unimodularity of the incidence matrix of a bipartite graph. In this context, the reason why the determination of maximal matchings (weighted or not) is considerably more difficult for arbitrary graphs than for bipartite ones will become apparent. As it would make little sense to describe an algorithm for the weighted matching problem in general graphs without using more of the theory of linear programming, no such algorithm is presented in this book. Nevertheless, on include three interesting applications of weighted matchings: the so-called Chinese postman problem (featuring a postman who wants an optimal route for delivering his mail); the determination of shortest paths for the case where edges of negative weight occur; and the decoding of graphical codes. On conclude the chapter with a few remarks about matching problems with certain additional restrictions—a situation which occurs quite often in practice; on see that such problems tend to be inherently more difficult.
The fifteenth chapter, A Hard Problem: The TSP, (pages 481-526), on concentrated on those optimization problems which allow efficient (that is, polynomial time) algorithms. In contrast, the final chapter deals with an archetypical NP-complete problem: the travelling salesman problem already introduced in the first chapter. It is one of the most famous and important problems in all of combinatorial optimization—with many fold applications in such diverse areas as logistics, genetics, telecommunications, and neuroscience—and has been the subject of extensive study for about 60 years. On see yet already that no efficient algorithms are known for NP-complete problems, and that it is actually quite likely that no such algorithms can exist. Now on address the question of how such hard problems—which regularly occur in practical applications—might be approached: one uses, for instance, approximation techniques, heuristics, relaxations, post-optimization, local search, and a complete enumeration. On explain these methods only for the TSP, but they are typical for dealing with hard problems in general. Also brie and explain the idea of a further extremely important approach—via polyhedra—to solving hard problems and present a list of notable large scale TSPs which were solved to optimality.
In the appendix A, Some NP-Complete Problems, (pages 527-536), on present a brief list of NP-problems, on restrict to problems which either mentioned before or are closely related to subject treated in this book. A much more intensive list can be found in the Bible of NP-problems, and the excellent text of Garey and Johnson (1979).
Appendix B: Solutions for Chapter, Chapter 1 to 15, (pages 537-621), contains solutions (or extended hints) to virtually all the proposed exercises. For difficult exercises, on include more details, if an exercise is of a purely computational nature, on usually state the result.
In the appendix C, List of Symbols, (pages 623-627), consist in two parts, the first about general symbols, contains those symbols which are more or less standard, and the second about special symbols, includes the special symbols of graph theory.
References, (pages 629-659), included an intensive and update bibliography, with 766 references.
Index, pages 661-675
Finally, in short, with update material, additional exercises and new references, this thoroughly revised fourth edition of this book retains the excellent attributes yet considered in above editions: it is clear writing, understandable, well-written, good organization, comprehensive coverage of essential theory, self-contained, highly recommended and well-chosen applications, that it convert in an excellent, challenging, intriguing, and powerful textbook, due to the substantial development effort.

This book is a first course or class on graphs, networks and algorithms, and is indispensable for everybody who has to teach combinatorial optimization. The well-worked solutions to the exercises, or hints for some, are indispensable for the students, or readers, does not remain helpless. It is very helpful and suitable for graduate courses in combinatorics, as well as for independent study and research by students, teachers, professionals and researcher in this area. In brief, the excellent book of Jungnickel, ought to available for reference.

Reviewer:
Francisco José Cano Sevilla
Affiliation: