Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-12-02T14:29:52.914Z Has data issue: false hasContentIssue false
  • English
  • Français

A Note on a Theorem of H. L. Abbott

Published online by Cambridge University Press:  20 November 2018

Robert J. Douglas
Robert J. Douglas*
Affiliation:
University of Washington, Seattle, Washington
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.

Let In be the graph of the unit n-dimensional cube. Its 2n vertices are all the n-tuples of zeros and ones, two vertices being adjacent (joined by an edge) if and only if they differ in exactly one coordinate. A path P in In is a sequence x1, …, xm of distinct vertices in In where xi is adjacent to xi+1 for 1 ≤ i ≤ m-1; P is a circuit if it is also true that xm and x1 are adjacent. A path is Hamiltonian if it passes through all the vertices of In. Finally, for vertices x and y in In, we define d(x, y) to be the graph theorectic distance between x and y, i.e., the number of coordinates in which x and y differ.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 13 , Issue 1 , March 1970 , pp. 79 - 81
Copyright
Copyright © Canadian Mathematical Society 1970

References

1. Abbott, H. L., Hamiltonian circuits and paths on the n-cube, Canad. Math. Bull. (5) 9, (1966), 557-562.Google Scholar
2. Gilbert, E. N., Gray codes and paths on the n-cube, Bel. Syst. Tech. J. 37 (1958), 815-826.Google Scholar