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.

Suppose there is a graph $G$. The graph will either have hamiltonian path or not.

I want to make an expansion $H$ of $G$ by adding nodes (vertexes) and corresponding edges to $G$ so that if a hamiltonian path of $G$ exists, the number of hamiltonian paths of $H$ is odd. If hamiltonian path of $G$ does not exist, $H$ should not have any hamiltonian path.

What would be a way to do this? Is this possible? How many nodes are required to do this?

Edit: when adding new edges, these edges must have an endpoint that is a new vertex(node).

Edit: Obviously, I am not asking for a way that requried trying every case (and checking whether the number of hampath is even or odd) - I want a way that does not require checking of the number of hampaths in the original graph and does not requrie trying every case as aforementioned.

Edit: If every undirected graph has even number of hampaths (except when it has no hampath), directed grpahs(digraphs) are fine. Anyway, even if the graph $G$ is undirected, the expansion can be directed. So, what about digraphs? Is this true?

share|improve this question
    
Is $G$ a digraph? –  Fixee Nov 4 '12 at 2:35
    
Digraph is fine, but I would prefer undirected graph. –  Dotto Nov 4 '12 at 2:39
    
I think if $G$ is undirected, and if we define a hamiltonian path as a permutation of the vertices, then there are always an even number of such permutations if the number of vertices > 1. –  Fixee Nov 4 '12 at 2:41

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.