I have come up with an algorithm, but I am not sure whether it is correct, and I do not know how to prove it.
I think that in general idea is correct and that it will work without modification if gcd(n,k)=1. In other cases you will have to modify it.
For example: 5 vertices, k=2
vertices in ham.cycle 1: 1, 2, 3, 4, 5 and again 1
vertices in ham.cycle 2: 1, 3, 5, 2,4 and again 1
For 6 vertices and k=2
vertices in ham.cycle 1: 1, 2, 3, 4, 5, 6 and again 1
vertices in ham.cycle 2: 1, 3, 5, and what now?
If the smallest nonused vertex is used, in this case vertex 2 (ie.1,3,5,2,4, 6) will result with cycle that are not disjoint (edge 61). It should be 135264.
Zoran Maksimovic
Dear Prof. Zoran Maksimovic,
Thanks for answering my question. But I think, we have some other ways to derive edge-disjoint Hamiltonian cycles in your example.
For 6 vertices and k=2,
the first Hamiltonian cycle can be 1, 2, 3, 4, 6, 5, 1;
and then the second one is 1, 3, 5, 4, 2, 6, 1.
Could you write how do you add edges one by one for n=6. For example in the first cycle there is at the end 6,5,1. However in description of the first cycle there at the end is (n,1) so there should be 5,6,1. And that will give the common edge with the second cycle 2,6,1.
It seams to me that the problem is what to do when the last vertex is exceeded (for example n+1 or n+2 or ...). Could you elaborate that?
Dear Prof. Zoran Maksimovic
Thanks! Sorry I do not understand your idea. We should keep in mind that the way that we construct this graph is NOT the way we pick out the Hamiltonian cycles from this graph.
Thus, to construct the graph with 6 vertices, we do the following things:
In the first round, add edges (1,2), (2,3), ..., (6,1);
In the second round, add edges (1,3), (2,4), (3,5), (4,6), (5,1), (6,2).
Now we have derived the graph with 6 vertices. Obviously, it contains 2 edge-disjoint Hamiltonian cycles:
The first Hamiltonian cycle can be 1, 2, 3, 4, 6, 5, 1;
and then the second one is 1, 3, 5, 4, 2, 6, 1.
Now I understand. You should formulate how do you choose cycles in a general case?
I thought that new edges are added in order to create a new cycle in each round. This way it would be easy to prove that k edge-disjoint cycles are created. The only problem is to select edges to add in a general case.
My idea was that when gcd(n,2)=gcd(n,2)=...=gcd(n,k)=1
for example for n=7, k=3
add edges 12,23,34,45,56,67,71 for the first cycle
add edges 13,35,57,72,24,46,61 for the second cycle
add edges 14,47,73,36,62,25,51 for the third cycle
For the first one vertices are incremented by one modulo 7
For the second ivertices are incremented by two modulo 7
For te third one vertices are incremented by three modulo 7.
They are hamiltonian and they are edge disjoint by the definition.
In a general case you should dig into combinatorics ie. permutations.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs