Hamiltonian Digraphs
Table of Contents

Hamiltonian Digraphs

Definition: A connected digraph $D$ is Hamiltonian if $D$ contains a cycle that itself contains all of the vertices in D. This cycle is known as a Hamiltonian Cycle.

Once again, the conditions for a graph to be Hamiltonian are analogous for both non-directed graphs and digraphs. The only difference is finding a Hamiltonian Cycle formed with arcs instead of edges. For example, the following digraph is Hamiltonian:

Screen%20Shot%202014-04-10%20at%202.43.13%20PM.png

There clearly exists a Hamiltonian cycle, namely the cycle $abcda$. Once again, we should note that just because an underlying graph of $D$ is Hamiltonian, this does not necessarily mean all digraphs with that underlying graph are also Hamiltonian. However, if the underlying graph is NOT Hamiltonian, then any digraph with this underlying graph cannot be Hamiltonian as well. Hence, the orientation of the arcs is vital if we have a Hamiltonian underlying graph.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License