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.

I am no graph-theory expert, but I've been thinking about this problem for a long time.

Let $G_n$ be the $n$-dimensional, infinite, unit-square-grid graph, i.e. the graph whose vertices are the points of $\mathbb{Z}^n$ and that has one edge between each couple of vertices separated by a Euclidean distance of 1.

I know that, for any $d$ in $\mathbb{N}$, the set $\mathbb{Z}^d$ is countably infinite, i.e. one can find a bijection between $\mathbb{N}$ and $\mathbb{Z}^d$. That is not the issue here.

My question is: what are the conditions under which that graph contains a Hamiltonian ray? In other words, under what conditions does a path starting at some vertex of the graph and visiting each vertex of $G_n$ exactly once (by jumping from one vertex to an adjacent vertex) exists?

Because of invariance of $G$ by translation by any basis unit vector, we can consider, without loss of generality, that such a ray starts at the origin.

It's easy to see that:

  • in the $n=1$ case, no such ray exists: whichever direction you set off on the number line, you can not doubleback to collect the integers located on the other side from the origin;
  • in the $n=2$ case, there is an infinite number of such rays: an easy example is some "square spiral" starting from the origin.

However, the answer for $n\geq3$ eludes me.

As an attempt to solve the $n=3$ case, I set out to answer a related question: whether the subgraph (let's call it $G_3'$) of $G_3$ whose coordinates are in $\{-1,0,1\}^3$ contains a Hamiltonian ray starting at the origin. Not knowing any better, I settled the issue by brute force in Matlab (see the code below, in which you can change the starting point).

enter image description here

Result: $G_3'$ does not contain a Hamiltonian ray starting at the origin.

My intuition leads me to conjecture that such a path exists in $G_n$ if and only if $n$ is even.

What do YOU think? Is a result known?


Matlab script:

tic
%clc

a=0.7;

% ---------------- vertex generation ------------------
N=3; % number of nodes along one edge

% generation of the coordinate vectors x, y, z
for k=1:3

    temp=[];
    for m=0:N-1
        temp=[temp m*ones(1,N^(k-1))];
    end

    temp2=[];
    for n=1:N^(3-k)
        temp2=[temp2 temp];
    end

    switch k
        case 1
            x=temp2;
        case 2
            y=temp2;
        case 3
            z=temp2;
    end

end



% ------------------ plotting and labelling the vertices -----------
fig = figure;
set(fig,'color',[1 1 1]);
ax = axes;
plot3(x,y,z,'o');
axis off

for k=1:N^3
    text(x(k),y(k),z(k)+0.1,num2str([N^0 N^1 N^2] * [x(k) y(k) z(k)]'+1));
end




% ----------------- generating the edges and the adjacency matrix ------------------

edge_h = zeros(53,1);
edges = zeros(53,1);

% adjacency matrix
A=zeros(N^3,N^3);

n=0;
for i=1:N^3

    vi = [N^0 N^1 N^2] * [x(i) y(i) z(i)]';

    for j=1:N^3

        vj = [N^0 N^1 N^2] * [x(j) y(j) z(j)]';
        weight = sum(([x(j) y(j) z(j)]-[x(i) y(i) z(i)]).^2);

        if (weight == 1) && isempty(find(edges(:,1) == vj + sqrt(-1)*vi)) % (vi,vj) is an edge

            % update adjacency matrix
            A(i,j)=1;
            A(j,i)=1;

            edge_h(n+1)=line([x(i) x(j)],[y(i) y(j)],[z(i) z(j)],'Color',a*[1 1 1],...
                                                                 'Linestyle',':',...
                                                                 'LineWidth', 2);
            vi = [N^0 N^1 N^2] * [x(i) y(i) z(i)]';
            vj = [N^0 N^1 N^2] * [x(j) y(j) z(j)]';

            edges(n+1,1) = vi+sqrt(-1)*vj;                                             
            n = n + 1;
            %pause(0.1)
        end
    end
end

toc

% ------- look for a Hamiltonian path starting by the given path -------

%path_init = [14 5 2]; % starting point
path_init = 10;%[2 1]; %[2 11]
path = path_init;
flag=0;
chemin=line(x(path),y(path),z(path),'Color',a*[1 1 1],'Linestyle',':','LineWidth', 2);

while numel(path)<N^3
    [ path , flag ]=recursive_path_finding( path ,flag , A );
    delete(chemin)
    chemin=line(x(path),y(path),z(path),'Color',[1 0 0],'Linestyle','-','LineWidth', 2);
    drawnow
    %pause(0.1)
    if numel(path) == numel(path_init)
        disp('No Hamiltonian path for which the initial path considered is a subgraph.');
        break
    end
end
set(fig,'Name',['Path length: ' num2str(path)]);

recursive_path_finding.m function:

function [ path1 , flag1 ]=recursive_path_finding( path0 , flag0 , A )

% NOTE: neighb(i) informs on the order of path0(i+1) as a neighbour of path0(i)

switch flag0
    case 0 % path0(end) has just been added to path0. Find a neighbour of path0(end) that hasn't already been explored.

        u = find(A(path0(end),:)==1);  % Find all the neighbours of path0(end).

            for k=1:length(u)
                % Check that u(k) has not already been explored.
                temp = find(path0==u(k));
                if isempty( temp )  % Not yet explored: add it to the path and break the loop.
                    path1 = [path0 u(k)];
                    flag1 = 0;
                    break % A new candidate for the next step has been found, not need to carry on the loop interations.
                end
            end

            if ~exist('path1')   % All the neighbours of path(end) have been explored, so path0(end) is not a valid candidate. Backtrack.
                    path1 = path0;
                    flag1 = path0(end);
            end


    otherwise % path0(end) is not a valid candidate.

        u = find(A(path0(end-1),:)==1); % Find all the neighbours of path0(end-1).
        v = u(find(u>flag0)); % Discard all the neighbours of path0(end-1) listed before flag0 (inclusive).

        for k = 1 : length(v) % Test all the neighbours of path0(end-1) listed AFTER the (previously tested) flag0.
            % Check that v(k) has not already been explored.
            temp = find(path0==v(k));
            if isempty( temp )  % Not yet explored: add it to the path and break the loop.
                path1 = [path0(1:end-1) v(k)];
                flag1 = 0;
                break % A new candidate has been found in place of path0(end), not need to carry on the loop interations.
            end
        end

        if ~exist('path1')   % All the neighbours of path(end-1) have been explored, so path0(end-1) is not a valid candidate. Backtrack.
                path1 = path0(1:end-1);
                flag1 = path0(end-1);
        end


end
share|improve this question
    
This may be just a terminology issue, but the way the terms "path" and "Hamiltonian path" are usually used, your analysis of the $n=1$ case is incorrect because the assumption that the path has to start somewhere is false. For $n=1$, there is a doubly infinite Hamiltonian path that doesn't start or end anywhere. If you're not interested in such paths, you should specify that you're looking for a Hamiltonian ray. –  joriki Mar 23 '13 at 23:33
    
Thanks for that. I'm not completely familiar with the graph-theory terminology and I knew I was bound to misuse some terms in my question. –  Jubobs Mar 23 '13 at 23:34
    
In $G'_3$ with your labelling: start with $1,2,3,6,5,4,7,8,9$, then continue the next level $18,17,16,13,14,15,12,11,10$, then finish top with $19,20,21,24,23,22,25,26,27.$ I think this visits each node once, and the two vertical junctures from 9 to 18 and from 10 to 19 are OK as unit moves. –  coffeemath Mar 24 '13 at 0:09
1  
Ha! Yes, $G_3'$ does contain a Hamiltonian ray starting at the vertex I labelled by "1". I should have specified that the starting point should be the origin. Sorry -_- I had forgotten that graph $G_3'$ does contain some Hamiltonian rays, if the starting point is chosen wisely. –  Jubobs Mar 24 '13 at 0:16
2  
@Jubobs: Color the nodes alternately black and white. Say the origin is white, so that the corners are black. There are $13$ white nodes and $14$ black nodes, and any path must alternate colors. You’re starting at a white node, so any path is of the form WBWBWB... and can therefore contain at most $26$ nodes. To hit every node, you must start at a black node. –  Brian M. Scott Mar 24 '13 at 18:40

1 Answer 1

up vote 3 down vote accepted
+100

It is indeed possible to make such a path. For that you use the following theorem (you can prove it by induction).

In any $d_1\times d_2\times ... \times d_n$-grid ($n\geq 3$) where every $d_i$ is even (let's call such a graph an even block), there is a hamiltonian path between any corners of different color, in the $2$-coloring of the grid (like a chessboard). (Actually it is true for any pair of vertices of different colors and with only one single even dimension).

In particular, it is possible, starting from any corner, to finish at a corner in any face (but not at any corner).

There are $2n$ directions : $e_1$, $-e_1$,..., $e_n$,$-e_n$.

Now, you construct your path in this way :

  • start with a hamiltonian path of the $2\times 2 \times.... 2$-grid. This path necessarily ends in a corner.
  • assume that you have a hamiltonian path of the $d_1\times d_2.... \times d_n$-grid ending in a corner.

  • extend your path by adding a block of even width in one of the n free directions of your corner and finishing in a corner. Let's call the chosen direction $e_k$. Let $e_\ell\neq -e_k$ be a direction. By choosing the right face for the extension, you will be able to extend in direction $e_\ell$ for the next step.

  • repeating the extension order : $e_1$, $e_2$,...,$e_n$, $-e_1$,....,$-e_n$, you will obtain your path.

share|improve this answer
    
Thanks, Aline! Your proof seems sound to me. Could you just elaborate a bit on your claim that "it is possible, starting from any corner, to finish at a corner in any face (but not at any corner)"? It's not obvious to me. –  Jubobs Mar 25 '13 at 12:50
    
You can prove by induction that you can join any pair of corners with opposite colors (in a block will all dimension even). It is true for the hypercube ($2\times 2...\times 2$). Assume the claim is not true and take a minimal counter example. At least one dimension is $\geq 4$, you remove a width of $2$ on this dimension. By minimality, there is always a path between any pair of corners of opposite colors in the remaining part. In the other part, you can make an hamiltonian cycle. Then you just have to put the paths together and be careful with the position of the corners... –  Aline Parreau Mar 25 '13 at 14:22
    
If you understand french, I wrote a proof of a stronger statement some years ago : enslyon.free.fr/rapports/info/Aline_Parreau_1.pdf (page 7 thm 2) –  Aline Parreau Mar 25 '13 at 14:23
    
I do understand French. Thanks for the link. I'm also relieved to learn that you spend a relatively long time thinking about the topic before finding a solution to this particular problem :) –  Jubobs Mar 25 '13 at 14:25

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.