Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [hamiltonian-path]

A path in a graph that visits each vertex exactly once.

0
votes
1answer
164 views

When does a complete bipartite graph contains a Hamiltonian cicle?

¿Is there a way to know when does a complete bipartite graph $K_(n,m) $ contains a Hamiltonian cicle? I was trying to figure a secure way to prove a Hamiltonian Cycle on those kind of Graphs, using ...
0
votes
1answer
234 views

show that if $G$ is a $2$-connected graph containing a vertex that is adjacent to at least three vertices of degree $2$, then $G$ is not Hamiltonian.

I would like to see how to show this statement is true. Can someone demonstrate why this is not Hamiltonian?
0
votes
1answer
104 views

A graph that is tough but not Hamiltonian.

A graph G is tough if the number of $c(G-s) \le |S|$ for all $S \in V(G)$. And I read that every tough graph is Hamiltonian, but the other way is not true. I was wondering if there is an example of ...
2
votes
2answers
467 views

Expected number of hamiltonian paths in a tournament

The following theorem is from Alon&Spencer's The probabilistic method, in the beginning of chapter 2: Theorem 2.1.1: There is a tournament $T$ with $n$ vertices and at least $\frac{n!}{2^{n-1}}$ ...
1
vote
1answer
129 views

Question on degree sequence of eulerian, hamiltonian bipartite graph

I've gathered that it requires a cycle with degree 10 to be considered hamiltonian and it is bipartite so there can not be any odd cycle, lastly it is eulerian hence every edge set can be partitioned ...
0
votes
0answers
119 views

NP-completeness certificate of a Hamiltonian path

A Hamiltonian path is a path in a directed , edge positive valued finite graph which visits every vertex exactly once and returns to the original vertex. This should be a NP-complete problem, but I do ...
3
votes
1answer
140 views

Rules for Reductions in NP-Completeness Proofs (many-one vs one-many)

My understanding is that when reducing one problem known to be NPC (e.g., HAM-Cycle) to another problem known to be NP (e.g., Ham-Path) we have shown that the second problem (the target of the ...
0
votes
1answer
88 views

Deleting a vertex from a Hamiltonian graph

Let $G=(V,E)$ be a connected simple graph with vertex $v\in V$. Define $G'=(V',E')$ with $V'=V\smallsetminus{v}$ and $E'=\{e\in E|v\not\in e\}$. Prove that if $G$ is Hamiltonian then there exists a ...
-2
votes
1answer
63 views

Traveling salesman problem

Consider the traveling salesman problem with five cities. The cities are called $\text{A,}$ $\text{B,}$ $\text{C,}$ $\text{D,}$ and $\text{E}$. Here is the mileage chart for the cities. $$\begin{...
0
votes
1answer
266 views

Proof with induction on $n$ so that the complete graph $K_n$ has $(n-1)!$ hamilton cycle for all $n \geq 3$.

I came up with this solution, but I'm not sure if it's right. Could you check if there is something missing? In the Hamilton cycle, every visit to a node is only exactly one time. Base case: $K_n$ ...
1
vote
1answer
93 views

How to prove that a non-complete bipartite graph has a Hamiltonian cycle

I am trying to prove $D$. I already proved $B$. I think that for $n \geq 3$, $G$ has a Hamiltonian cycle. I tried using a few theorems that use the cardinality of the independent sets and connectivity ...
1
vote
2answers
543 views

P/NP reduction (hamiltonian cycle to TSP)

I have a P/NP question. I have read that were any NP problem be found to have a polynomial time algorithm, then we can reduce any other NP problem to a form where we can use our first algorithm to ...
1
vote
2answers
46 views

Hamiltonian circuits / graphing

Can someone tell me if I'm correctly doing these graphs for Hamiltonian circuits? I know that you start at the root node and show the path "back" in a tree. But what if it crosses and such. I'm just ...
1
vote
1answer
172 views

Graph Theory - Hamiltonian Cycle, Eulerian Trail and Eulerian circuit

Is it possible to draw a graph that has an Eulerian trail as well as a Hamiltonian Cycle but does not have an Eulerian circuit?
0
votes
1answer
74 views

Finding Hamiltonian cycle for $N\times M$ grid where $N$ is even

This is the solution provided for the problem. However when I follow it, I am not getting the correct path. I assumed $N=4$ and $M=3$ and started with $k=0$ and got this path: $$(0, 1) \to (0, 2) \to ...
1
vote
0answers
229 views

Show the NP completeness of Hamiltonian Path with the knowledge of an directed Euler graph

I'm interested in the idea behind a NP completeness problem. It should be checked that Hamiltonian Path is in NP. As an indication, the problem Euler graph is in NP. Definition of Euler graph: An ...
2
votes
1answer
144 views

Does this graph have a Hamiltonian cycle?

My gut feeling is to say no because this is a bipartite graph with an unequal partition of vertices $(3,1,3)$. However, I am not sure if the exact logic applies because of the line going through above ...
0
votes
1answer
116 views

Graph Theory: Hamilton Cycle Definition Clarification

- Background Information: I am studying graph theory in discrete mathematics. I have come across Hamilton cycle definition, but there are some things I am not sure about, I need clarification, thanks....
2
votes
1answer
435 views

Using Ore's theorem to show the graph contains a Hamilton cycle

Define the complement $\bar{G}$ of a graph as follows: $V(\bar{G})=V(G)$ and for all $x,y \in E(\bar{G})$ if and only if $x,y \notin E(G)$. Suppose that $G$ is a graph that is not a forest and does ...
1
vote
3answers
585 views

Prove that if a graph $G$ has a Hamilton path then for every $S \subseteq V(G)$ the number of components of $G - S$ is at most $|S| + 1$

Prove that if a graph $G$ has a Hamilton path then for every $S \subseteq V(G)$ the number of components of $G - S$ is at most $|S| + 1$. I have tested this numerically with some examples and can ...
0
votes
1answer
55 views

Is it true that every graph with n vertices in which δ(G)>=(n/2)-1 has Hamiltionian path?

Is it true that every graph with $n$ vertices in which $δ(G)\geq\frac{n}{2}-1$ has Hamiltionian path? Prove it.
1
vote
1answer
28 views

Most efficient way to detect if a series of n edges creates a cycle of size n.

I am working on an algorithm but there is so much about math that I don't know and I could speed up my algorithm a ton if there was a trick here. I have a weighted, undirected graph. From this graph ...
0
votes
1answer
226 views

constraints to the hamiltonian path: can one tell if a path is hamiltonian by looking at it?

A few days ago, the channel Numberphile released this video on the square-sum problem. The show later released this follow-up video on how they proved that every number from 25 to 91 can have ...
0
votes
2answers
45 views

Solving P vs. NP by writing a deductive solution-excluding algorithm

I'm thinking about the P vs. NP problem. Take the Hamiltonian graph problem, for example. If I make a Hamiltonian graph-finding algorithm which goes through every edge of a given graph and deductively ...
2
votes
1answer
90 views

Where are the Optimal Tours of TSPLIB 95 Instances?

I am looking for the optimal tours of the TSPLIB 95 instances as downloadable files. I have checked several places, but all lists I could find contain gaps, despite the fact, that all instances have ...
1
vote
0answers
75 views

Minimum board size for knights tour to be possible

What is the minimum board size for a knight's tour: open or closed, to be possible. Edit: I want to write a program that can solve knight's tour for any board size. I want to implement a lower limit ...
0
votes
1answer
44 views

$K_n$ for odd $n$ $ϵ$ $Z_+$ is a disjoint union (of edges) of collections of Hamiltonian cycles

Show that (the edges) in the complete graph $K_n$ for odd $n$ $ϵ$ $Z_+$ is a disjoint union (of edges) of collections of Hamiltonian cycles. Further, show that (the edges) in the complete graph $K_n$ ...
0
votes
1answer
32 views

Hamiltonian cycle equivalence?

If we have an undirected graph, is the existence of a Hamiltonian cycle in the graph equivalent to finding a subset of edges S in the graph such that every vertice appears in exactly two different ...
2
votes
1answer
249 views

Graph theory - How many Hamiltonian Cycle in a non-complete graph

(In this representation of $\phi$, the first row specifies the edges and the second row specifies the two vertices of that edge) I tried and actually draw some example graphs for $\phi$ and I can ...
-1
votes
1answer
1k views

How to prove that a graph has a Hamiltonian cycle? [closed]

I need to this for my homework and I've been looking for over an hour but don't really know where to start. A tip would be appreciated! Assume we have the following graph: How can you prove that it ...
2
votes
1answer
71 views

Determine if an intersection graph is Hamiltonian

I have a problem about graph theory and I need some hints to solve it. Consider a graph $G$ with the vertex set $V(G)$ equal to the set of all two element subsets of the set $A=\{1, 2, 3, 4, 5\}$. ...
1
vote
1answer
503 views

Is it correct to prove the Dirac's theorem in the way I tried?

Here is a proof from Wiki: and another proof I found here: http://faculty.wwu.edu/sarkara/dirac.pdf I read them and tried it on my own, I haven't assumed that P is the longest path, and then I ...
1
vote
1answer
183 views

Proving a relationship between minimum Perfect Matching and minimum Hamiltonian Cycle

The question states: Let n > 0 be an even integer and let G = (V,E) be the complete graph on n vertices. Each edge e ∈ E has a non-negative weight w(e) >= 0 such that the weights satisfy the triangle ...
0
votes
1answer
78 views

What values of n lead to a modified cycle having a bipartite?

The graph $D_n$ is created by adding a vertex to $C_n$ and connecting the vertex to each of the vertices in $C_n$ with an edge. What values of n will lead to $D_n$ having a bipartite? So far for my ...
1
vote
1answer
93 views

On 4-ordered Hamiltonian Graphs

I am trying to solve the following problem: Let $G$ be a graph of order $n\geq 4$ such that deg $v \geq n/2$ for every vertex $v$ of $G$. Show that $G$ need not be 4-ordered Hamiltonian. Here, a ...
1
vote
1answer
329 views

Connected graph with colored edges

We have connected undirected graph with colored edges in two way (green or blue). And also each vertex have the same number of green and blue edges. How to prove that there are alternate colored (...
1
vote
2answers
3k views

Is every Eulerian graph also Hamiltonian?

I know that if a graph is Eulerian then there exists an Eulerian cycle that contains all edges of the graph. I also know that if a graph is Hamiltonian then there exists a Hamiltonian cycle that ...
0
votes
1answer
1k views

Hamiltonian Path to Hamiltonian Cycle reduction

I have to show that HP polynomially transforms HC by following steps: (1) Construct a polynomial transformation f from HP to HC. (2) Show for all graphs G that G ∈ YHP ⇒ f(G) ∈ YHC. (3) Show for all ...
10
votes
3answers
3k views

Is this graph Hamiltonian?

I know that a Hamiltonian graph has a path that visits each vertex once. But I am not sure how to figure out if this one does. Obviously I can try and trace various different paths to see if one works ...
1
vote
0answers
72 views

Directed Cayley Graph With No Hamilton Cycles

In the excellent Algebraic Graph Theory book by Godsil and Royle, they show that you can construct an infinite family of directed Cayley Graph (so vertex transitive) that are not Hamiltonian. The ...
1
vote
1answer
376 views

Computational complexity of Eulerian and Hamiltonian paths and cycles in (un)directed graphs

Hey Guys I am aware that we can find if there exists a hamilton path in a directed graph in O(V+E) time using topological sorting. I was wondering if hamilton cycles, euler paths and euler cycles can ...
0
votes
1answer
30 views

Is hamiltonian graph a graph where a Cycle covers all the vertexes?

I learnt that , a Cycle should have unique vertices and unique edges where start vertex = end vertex. So if the there is a Cycle that can cover every vertex, is that sufficient enough to make the ...
0
votes
0answers
256 views

Prove that if $T$ is tournament that is not transitive then $T$ has at least three hamiltonian paths.

Prove that if $T$ is tournament that is not transitive then $T$ has at least three hamiltonian paths. Proof: I am not sure how to start this proof. If it is not transitive then I think the tournament ...
1
vote
2answers
317 views

Hamiltonian Path on Cubic Graphs, and whether closed triangle meshes are triangle strips

The problem is this: Can every closed triangle mesh (an approximation of a 3d object using triangles, eg. a tetrahedron) be 'peeled like an orange', that is, can we find a sequence of triangles ...
0
votes
1answer
450 views

Prove by induction any $k$-hypercube (for$ k>1$) has a Hamilton Circuit

I have a basic understanding of graph theory and I know what a Hamiltonian circuit is, but I really need help with this proof, it makes little since to me. Thanks so much in advance for the help!! ...
0
votes
2answers
218 views

What is a max non hamiltonian graph?

Assume we're taking about simple graphs here. What is the exact definition of a non-hamiltonian graph ? Is it true if I say that: Adding one single edge to the max non-hamiltonian graph, will make ...
3
votes
1answer
56 views

Listing the elements of a covering for a closed disk by open disks

This problem is somewhat related to some homework I had recently. However, as stated, I don't know if a solution yet exists. I asked some friends and some of my professors, but none of them know how ...
1
vote
0answers
79 views

Find a Hamiltonian circuit in a given Hamiltonian graph.

I am wonder if there is a polynomial time algorithm(may be probabilistic) that can compute a Hamiltonian circuit in a graph which is known as Hamiltonian graph without other assumption. If there is,...
1
vote
1answer
32 views

For a graph G with greater than or equal to 3 vertices, prove that G is Hamitonian if there is a Hamiltonian path between every pair of vertices

As the title of the question states, a proof for this proposition will be highly appreciated. The proof can either be inductive or, explained in plain English.
0
votes
0answers
70 views

edge of a cubic graph and number of Hamilton cycles

I'd like to prove this statement. I want to start with: at any vertex v, edges connected with v can be colored in 3 colors. so there are at least 3 hamilton cycles. Then I don't know how to continue ...