The Zeroth Book of Graph Theory | springerprofessional.de

Springer Professional

nach oben

2021 | Buch

Kapitel lesen Erstes Kapitel lesen

The Zeroth Book of Graph Theory

An Annotated Translation of Les Réseaux (ou Graphes)—André Sainte-Laguë (1926)

verfasst von: Prof. Dr. Martin Charles Golumbic, Prof. André Sainte-Laguë

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Mathematics

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

Einloggen, um Zugang zu erhalten

Über dieses Buch

Marking 94 years since its first appearance, this book provides an annotated translation of Sainte-Laguë's seminal monograph Les réseaux (ou graphes), drawing attention to its fundamental principles and ideas.

Sainte-Laguë's 1926 monograph appeared only in French, but in the 1990s H. Gropp published a number of English papers describing several aspects of the book. He expressed his hope that an English translation might sometime be available to the mathematics community.

In the 10 years following the appearance of Les réseaux (ou graphes), the development of graph theory continued, culminating in the publication of the first full book on the theory of finite and infinite graphs in 1936 by Dénes König. This remained the only well-known text until Claude Berge's 1958 book on the theory and applications of graphs. By 1960, graph theory had emerged as a significant mathematical discipline of its own.

This book will be of interest to graph theorists and mathematical historians.

Anzeige

Inhaltsverzeichnis

Frontmatter

Tracing the topics in Les Réseaux (ou Graphes)

Abstract

In 1926, André Sainte-Laguë published a 65-page monograph entitled Les Réseaux (ou Graphes) which Harald Gropp has called the ‘zeroth’ book on graph theory [248]. The monograph appeared only in French, but Gropp published a number of papers in English between 1993 and 2003 discussing historical aspects and giving a modern interpretation of several topics.

Martin Charles Golumbic, André Sainte-Laguë

I Introduction and definitions

Abstract

1. Generalities. — Topological problems can be viewed from two different perspectives. Either one tries to study continuous deformations that allow one to pass from one curve or surface to a different curve or surface, and this is what is done in particular in Analysis situs [13, 20, 117, 118, 119, 120], or one excludes completely any idea of measure and one considers only relative placement of the objects given.

Martin Charles Golumbic, André Sainte-Laguë

II Trees

Abstract

11. Centers. — Jordan [44], and then Sylvester [46] and Cayley [39], introduced the notion of a center of a tree, which was later used by de Polignac [23] and Delannoy [42].

Martin Charles Golumbic, André Sainte-Laguë

III Chains and cycles

Abstract

16. Interlacings (Eulerian chains and cycles).— The question of whether a given graph admits a chain or cycle passing through every edge exactly once51 was first asked by Euler [25], but must have been known before, as shown for instance by the legend of the signature of Mohammed [68] which he traced with a tip of his sabre, or by the drawings reproduced by Listing [67] or Clausen [52].

Martin Charles Golumbic, André Sainte-Laguë

IV Regular graphs

Abstract

28. Polygonal graphs.— Apolygonal graph is made of vertices of a regular polygon, numbered 0, 1, 2, . . . , n – 1, with edges being sides or diagonals of the polygon.

Martin Charles Golumbic, André Sainte-Laguë

V Cubic graphs

Abstract

38. Bipartite cubic graphs. — A particular case of regular graphs is that of cubic graphs (§7) which serves as a foundation for the statement of the four color problem.

Martin Charles Golumbic, André Sainte-Laguë

VI Tableaux

Abstract

48. Matrices. — The following idea can be found in the writings of many authors, including de Polignac [22], Brunel [51], Chuard [41], and Sainte-Laguë [122].

Martin Charles Golumbic, André Sainte-Laguë

VII Hamiltonian graphs

Abstract

58. Permutations. — Permutations have been extensively studied, and we refer in particular to the interesting overview of Aubry [127]. This area of research immediately leads to the study of graphs.

Martin Charles Golumbic, André Sainte-Laguë

VIII Chessboard problems

Abstract

67. A large number of relations between the vertices or cells of a chessboard are represented by chess pieces.

Martin Charles Golumbic, André Sainte-Laguë

IX Knight’s tour

Abstract

77. At each move, a knight jumps from an even (or white) cell to an odd (or black) cell or vice versa [67]. We deduce, as did Euler [208, 209], that in a closed knight’s tour, the sum of the numbers in each row or column is even.

Martin Charles Golumbic, André Sainte-Laguë

X Conclusion

Abstract

The study of graphs can be pursued in many different ways, and each of the notions defined may initiate new research. We have investigated, to the best of our ability, the complexity of issues that are raised, and the variety of methods that have been employed and are indispensable.

Martin Charles Golumbic, André Sainte-Laguë

Backmatter

Titel: The Zeroth Book of Graph Theory
verfasst von: Prof. Dr. Martin Charles Golumbic
Prof. André Sainte-Laguë
Copyright-Jahr: 2021
Verlag: Springer International Publishing
Electronic ISBN: 978-3-030-61420-1
Print ISBN: 978-3-030-61419-5
DOI: https://doi.org/10.1007/978-3-030-61420-1

Premium Partner