Eulerian graphs and related topics

Author(s)

• Fleischner, Herbert

Bibliographic Information

Eulerian graphs and related topics

Herbert Fleischner

（Annals of discrete mathematics, 45, 50）

North-Holland , Distributors for the U.S.A. and Canada, Elsevier Science, 1990-

• pt. 1, v. 1
• pt. 1, v. 2

Note

Includes bibliographical references and index

Description and Table of Contents

Volume

pt. 1, v. 1 ISBN 9780444883957

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.

Table of Contents

• 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.

Volume

pt. 1, v. 2 ISBN 9780444891105

Table of Contents

VIII. Various Types of Closed Covering Walks. Double Tracings. Value-True Walks and Integer Flows in Graphs. The Chinese Postman Problem. The Chinese Postman Problem for Graphs. Some Applications and Generalizations of the CPP. Applications. t -Joins, t -Cuts and Multicommodity Flows. Hamiltonian Walks, the Traveling Salesman and Their Relation to the Chinese Postman. The Directed Postman Problem. The Mixed Postman Problem. The Windy Postman Problem and Final Remarks. Exercises. IX. Eulerian Trails - How Many? ...As Many As...-Parity Results for Digraphs and Mixed Graphs. An Application to Matrix Algebra. The Number is ...- A First Excursion Into Enumeration. The Matrix Tree Theorems. Enumeration of Eulerian Trails in Digraphs and Graphs. On the Number of Eulerian Orientations. Some Applications and Generalizations of the BEST-Theorem. Final Remarks. Exercises. X. Algorithms for Eulerian Trails and Cycle Decompositions, Maze Search Algorithms. Algorithms for Eulerian Trails. Algorithms for Cycle Decompositions. Mazes. Exercises. Bibliography. Index. Appendix: Corrections and Addenda to Volume 1.

by "Nielsen BookData"

Details

• NCID: BA10167174
• ISBN:
  • 0444883959
  • 0444891102
• LCCN: 90007300
• Country Code: ne
• Title Language Code: eng
• Text Language Code: eng
• Place of Publication: Amsterdam ; Tokyo,New York
• Pages/Volumes: v.
• Size: 25 cm
• Classification:
  • LCC : QA166.19
  • DC20 : 511/.5
• Subject Headings:
  • LCSH : Eulerian graph theory
• Parent Bibliography ID:
  • BA00027259