Eulerian Graphs and Related Topics

Eulerian Graphs and Related Topics

1st Edition - May 2, 1990

Write a review

  • Editor: H. Fleischner
  • eBook ISBN: 9780080867854

Purchase options

Purchase options
DRM-free (PDF)
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order

Description

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. D0-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 &kgr;1-Transformations. Transformation of Eulerian Trails in Digraphs. Final Remarks and Some Open Problems. Exercises.
    Bibliography. Index.

Product details

  • No. of pages: 407
  • Language: English
  • Copyright: © North Holland 1990
  • Published: May 2, 1990
  • Imprint: North Holland
  • eBook ISBN: 9780080867854

About the Serial Editor

H. Fleischner

Affiliations and Expertise

Institute for Information Processing, Austrian Academy of Sciences, Vienna, Austria

Ratings and Reviews

Write a review

There are currently no reviews for "Eulerian Graphs and Related Topics"