Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-25T09:21:55.279Z Has data issue: false hasContentIssue false
  • English
  • Français

Digraphs with eulerian chains

Part of: Graph theory

Published online by Cambridge University Press:  09 April 2009

D. K. Skilton
D. K. Skilton
Affiliation:
20 Watkins Road, Elermore Vale, N.S.W. 2287, Australia
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

An eulerian chain in a directed graph is a continuous directed route which traces every arc of the digraph exactly once. Such a route may be finite or infinite, and may have 0, 1 or 2 end vertices. For each kind of eulerian chain, there is a characterization of those diagraphs possessing such a route. In this survey paper we strealine these characterizations, and then synthesize them into a single description of all digraphs having some eulerian chain. Similar work has been done for eulerian chains in undirected graphs, so we are able to compare corresponding results for graphs and digraphs.

MSC classification

Secondary: 05C45: Eulerian and Hamiltonian graphs 05C20: Directed graphs (digraphs), tournaments
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 41 , Issue 3 , December 1986 , pp. 298 - 303
Copyright
Copyright © Australian Mathematical Society 1986

References

[1]Eggleton, R. B. and Skilton, D. K., ‘Graphs with eulerian chains’, Bull. Austral. Math. Soc. 29 (1984), 389–399.CrossRefGoogle Scholar
[2]Erdös, P., Grünwald, T., and Vázsonyi, E., ‘Über Euler-Linien unendlicher Graphen’, J. Math. Phys. 17 (1938), 59–75.CrossRefGoogle Scholar
[3]Nash-Williams, C. St. J. A., ‘Decomposition of graphs into closed and endless chains’, Proc. London Math. Soc. 10 (1960), 221–238.CrossRefGoogle Scholar
[4]Nash-Williams, C. St., ‘Decomposition of graphs into two-way infinite paths’, Canad. J. Math. 15 (1963), 479–485.CrossRefGoogle Scholar
[5]Nash-Williams, C. St. J. A., ‘Euler lines in infinite directed graphs’, Canad. J. Math. 18 (1966), 692–714.CrossRefGoogle Scholar