Questions tagged [hamiltonian-path]

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

396 questions
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 ...
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?
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 ...
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}}$ ...
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 ...
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 ...
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 ...
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 ...
63 views

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 ...
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 ...
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....
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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\}$. ...
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 ...
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 ...
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 ...
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 ...
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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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!! ...
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 ...
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 ...
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,...