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.

Assume an at least $2$-vertex connected, cubic, bipartite, planar graph $G$ that contains a Hamilton cycle (HC) $abcdefg\dots yx\dots za$ (in fact $G$ would then have at least four HCs, see here; it is $yx$ due to the picture I've drawn below and an assumption disproven here). My question is:

How can one deviate from a given Hamilton cycle in such a way, that one introduces exactly two errors, resp. does introducing two errors rely on certain subgraphs?

By errors I mean, that two vertices are met twice, while two others are not met at all.


EDIT: To be a little more specific: The Hamilton cycle and the deviation from it with two errors both start and end at the same vertex and are of the same length. We don't add or remove edges.


With the notation above the HC would be e.g. $adef\color{red}{ef}\dots yx \dots za$, so the $\color{grey}{cd}$-edge is missing. I found three possibilities that are PAINTed below. Let the edges of the HC be coloured in $\color{green}{green}$ and edges that introduce errors in $\color{red}{red}$. $\color{black}{Black}$ edges don't contribute to the case under investigation.

enter image description here

Figure 1: We can introduce two errors if we go directly from $a$ to $d$, thereby miss $bc$, and then:

  1. use backtracking along the HC $ad\dots ef\color{red}{ef}\dots yx$ $\scriptstyle \text{(this can happen at any edge along the HC)}$
  2. use backtracking aside the HC $ad\dots e\color{red}{xe}f\dots yx$ $\scriptstyle \text{(this also can happen everywhere on the HC)}$ or
  3. make a detour at a second square $ad\dots e\color{red}{xy}f\dots yx$ $\scriptstyle \text{(only here we need a 2nd square)}$.

EDIT For Figure 1)ii. I found another version without backtracking:

Let the part of the HC be $\dots abcd\dots ef \dots yx\dots$, so that there is another cycle part $C_{fy}$ joining $f$ and $y$. Then two errors can be introduced as follows:

  • make the usual shortcut at a square, missing the $bc$-edge
  • go from $e$ to $x$
  • walk along $C_{fy}$ in the opposite direction
  • again go from $e$ to $x$, which is traversed twice

You may think of backtracking as a $2$-cycle. This variant may also happen everywhere.


Figure 2: "$\color{blue}4$-$\color{goldenrod}2$-hexagon": Again the original HC $\underbrace{abcd}_{\color{blue}4} \dots \underbrace{yx}_{\color{goldenrod}2}$ is depicted in green. Two errors can be introduced by $a\color{red}{xy}d\dots yx$.


My question rephrased:

$\hskip1.3in$ Are these subgraphs the only ones to introduce two errors?

Some remarks:

  • In Figure 1 the vertices $d$ and $e$ don't need to be adjacent as indicated by the dashed line.
  • In both figures, I think (not sure) that I could have also chosen $yx$ at the end.
  • I tried to use the "$2$-$2$-$2$-hexagon" (where Hamilton runs through like $ab...cd...yx$, so without the $bc$-, $dy$- and $xa$-edges) without success
  • and sorry for the PAINT work (feel free to improve it!)...

.. and I'm pretty sure that the answer is no, see below...


EDIT: Some more remarks concerning a general solution

I also thought about a more general approach by using $n$th powers of adjacency (sub)matrices, which corresponds to doing $n$ steps on the subgraphs. It's even possible to exclude backtracking as you can read here.

But since the the set of adjacency (sub)matrices, i.e. the (sub)graphs sould be the result of such an approach, I admit that for now, I don't know how to work this out. How does the HC come into play then?


Thanks for your help and special thanks to Brian Rushton,...

share|improve this question
    
What's the motivation for this? It seems like something that underlies an interesting problem in another area. How did you come to it? –  Brian Rushton Dec 30 '12 at 4:30
    
Would $abeafbg\ldots za$ count as a two-error path? –  Hagen von Eitzen Jan 1 '13 at 22:52
    
@Hagen Yes you miss cd and get ab twice. Do you have another subgraph? Sorry the late answer... –  draks ... Jan 3 '13 at 13:05
add comment

2 Answers

Just to clarify, it seems like you want your deviation to result in an edge path still (no jumping from one vertex to another). Is that right? In fact, it seems you want a closed edge path, one that starts and stops at the same vertices.

When you introduce your first kind of error (missing two vertices completely), you have to remove three line segments, the ones going into, between, and out of the pair of points (call them $a$ and $b$). Removing these breaks the closed circuit into a single arc, whose end points must be connected by some new path to form a new closed circuit. Any such path will either:

  1. Go directly from $a$ to $b$, or
  2. Go through some even number of other points on the way to $b$ (even by bipartiteness).

In case 1, the three deleted edges and the new edge start and end at the same points, and so they form a simple closed curve separating the plane. So we get a square, possibly with part of the graph inside and part outside. I do not know if your conditions prevent this possibility. We then need to go through two vertices an extra time. So we can only do this by adding a new edge somewhere. We can either follow this new edge by its inverse, and continue onward (I.e. backtracking) or not. If not, call the vertex we labded at x. We must go over some subsequent edge to a point y. However, I believe your figure 3 is false, as x and y need not be connected by an edge of the Hamiltonian cycle. In any case, this can't go on forever, as we can't visit any other vertex twice, so we must return immediately to the place where we left off (f in your picture). As above, this does give a square, although it may be non-empty inside.

In case 2, our new path can only go through two other vertices, since otherwise we added too many errors. Thus, we must have a hexagon, although, again, some of the grah might be inside of the hexagon and some outside.

So, the only things not covered by your pictures are:

  1. The square/hexagon might contain parts of the graph inside and outside at the same time.
  2. The new edge added between x and y might not be an edge in the old Hamiltonian cycle.

This proof method should generalize easily, although I haven't thought it through. Adding twice as many errors either gives copies of the above errors, or octagon errors, etc. I may post more. Thanks for sharing your problem! Let me know if there are any problems in my analysis.

share|improve this answer
    
Brian, thanks for your answer, here are mine: Yes, the path should be closed (it was/is a cycle) and of the same length as the original HC. Not sure if this is called an edge path, but it sounds right. (i)But I don't want to remove/add edges to the graph. (ii)To admit the drawing are a little wrong since some of the vertices miss the cubic property (I will update it). (iii) Also "2 squares" doesn't really fit. I removed the $ex$/$fy$-edge(s) (see the post revisions), because you don't need them, to introduce two errors. –  draks ... Dec 30 '12 at 15:54
    
(iv) How is Figure 3 false? When the original HC is $abcd..ef..yx$ and you have exactly these two 2 squares (here the subtitle is correct), you could introduce two errors if take the path $ad\dots e\color{red}{xy}f\dots xy$. Maybe a picture of yours would help. Thanks for your time so far... I will put some of my motivation in the next edit together with some more clarifications... –  draks ... Dec 30 '12 at 15:58
    
Figure three isn't false, it just splits into two cases. The points x and y might not have a green edge between them; you can think of the path going into x, diving down and to the left and coming back up and to the right to y in a kind of "hairpin" turn. –  Brian Rushton Dec 31 '12 at 13:18
    
What if the original path is abcd...ef...y...x and the new path is abcd...exyf...y...x? That's what I was saying;I should draw a picture, but I'm doing this n an iPad. –  Brian Rushton Jan 2 '13 at 1:46
    
Where do you go from the second $y$? To $f$,$x$ or back to where you came from (call it $t$), but anyway you introduce more than two errors. Draw the picture by hand, make a photo and post that. –  draks ... Jan 2 '13 at 19:00
show 1 more comment
up vote 1 down vote accepted

Ok, I think one can split the problem into two parts on two subgraphs:

  1. Miss two vertices and
  2. meet two vertices twice.

This was already indicated in Fig.1, where the upper square subgraph was always the same and only the lower one varied. When you miss two vertices, the number of edges used in that subgraph drops by two as well ( two additional edges are used in the "meet twice" case).

I think I found another way to miss two vertices: enter image description here

Combine this with, let's say backtracking or any other option to meet vertices twice from the question's figure 1 (edit: or the example below). I think is really different from the way above shown, since the vertices that are missing are not connected by an edge as above.

Let the 10-vertex-Hamiltonian path be $abcdefghij$, then the two error variant is 8 vertices long and may be written as $afghicdj$. It should be possible to extend the inner hexagon to larger structures by introducing additional edges into the outer squares.

EDIT

Here's another example of how to meet two vertices twice: enter image description here

Let the part of the HC be $abcd$, then the path on the rhs is $abadcd$, where $a$ and $d$ are met twice. The difference to example 1.iii.(lower part) is the HC we start out with.

So the above shown are not the only onces...


Now for something analytical. Think of $A$ as the adjacencey matrix of the subgraph with $n$ vertices (without the black edges going out of the subgraph itself, so it might not be cubic anylonger, which is not important for the moment). A Hamilton path would need $n$ steps to traverse it. Starting from $\vec {v_{start}}=(1,0,0,\dots ,0)^T$ we get $\vec{v_{final=n}}=A^n\vec{v_0}=(a_1,a_2,\dots,a_n)^T$ where $a_k$ denotes the number of ways from the starting vertices to vertex $k$. So $a_n$ would contain the Hamiltonian paths next to other paths that reach vertex $n$ in $n$, but maybe don't touch all other points.

To miss two vertices wee need to check if it's possible to reach $n$ after $n-2$ steps as well and meanwhile meet $n-2$ vertices. Similar for the "meet twice" case.

Instead of using $A^n$, one could use propagation without backtracking (see here), to get rid of some of the obsolete paths (at least in the "missing" case, in the "meeting" case backtracking should be allowed), but, all in all and after all I personally think that one has to check infinitely large subgraphs for the property sketched above, which is not possible in finite time.

The question remains, if these are all possible subgraphs if the largest face degree is $6$?

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.