# Hamilton-Connected Harary Graphs

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

The Harary graphs are a specifically defined family of graphs on vertices that are -connected and have the minimum possible number of edges for such a graph, . A path is Hamiltonian if it visits all vertices without repetition. This Demonstration illustrates a proof that , where has the form , admits a Hamiltonian path from any vertex to any other. (The start vertex is green and end vertex is red.)

Contributed by: Stan Wagon (March 2013)

(Macalester College)

Open content licensed under CC BY-NC-SA

## Snapshots

## Details

A graph is Hamilton-connected if, for any vertices and , there is a Hamiltonian path from to . In most cases the Harary graphs are circulants, or have a circulant as an edge subgraph (see [1] or [4] for the explicit construction). For example, if is even or is even, then is a circulant graph. And if is odd, then has a circulant as an edge subgraph. When , the circulants that arise are connected, not bipartite, and not a cycle, and therefore the Chen–Quimpo theorem [2] on Hamilton-connectedness of such circulants applies: such graphs are Hamilton-connected.

The case is different, because the circulant graphs that underlie the Harary graphs are not all Hamilton-connected.

• is a bipartite circulant and so is not Hamilton-connected, though it is Hamilton-laceable, by the Chen–Quimpo theorem.

• can be proved to be not Hamilton-connected: there is no path from the unique vertex of maximum degree to the vertex two steps away in the natural circular order.

• is the reason for this Demonstration, which shows the paths that arise in a proof that these graphs are Hamilton-connected. There are several different cases based on the parity of the starting vertex and the position of the target vertex.

References

[1] O. Baudon, J. Bensmail, E. Sopena, "Partitioning Harary Graphs into Connected Subgraphs Containing Prescribed Vertices," preprint. hal.inria.fr/docs/00/68/99/34/PDF/bbs2012.pdf.

[2] C. C. Chen and N. F. Quimpo, "On Strongly Hamiltonian Abelian Group Graphs," *Lecture Notes in Mathematics*, Vol. 884, (K. L. McAvaney, ed.), Berlin: Springer-Verlag, 1981 pp. 23–34. link.springer.com/chapter/10.1007%2 FBFb0091805.

[3] F. Harary, "The Maximum Connectivity of a Graph," *Proceedings of the National Academy of Science*, 48(7), 1962 pp. 1142–1146. www.jstor.org/stable/71730.

[4] D. B. West, *Introduction to Graph Theory*, 2nd ed., Upper Saddle River, NJ: Prentice-Hall, 2001 pp. 150–151.

## Permanent Citation