Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-05T05:51:35.137Z Has data issue: false hasContentIssue false
  • English
  • Français

On Eulerian and Hamiltonian Graphs and Line Graphs

Published online by Cambridge University Press:  20 November 2018

Frank Harary  and
C. St. J. A. Nash-Williams
Frank Harary
Affiliation:
Universities of AberdeenMichigan and Waterloo
C. St. J. A. Nash-Williams
Affiliation:
Universities of AberdeenMichigan and Waterloo
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.

A graph G has a finite set V of points and a set X of lines each of which joins two distinct points (called its end-points), and no two lines join the same pair of points. A graph with one point and no line is trivial. A line is incident with each of its end-points. Two points are adjacent if they are joined by a line. The degree of a point is the number of lines incident with it. The line-graph L(G) of G has X as its set of points and two elements x, y of X are adjacent in L(G) whenever the lines x and y of G have a common end-point. A walk in G is an alternating sequence v1, x1, v2, x2, …, vn of points and lines, the first and last terms being points, such that xi is the line joining vi to vi+1 for i=1, …, n-1.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 8 , Issue 6 , December 1965 , pp. 701 - 709
Copyright
Copyright © Canadian Mathematical Society 1965

References

1. Chartrand, G., Graphs and their associated line-graphs. Doctoral dissertation, Michigan State University, 1964.Google Scholar
2. Harary, F. and Norman, R. Z., Some properties of linedigraphs. Rendiconti del Circolo Matematico di Palermo 9 (1960), 1-8.Google Scholar
3. Harary, F., Norman, R. Z. and Cartwright, D., Structural models: an introduction to the theory of directed graphs. New York, 1965.Google Scholar
4. Kasteleyn, P. W., A soluble self-avoiding walk problem. Physica 29 (1963), 1329-1337.Google Scholar
5. Sedlaček, J., Some properties of interchange graphs. In Theory of graphs and its applications, (Fiedler, M., ed.) Prague, 1964, 145-150.Google Scholar
6. Whitney, H., Congruent graphs and the connectivity of graphs. Amer. J. Math. 54 (1932), 150-168,Google Scholar