Eulerian Graphs and Related Topics: v.1
Published in May 1990
Book
Hardback
406 pages
978-0-444-88395-7 (ISBN)
Description
The two volumes comprising Part 1 of this work embrace the theme of Eulerian trails and covering walks. They should appeal both to researchers and students, as they contain enough material for an undergraduate or graduate graph theory course which emphasizes Eulerian graphs, and thus can be read by any mathematician not yet familiar with graph theory. But they are also of interest to researchers in graph theory because they contain many recent results, some of which are only partial solutions to more general problems. A number of conjectures have been included as well. Various problems (such as finding Eulerian trails, cycle decompositions, postman tours and walks through labyrinths) are also addressed algorithmically.
The two volumes comprising Part 1 of this work embrace the theme of Eulerian trails and covering walks. They should appeal both to researchers and students, as they contain enough material for an undergraduate or graduate graph theory course which emphasizes Eulerian graphs, and thus can be read by any mathematician not yet familiar with graph theory. But they are also of interest to researchers in graph theory because they contain many recent results, some of which are only partial solutions to more general problems. A number of conjectures have been included as well. Various problems (such as finding Eulerian trails, cycle decompositions, postman tours and walks through labyrinths) are also addressed algorithmically.
The two volumes comprising Part 1 of this work embrace the theme of Eulerian trails and covering walks. They should appeal both to researchers and students, as they contain enough material for an undergraduate or graduate graph theory course which emphasizes Eulerian graphs, and thus can be read by any mathematician not yet familiar with graph theory. But they are also of interest to researchers in graph theory because they contain many recent results, some of which are only partial solutions to more general problems. A number of conjectures have been included as well. Various problems (such as finding Eulerian trails, cycle decompositions, postman tours and walks through labyrinths) are also addressed algorithmically.
More details
Series
Language
English
Place of publication
Oxford
United Kingdom
Publishing group
Elsevier Science & Technology
Target group
College/higher education
Professional and scholarly
Dimensions
Height: 230 mm
ISBN-13
978-0-444-88395-7 (9780444883957)
Copyright in bibliographic data is held by Nielsen Book Services Limited or its licensors: all rights reserved.
Schweitzer Classification
Other editions
Additional editions
Author Unknown | Unknown Author
Eulerian Graphs and Related Topics
E-Book
05/1990
Elsevier
€54.95
Available for download
Content
I. Introduction. II. Three Pillars of Eulerian Graph Theory. Solution of a Problem Concerning the Geometry of Position. On the Possibility of Traversing a Line Complex Without Repetition or Interruption. From O. Veblen's ``Analysis situs''. III. Basic Concepts and Preliminary Results. Mixed Graphs and Their Basic Parts. Some Relations Between Graphs and (Mixed) (Di)graphs. Subgraphs. Graphs Derived from a Given Graph. Walks, Trails, Paths, Cycles, Trees; Connectivity. Compatibility, Cyclic Order of K * v and Corresponding Eulerian Trails. Matchings, 1-Factors, 2-Factors, 1-Factorizations, 2-Factorizations, Bipartite Graphs. Surface Embeddings of Graphs; Isomorphisms. Coloring Plane Graphs. Hamiltonian Cycles. Incidence and Adjacency Matrices, Flows and Tensions. Algorithms and Their Complexity. Final Remarks. IV. Characterization Theorems and Corollaries. Graphs. Digraphs. Mixed Graphs. Exercises. V. Euler Revisited and an Outlook on Some Generalizations. Trail Decomposition, Path/Cycle Decomposition. Parity Results. Double Tracings. Crossing the Border: Detachments of Graphs. Exercises. VI. Various Types of Eulerian Trails. Eulerian Trails Avoiding Certain Transitions. P(D)-Compatible Eulerian Trails in Digraphs. Aneulerian Trails in Bieulerian Digraphs and Bieulerian Orientations of Graphs. D 0 -Favoring Eulerian Trails in Digraphs. Pairwise Compatible Eulerian Trails. Pairwise Compatible Eulerian Trails in Digraphs. A-Trails in Plane Graphs. The Duality between A-Trails in Plane Eulerian Graphs and Hamiltonian Cycles in Plane Cubic Graphs. A-Trails and Hamiltonian Cycles in Eulerian Graphs. How to Find A-Trails: Some Complexity Considerations and Proposals for Some Algorithms. An A-Trail Algorithm for Arbitrary Plane Eulerian Graphs. Final Remarks on Non-Intersecting Eulerian Trails and A-Trails, and another Problem. Exercises. VII. Transformations of Eulerian Trails. Transforming Arbitrary Eulerian Trails in Graphs. Transforming Eulerian Trails of a Special Type. Applications to Special Types of Eulerian Trails and k 1 -Transformations. Transformation of Eulerian Trails in Digraphs. Final Remarks and Some Open Problems. Exercises. Bibliography. Index.