Problem1I

Problem 1I: Let {Q:=\{1,2,...,q\}}. Let {G} be a graph with the elements of {Q^{n}} as vertices and an edge between {(a_{1},\ldots ,a_{n})} and {(b_{1},\ldots ,b_{n})} if and only if {a_{i}\neq b_{i}} for exactly one value of {i} . Show that {G} is Hamiltonian.

Solution: When {q=1}, the graph is trivial. Suppose {q\geq 2}. When {n=1}, the graph is Hamiltionian since it is a complete graph. Assume that the graph is Hamiltonian for {n=k}. Suppose a Hamiltonain circuit of the graph with vertices {Q^{k}} is {v_{1}v_{2}\cdots v_{q^{k}}v_{1}}. Then if {q} is even, a Hamiltonian circuit for {n=k+1} would be

\displaystyle  (v_{1},1)(v_{2},1)\cdots (v_{q^{k}},1)(v_{q^{k}},2)(v_{q^{k}-1},2)\cdots (v_{1},2)(v_{1},3)(v_{2},3)\cdots (v_{1},q)(v_{1},1).

If {q} is odd, if use the same procedure, we would obtain

\displaystyle  (v_{1},1)(v_{2},1)\cdots (v_{q^{k}},1)(v_{q^{k}},2)(v_{q^{k-1}},2)\cdots (v_{1},2)(v_{2},3)(v_{q^{k}},3)\cdots (v_{q^{k}},q),

which cannot be a circuit. So we use a different procedure, keep the first { q^{k}(q-2)} points same as before, and the last {2q^{k}+1} points are:

\displaystyle  (v_{q^{k}},q-1)(v_{q^{k}},q)(v_{q^{k}-1},q)(v_{q^{k}-1},q-1)(v_{q^{k}-2},q-1)\cdots (v_{1},q-1)(v_{1},q)(v_{1},1).

This is a Hamiltonian circuit for odd {q.} The induction completes.

Notes: If {q} is {\geq 5}, we can find another way to produce Hamiltonian circuit by exchanging the points in the circuit of even {q} case: W.L.O.G., assume there is a path segment { v_{q^{k}-1}v_{q^{k}}v_{1}v_{2}v_{3}} from the Hamiltonian circuit of {Q^{k}} , and these {5} points differ on the same position. Hence exchanging { v_{1},v_{2}} or exchanging {v_{2},v_{q^{k}}} would not destroy the Hamiltonian circuit. Now exchange {(v_{1},1)} , {(v_{2},1)}, and exchange { (v_{2},q)}, {(v_{q^{k}},q)}, then a Hamiltonian circuit forms.

Find a Hamiltonian circuit is not easy. In general case, it is NP hard. However, if the graph has a ‘nice’ representation, it might be easy to find one.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: