×

An Eulerian exposition. (English) Zbl 0717.05054

Summary: 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, we conclude with a summary of a variety of results involving enumeration.

MSC:

05C45 Eulerian and Hamiltonian graphs
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] van Aardenne-Ehrenfest, Simon Stevin 28 pp 203– (1951)
[2] Bäbler, Comment. Math. Helv. 2 pp 81– (1953)
[3] , and , Graphs and Digraphs. Wadsworth, Belmont (1981).
[4] Berman, Discrete Math. 22 pp 75– (1978)
[5] Berman, Congressus Numerantium 23–24 pp 193– (1979)
[6] , and , Graph Theory 1736–1936. Clarendon Press, London (1976).
[7] Boesch, J. Graph Theory 1 pp 79– (1977)
[8] Bondy, J. Graph Theory
[9] Chartrand, Czech. Math. J. 21 pp 424– (1971)
[10] Chartrand, Elem. Math. 25 pp 101– (1970)
[11] Das, Ars Combin. 12 pp 47– (1981)
[12] Dirac, Math. Scand. 31 pp 319– (1972) · Zbl 0259.05119
[13] Edmonds, Oper. Res. 13 pp b73– (1965)
[14] Edmonds, J. Res. Nat. Bur. Standards 69B pp 125– (1965) · Zbl 0141.21802
[15] Edmonds, Math. Programming 5 pp 88– (1973)
[16] Euler, Comment. Acad. Sci. Petropolitanae 8 pp 128– (1736)
[17] Eulerian graphs. Selected Topics in Graph Theory 2 ( and , eds.), Academic, London (1983) 17–53.
[18] Fleischner, Ars. Combin. 16B pp 177– (1983)
[19] Goodman, SIAM J. Comput. 2 pp 16– (1973)
[20] and , The length of a round of a graph. Kibernetika (Kiev) (1973) 34–37.
[21] Guan, Acta Math. Sinica 10 pp 263– (1960)
[22] Chinese Math. 1 pp 273– (1962)
[23] Harary, Scripta Math. 23 pp 37– (1957)
[24] and , Graphical Enumeration, Academic, New York (1973).
[25] Harary, J. Graph Theory 1 pp 131– (1977)
[26] Hierholzer, Math. Ann. 6 pp 30– (1873)
[27] On nowhere-zero flows in multigraphs. Proc. 5th British Combin. Conf. (1975) 373–378.
[28] Jaeger, J. Graph Theory 3 pp 91– (1979)
[29] Jaeger, J. Combin. Theory 26B pp 205– (1979) · Zbl 0422.05028
[30] Kapoor, Elem. Math. 28 pp 111– (1973)
[31] Kapoor, Fund. Math. 95 pp 189– (1977)
[32] Koh, Nanta Math. Part III 8–9 pp 14– (1974–1975)
[33] Kosaraju, J. Graph Theory 1 pp 379– (1977)
[34] Kotzig, Časopis Pěst. Mat. 84 pp 31– (1959)
[35] Kundu, J. Combin. Theory 17B pp 199– (1974) · Zbl 0285.05113
[36] Lesniak, Rend. Mat. 10 pp 193– (1978)
[37] Lesniak-Foster, Canad. Math. Bull. 20 pp 215– (1977) · Zbl 0357.05060
[38] The number of Eulerian digraphs and homogeneous tournaments. Vesci Adad. Nauk BSSR Ser. Fiz.-Mat. (Russian) (1971) 22–27.
[39] On graphs as unions of Eulerian graphs. Combinatorial Mathematics ( and , eds.), Lecture Notes in Math. 686, Springer-Verlag, Berlin–Heidelberg–New York (1978) 206–209.
[40] Récréations Mathématiques IV, Paris (1921).
[41] Matthews, J. Graph Theory 2 pp 143– (1978)
[42] McKee, Discrete Math. 51 pp 237– (1984)
[43] Mohanty, Bull. Austral. Math. Soc. 20 pp 437– (1979)
[44] Nebeský, Comment. Math. Univ. Carolin. 14 pp 107– (1973)
[45] Nebeský, Czech. Math. J. 29 pp 298– (1979)
[46] Oellermann, Exposition. Math. 2 pp 183– (1984)
[47] Ore, Elem. Math. 6 pp 49– (1951)
[48] The enumeration of graphs. Selected Topics in Graph Theory 1 ( and , eds.), Academic, New York (1978) 385–415.
[49] Read, Canad. J. Math. 14 pp 482– (1962) · Zbl 0105.35501
[50] Contributions to the Theory of Condensation. Ph.D. thesis, University of Michigan, Ann Arbor (1951).
[51] Enumeration of Euler graphs. Proof Techniques in Graph Theory (ed.), Academic, New York, (1969) 147–153.
[52] Seymour, J. Combin. Theory 31B pp 327– (1981) · Zbl 0493.05041
[53] Shank, Ars Combin. 8 pp 107– (1979)
[54] and , Remark on Tarriś method of counting Euler cycles. Kibernetika (Kiev) (1968) 76–80.
[55] Sorokin, Uspehi Mat. Nauk 24 pp 191– (1969)
[56] Sridharan, J. Combin. Theory 13B pp 99– (1972) · Zbl 0243.05107
[57] Toida, J. Franklin Inst. 295 pp 343– (1973)
[58] Tutte, Amer. Math. Monthly 48 pp 233– (1941)
[59] Veblen, Ann. Math. 14 pp 86– (1912–1913)
[60] and , The length of a circuit of a strongly connected graph. Kibernetika (Kiev) (1969) 79–82.
[61] Zelinka, Czech. Math. J. 29 pp 564– (1979)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.