# Questions tagged [hamiltonian-path]

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

638 questions
Filter by
Sorted by
Tagged with
49 views

### Hamiltonian path in graph where every $u,\ v$ has max $3$ length path.

Given a tree $T = (V, E)$ and a graph $G = (V, F)$ such that $F = \{(u,v)\mid\text{ if the distance from$u$to$v$in$T$is at most$3$}\}$, prove that $G$ contains a Hamiltonian path. So, my ...
11 views

### Let $G$ be a k-regular graph on at least $3$ vertices. Then $G$ or $G$ has a Hamiltonian path.

I want to show that for a $k$-regular graph $G$, i.e., every vertex has degree $k$, on at least $3$ vertices, $G$ or $\overline{G}$ has a Hamiltonian path. There have been some related posts, e.g., ...
41 views

### What are necessary and sufficient conditions to have a negative cycle in a directed graph with some negative edges? [closed]

Trying to test Johnson’s algorithm with over 100 vertices but it doesn’t work if there is a negative cycle. So I’m trying to write code to construct graphs with some negative weights (about 10% of the ...
33 views

### Hamiltonian graph on a $8\times 8$ chessboard with upper left corner and bottom right corner square removed

Suppose we are given the setup in the title. Two squares are adjacent if and only if they share a common edge. I want to find out whether the obtained graph considering squares as nodes would be ...
• 79
71 views

### Let $m\geq 2n+1$. Prove that $R(C_m,K_{1,n})=m$.

Let $m\geq 2n+1$. Prove that $R(C_m,K_{1,n})=m$. To prove that $R(C_m,K_{1,n}) = m$, where $m \geq 2n + 1$, let me first define the terms: $C_m$ represents a cycle graph with $m$ vertices. $K_{1,n}$ ...
• 211
1 vote
41 views

• 53
58 views

### How to prove if there is no Hamilton Cycle?

This picture should be a good example of no Hamilton Cycles: I have checked multiple times and made sure there was no cycle, but I don't know how to prove that there is no cycle. Proving that there ...
30 views

### Is there a connected graph where every vertex has degree k >1 with no Hamiltonian cycle?

I am trying to construct a simple connected graph where every single node has the same degree $k>1$ but without containing any Hamiltonian cycle. Take this simple example as shown in the images ...
• 103
149 views

### Hamiltonian Circuit Counting and Classification Problem

Consider an undirected complete graph $G_n$ with $n$ vertices, where if the numerical labels of each vertex are consecutive, then the edge between them is $1$, and the edge between the numerical ...
• 601
1 vote
69 views

### Hamiltonian in optimal control

Hamiltonian $~H~$ (control theory) is: \begin{align*} {H}(\vec{x}~,\vec{\lambda},~u,t)=\vec{\lambda}^T\vec f(\vec{x}~,u,t)+L(\vec{x}, u,t) \end{align*} For Zermelo's navigation problem https://en....
• 413
34 views

### Is There any Untraceable Generalized Petersen Graph?

The Petersen graph is one of the example of graph which is not Hamiltonian. Can we find an example among the generalized Petersen graph which doesn't have Hamiltonian path (untraceable)?
• 1,949
1 vote
42 views

### Does a strongly connected component necessarily have a Hamiltonian path or cycle?

In a general directed graph, does a strongly connected component necessarily have a Hamiltonian path or cycle? I don't think so, and I've tried to come up with compact counter example, but have yet to ...
• 249
21 views

### What is the smallest untraceable graph satisfying some necessary conditions for traceability?

I am trying to find a graph (ideally the smallest) that demonstrates why the following 3 necessary conditions are not sufficient for a graph to be traceable. In other words, what is the smallest ...
350 views

### Arranging Drilled Unit Cubes into a Rectangular Prism Without Breaking the Thread

Given positive integers p, q, and r, we have $p \cdot q \cdot r$ unit cubes. Each cube has a hole drilled along one of its space diagonals. These cubes are then strung onto a very thin thread of ...
42 views

32 views

### Hamilton paths skipping some vertex relations

I have been developing a Python code to compute all the Hamilton cycles for a system but excluding those that have a maximum distance d between vertices. Hence, for d=1 i would only have a single ...
1 vote
53 views

### How Many Self-Avoiding Walks are there in a 3x8 Grid of Nodes where all nodes must be traversed.

You must start from the bottom left corner of the grid and end at the top right corner. From my research, most solutions focus on all possible self-avoiding walks but not the specific case where every ...
1 vote
28 views

### Is there a Hamiltonian path though a Menger sponge of level-n?

This is a thought that I was having while building a model of a level 4 Menger sponge in minecraft. Imagine a Menger sponge to be built of cubic voxels the same size as the smallest void. You can ...
• 4,613
1 vote
I would like to know under what conditions there exisits a (possibly open) knight's tour on a generic (hyper)cubic lattice $\{\{0,1,\ldots,n-1\} \times \{0,1,\ldots,n-1\} \times \cdots \times \{0,1,\... • 1,112 1 vote 1 answer 91 views ### Graph is hamiltonian iff$n$-closure is$K_n$I have seen this statement and was wondering how one might show that if a graph (with$|V(G)| = n$vertices) is hamiltonian, that then it's$n$-closure is the$K_n$(note that this is refering to ... • 654 1 vote 1 answer 49 views ### Prove that the language HAMTWOCYCLES = {G | there exist two cycles in G such that any vertex belongs to exactly one of them} is NP-complete I have attempted to prove this theorem, but I am not confident in my solution. Can someone please review my proof and let me know if there are any errors, or provide a correct proof if mine is ... • 25 0 votes 1 answer 60 views ### Delaunay graph and hamiltonian paths Does the Delaunay graph (dual of Voronoi) always contain a hamiltonian path (traceable)? I know the answer is negative for hamiltonian cycles since there are several examples such as the one gave by ... 0 votes 0 answers 20 views ### Reducing Hamiltonian path to TREFOIL HAMTREFOIL = {(G,s,t,u,v) | there exist paths s->t, s->u, s->v such that every vertex(except s) belongs to one of the paths} I want to prove that HAMTREFIOL is NP-complete by reducing ... 2 votes 1 answer 119 views ### Inapproximability research for metric TSP I'm doing research into improving the inapproximability ratio for the metric/graphic Traveling Salesman Problem. As I've been reading through the literature in this field, I've noticed that most of ... 1 vote 0 answers 40 views ### Is this statement true? Proving a theorem is equivalent to a problem in proving a Hamiltonian cycle of a graph Blum proved that any mathematical theorem can be converted into a graph such that the proof of that theorem is equivalent to proving a Hamiltonian cycle in the graph from Applied Cryptography by ... 0 votes 0 answers 39 views ### Asymptotic approximation algorithms for TSP I have been reading a lot about TSP approximation algorithms recently, and I noticed that most of the algorithms tend to fall under two general categories: some that have a guaranteed approximation ... 1 vote 1 answer 123 views ### Polynomial time approximation methods for TSP I am aware that the Christofides algorithm is the best known polynomial-time algorithm for approximating solutions to the traveling salesman problem, but it only works for the metric TSP. Does anyone ... 1 vote 1 answer 106 views ### decompose complete directed graph with n vertices into n edge-disjoint cycles with length n-1 I want to know how to decompose a complete directed graph with$n$nodes into$n$edge-disjoint cycles with length$n-1$. I found this result was proved in this paper (Theorem 3). However, the proof ... • 21 6 votes 1 answer 195 views ### Maximal cycle on n items Suppose$n$items are in a circle. What is the maximal cycle length that goes through all of the items. Length between 2 points is measured according to the shorter arc on the circle. I solved the ... 0 votes 1 answer 96 views ### Finding path lengths by the power of adjacency matrix of an undirected graph The same question was asked almost 7 years ago. It turned out to be a matter of terminology in different textbooks between the terms "path" and "walk". While the answers addressed ... • 103 1 vote 0 answers 67 views ### Maximum number of edges in a connected graph without Hamiltonian path What is the maximum number of edges in a connected graph without Hamiltonian path? I've searched the Internet on a while, and read the question Maximum number of edges in a non-Hamiltonian graph here,... 1 vote 1 answer 78 views ### Hamiltonian paths in same degree graph Suppose we have a connected graph, and all vertices of this graph have the same even degree. Is it always true that this graph has a Hamiltonian path? Furthermore, is it true if the degree$2k$, this ... • 13 1 vote 1 answer 34 views ### A Hamiltonian cycles (plural) problem? I'll be brief. I have a set of n vertices in a complete weighted graph, some of these vertices can be thought of as power plants and the rest as cities, and I need to find the shortest way to connect ... 3 votes 1 answer 99 views ### Proof that$n$points on a plane cannot be connected with straight lines under a certain angle treshold I have$n$points on a two-dimensional coordinate plane. My goal is finding a path that visits every point once, with straight lines interconnection two points. Additionally, the angle of a line ... • 35 1 vote 1 answer 27 views ###$\nexists$A hamiltonian closed trail$\Rightarrow \exists x_0 \in V(G)$such that$\textrm{#\{connected components of }G-\{x_0\}\} \geq 3 $I'm trying to characterize the hamiltonian paths with the following property: Given$G$a connected graph and$K(G)$the number of connected components of$G$then$\exists x_0 \in V(G) \textrm{ s.t. }...
For $p_k(n)$, the partitions of $n$ with exactly $k$ parts, it's possible to order them such that each adjacent pair of partitions differ only by one, i.e. one can be transposed to the other by ...