Back to School Savings: Save up to 30% on print books and eBooks. No promo code needed.
Back to School Savings: Save up to 30%
Eulerian Graphs and Related Topics
1st Edition - May 2, 1990
Editor: H. Fleischner
eBook ISBN:9780080867854
9 7 8 - 0 - 0 8 - 0 8 6 7 8 5 - 4
Purchase Options
Save 50% on book bundles
Immediately download your ebook while waiting for your print delivery. No promo code is needed.
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.
No. of pages: 407
Language: English
Published: May 2, 1990
Imprint: North Holland
eBook ISBN: 9780080867854
HF
H. Fleischner
Affiliations and expertise
Institute for Information Processing, Austrian Academy of Sciences, Vienna, Austria