9860

Hamilton-Connected Harary Graphs

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.)

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+