Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

More specifically, does the stronger statement apply (Georgakopoulos 2009)?

"If $G=(V,E)$ is a 2-connected finite graph and $x \in V(G)$, then $G^2$ has a Hamilton cycle whose edges at $x$ lie in $E(G)$."

I am not sure I understand that statement fully. In the graph $G$ below the line $ag$ (or some other grey line) does not lie in $E(G)$, and I assume the existence of Hamilton cycle requires that line in G^2.

I either proved Georgakopoulos wrong (yeah right) or misunderstood something badly. I got wrong the statement, hamiltonicity, definition of $G^2$, or something else.

The graph in question

$G$ (black) and $G^2$ (black and grey): Graph $G$ (black) and $G^2$ (black and grey)

share|improve this question
    
+1 interesting. BTW: What did you use to draw that? –  draks ... Jan 14 '13 at 12:59
    
@draks... Illustrator CS2. Still having trouble making the letters look like letters in LaTeX ... –  Ohto Nordberg Jan 14 '13 at 13:14
add comment

2 Answers

up vote 3 down vote accepted

Ok as far as I see you are confused about this part of the paper.

Theorem 1. If $G$ is a 2-connected finite graph and $x \in V(G)$, then $G^2$ has a Hamilton cycle whose edges at $x$ lie in $E(G)$.

What this means is the following. Let $x \in V(G)$ be a vertex incident with the edges $\{e_1,e_2,\ldots,e_k\}$ in $G.$ Then there exist a Hamiltonian cycle $C$ in $G^2$ such that the edges incident with $x$ in $C$ are in $\{e_1,e_2,\ldots,e_k\}.$

Hopefully this clears your confusion?

share|improve this answer
    
Guess I do need more clarification ... Say in this case, vertex $g \in V(G)$ is incident with the edges $fg \in E(G)$ and $gb \in E(G)$. There does exist Hamiltonian cycle $C=\{agbcdefa\}$ in $G^2$. Now the edge $ag$ is incident with g but is not in E(G). –  Ohto Nordberg Jan 14 '13 at 13:26
    
@OhtoNordberg Yes. The statement does not claim that every Hamiltonian cycle has this property but that there IS such a cycle. And this is true since you can take $g \mapsto f \mapsto e \mapsto a \mapsto c \mapsto d \mapsto b \mapsto g$ and you see that it contains $fg$ as well as $bg$ –  Jernej Jan 14 '13 at 13:40
    
Ok, so what the statement is saying, is that $C$ (or some Hamilton cycle of $G^2$) will have a vertex whose incident edges are all edges of $G$? –  Ohto Nordberg Jan 14 '13 at 13:56
    
No. What it says is that if you fix a vertex $x \in G$ you can find such a Hamiltonian cycle $C$ of $G^2$ that the incident edges of $x$ in $C$ are also the incident edges of $x$ in $G$ that is, they are from $G$ –  Jernej Jan 14 '13 at 14:03
    
Ok, now I get it, thanks! –  Ohto Nordberg Jan 16 '13 at 15:36
add comment

The question has actually 3 parts, and here is answer to the two first ones.

The graph $G$ in question is 2-connected, because no two vertices can be separated by removing one vertex.

The graph $G$ is not hamiltonian. According to this paper (page 7 theorem 2), order of $S$ must be greater than or equal to the number of components of the graph $G-S$ for $G$ to be hamiltonian.

You can think of the proof inductively: when you remove a vertex from a circle, it either keeps the number of components same or adds precisely one component to the graph $G-S$. When you remove one more vertex, number of components increase only if the removed vertex is not adjacent to any previously removed vertex.

In graph $G$ when $S={f,b}$, number of components of the graph $G-S$ is 3, which is greater than $|S|=2$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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