Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-09T22:45:28.723Z Has data issue: false hasContentIssue false
  • English
  • Français

Graphs with Eulerian chains

Published online by Cambridge University Press:  17 April 2009

Roger B. Eggleton  and
Donald K. Skilton
Roger B. Eggleton
Affiliation:
Department of Mathematics, The University of Newcastle, Newcastle, New South Wales 2308, Australia.
Donald K. Skilton
Affiliation:
Department of Mathematics, The University of Newcastle, Newcastle, New South Wales 2308, Australia.
Rights & Permissions [Opens in a new window]

Extract

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 graph is a continuous route which traces every edge exactly once. It 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 the graphs which admit such a tracing. This paper derives a uniform characterization of graphs with an eulerian chain, regardless of the kind of chain. Relationships between the edge complements of various kinds of finite subgraphs are also investigated, and hence a sharpened version of the eulerian chain characterization is derived.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 29 , Issue 3 , June 1984 , pp. 389 - 399
Copyright
Copyright © Australian Mathematical Society 1984

References

[1]Eggleton, Roger B. and Skilton, Donald K., “Double tracings of graphs”, to appear in Proceedings of the 11th Australian Conference on Combinatorial Mathematics, The University of Canterbury, 08 29 – 09 2, 1983.Google Scholar
[2]Erdős, P., Grtüwald, T. and Vázsonyi, E., “Über Euler-Linien unendlicher Graphen”, J. Math. Phys. 17 (1983), 59–75.CrossRefGoogle Scholar
[3]Euler, L., “Solutio problematis ad geometriam situs pertinentis”, Commentarii Academiae Scientiarum Imperialis Petropolitanae 8 (1736), 128–140. A readily available English translation is given on pp. 3–8 of N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory 1736–1936, (Oxford University Press 1976).Google Scholar