A Hamiltonian graph $G$ of order n is $k-$ordered Hamiltonian for an integer $k$ with $1≤k≤n$ if for every ordered set $S=\{v_1,v_2,…,v_k\}$ of $k$ vertices of $G$, there is a Hamiltonian cycle of $G$ encounter these $k$ vertices of $S$ in the order listed.

a) Let $G$ be a graph of order $n≥3$ such that $deg(v)≥\frac{n}{2}$ for every vertex $v$ of $G$. Show that $G$ is $3-$ordered Hamiltonian.

b) Let $G$ be a graph of order $n≥4$ such that $deg(v)≥\frac{n}{2}$ for every vertex $v$ of $G$. Show that $G$ need not be $4-$ordered Hamiltonian.

c) Show that if $G$ is 4-ordered Hamiltonian graph, then $G$ is 3-connected.

For both a) by Dirac's theorem, I know that $G$ is Hamiltonian, meaning $G$ has a cycle that go through every vertex of $G$. So Let $S=\{a,b,c\}$. We can find a cycle that goes through $S$ by following orders : $abc, acb, bca,bac, cab,cba$. So $G$ is 3-ordered Hamiltonian

for c), I'm still stuck

  • $\begingroup$ 3-ordered Hamiltonian seems to be exactly the same as 'regular' Hamiltonian: for 3 elements you can start at 3 different places and walk in 2 different directions to get all possible permutations. $\endgroup$ – Leen Droogendijk Oct 26 '14 at 17:17
  • $\begingroup$ thanks for your hint I can do part a) and b), but I still can't see the relationship between the 4-ordered Hamiltonian and 3-connected. $\endgroup$ – Diane Vanderwaif Oct 27 '14 at 13:05
  • $\begingroup$ The concept of 'ordered Hamiltonian' is/was unknown to me. Nevertheless I would attempt to help if only you had specified part c in your question. Btw. your solution for part b is wrong. You have used a graph of order 8, but then the minimum degree must be 4. $C_8$ has minimum degree 2. $\endgroup$ – Leen Droogendijk Oct 27 '14 at 14:33
  • $\begingroup$ sorry, I forgot to add part c), $\endgroup$ – Diane Vanderwaif Oct 27 '14 at 17:21
  • $\begingroup$ Please do not forget to remove your incorrect "solution" for part b). $\endgroup$ – Leen Droogendijk Oct 27 '14 at 18:08

Proof of part c)

Note that for c) we need the additional requirement that $|G|>3$: $K_1$ certainly is 4-ordered Hamiltonian according to the given definition, but it is not 3-connected.

Suppose $G$ is not 3-connected. Then it has a vertex cut of size 2, say $\{x,y\}$. Suppose this vertex cut separates vertices $a$ and $b$. Because $G$ is 4-ordered Hamilton, there is a cycle in $G$ that contains the vertices $a,x,y,b$ in this sequence. Now by walking from $a$ to $b$ along this cycle, using the path that avoids $x$ and $y$ we have exhibited an $a,b$-path in $G-\{x,y\}$. Contradiction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.