An Eulerian exposition

✍ Scribed by Linda Lesniak; Ortrud R. Oellermann

• Publisher: John Wiley and Sons
• Year: 1986
• Tongue: English
• Weight: 984 KB
• Volume: 10
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190100306

✦ Synopsis

An overview of Eulerian graphs is presented. In particular, characterizations of Eulerian graphs and digraphs as well as algorithms for constructing Eulerian circuits are discussed. A solution to the Chinese postman problem is followed by a study of subgraphs and supergraphs of Eulerian graphs. After an introduction to randomly Eulerian graphs and digraphs, w e conclude with a summary of a variety of results involving enumeration.

We discuss some of the many topics related to Eulerian multigraphs and multidigraphs. In Section 1, results related to characterizations of Eulerian multigraphs and multidigraphs as well as some algorithms are studied. Section 2 concentrates on the Chinese postman problem, which is one example of embedding a graph in an Eulerian multigraph, whereas Section 3 discusses the question of embedding a graph in an Eulerian graph. Further, Section 3 includes results on Eulerian subgraphs of a graph. Section 4 is concerned with randomly Eulerian multigraphs and multidigraphs. We close with a discussion of some enumeration results relating to Eulerian multigraphs and multidigraphs.