### Mathematics Research Projects

## Project 4: Hamiltonian Circuits
Arising from Coded Paths

in 3-valent Plane Graphs

Let G be a plane 3-valent graph and e be one of its edges. Suppose
that by moving along some edge one can generate a circuit which:

a. Closes into a simple closed curve.

b. Passes through each vertex of the graph once and only once
(i.e. Hamiltonian circuit) by following a "coded sequence"
over and over again.

Examples of coded sequences are: L, R, L, R, .... and L, L, R,
R, L, L, R, R, .... where L and R refer to making left and right
turns, respectively, when one gets to the vertex at the end of
an edge.

For example, Figure 1 shows an example of a graph where this occurs
for the the L, R code. The edge e is shown and an arrow indicates
the direction of motion along e. The dark edges are those that
are generated by applying the L, R code.

Figure 1
**Problems**

1. Determine which 3-valent plane graphs have hamiltonian circuits
generated by the L,R code.

2. Determine which 3-valent plane graphs have hamiltonian circuits
generated by the L,L,R,R code; by the L,R,R,L code.

**Extensions**

1. Extend your results to graphs which have valence other than
3.

**References**:

1. Ore, O., Graphs and their Uses, Mathematical Association of
America, Washington, 1963. (There is a new revised edition prepared
by R. Wilson.)

2. West, D., Graph Theory, Prentice-Hall, Englewood Cliffs, 1996.

Previous |
Home |
Glossary |
Next

**Joseph Malkevitch**

*Department of Mathematics and Computing*

York College (CUNY)

Jamaica, New York 11451-0001

email: malkevitch@york.cuny.edu

(Comments and results related to the project above are welcome.)

**Acknowledgements**

Some of this work was prepared with partial support from the National
Science Foundation (Grant Number: DUE 9555401) to the Long Island
Consortium for Interconnected Learning (administered by SUNY at
Stony Brook, Alan Tucker, Project Director).