Skip to main content

Questions tagged [hamiltonian-path]

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

Filter by
Sorted by
Tagged with
2 votes
0 answers
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 ...
Yarden Tziar's user avatar
0 votes
1 answer
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., ...
claudelle95's user avatar
-1 votes
1 answer
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 ...
Bark Jr. Jr.'s user avatar
3 votes
1 answer
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 ...
Sj2704's user avatar
  • 79
-3 votes
1 answer
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}$ ...
good12's user avatar
  • 211
1 vote
1 answer
41 views

$G$ hamiltonian iff $H^2$ is hamiltonian

Let $G$ be a graph on the vertex set $V = \{v_0, \ldots, v_{n-1}\}$. Construct $H$ as the graph on vertex set $\{v_0, \ldots, v_{n-1}, u_0, \ldots, u_{n-1}, w_0, \ldots, w_{n-1}\}$ with $$ E(H) = E(G) ...
mNugget's user avatar
  • 511
1 vote
0 answers
51 views

Complexity of a Sorting Problem

i investigate the following problem. Given a set of tuples $(a_i, b_i), i=1\ldots,n$ with $a_i,b_i \in \mathbb{N}$, i want to order them into a sequence such that the sum of differences of endelements ...
Dom's user avatar
  • 19
0 votes
0 answers
25 views

dynamic optimization with a differential constraint

In Benevolent Social Planner's Problem, there's a dynamic optimization problem with fixed horizon $T$, that is (simplified): $$ \max_{c_t,k_{t+1}} \sum_0^{T} \beta^t u(c_t) \quad \text{s.t.} \quad c_t+...
Kozack51's user avatar
2 votes
1 answer
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 ...
MotherHorse's user avatar
0 votes
0 answers
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 ...
JCr's user avatar
  • 103
2 votes
2 answers
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 ...
nevermind_15's user avatar
1 vote
1 answer
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....
Eli's user avatar
  • 413
3 votes
1 answer
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)?
user966's user avatar
  • 1,949
1 vote
1 answer
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 ...
sadcat_1's user avatar
  • 249
0 votes
1 answer
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 ...
Vincent Cattoni's user avatar
7 votes
2 answers
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 ...
Wismar Günther's user avatar
0 votes
1 answer
42 views

A question about tournaments containing Hamilton paths

I need to show that there exists a tournament of n vertices $n\ge3$ that has more than $\frac{n!}{2^{n-1}}$ Hamiltonian paths Can I try to show that with induction? I'm not so sure how to start with $...
Whatever-_-'s user avatar
0 votes
0 answers
107 views

A polynomial time algorithm for Finding a Hamiltonian path in an undirected graph - searching for a counter example

I have the below algorithm that appears to find a Hamiltonian path in undirected graphs (if one exists). I've tested with every graph I could find or come up with and it appears to work. I've included ...
Ben's user avatar
  • 1
1 vote
1 answer
91 views

Does the graph have a Hamiltonian circuit or a Hamiltonian path?

Certain necessary conditions for a Hamiltonian circuit such as the graph being 2-connected, having zero pendants are met. Dirac's and Ore's theorem provide sufficient conditions, which are not ...
0x13's user avatar
  • 415
2 votes
1 answer
75 views

Is there a Hamiltonian cycle of $m$ x $n$ rectangular lattice points (these are the vertices) in $\mathbb{R}^2$ such that no two edges are parallel?

Let $m,n\geq 2$ and consider the rectangular lattice of $mn$ vertices in $\mathbb{R}^2,\ (i,j);\ i\in \{1,2,\ldots,m\},\ j\in \{1,2,\ldots,n\}.\ $ Call these vertices $X_1, X_2, \ldots, X_{mn}.$ Is ...
Adam Rubinson's user avatar
5 votes
1 answer
332 views

Hamiltonian path for a $N\times N$ grid. Focus on all the possible ending points

On a $3\times3$ grid, draw a path that starts in the center of a square in the corner of the grid, and repeatedly moves from the center of one square to the center of an adjacent square, without ...
Johnny Boi's user avatar
5 votes
1 answer
83 views

What's the probability of stumbling onto a Hamiltonian path?

Suppose we have a graph $G$, which for sake of convenience we'll require to be vertex-transitive. Then there's a natural notion of a random path: start at any vertex $v_1$ (and this is where the ...
Steven Stadnicki's user avatar
0 votes
0 answers
66 views

Corollary of Ore's Theorem

"Theorem (Ore; 1960) Let $G$ be a simple graph with $n$ vertices. If $$\deg v + \deg w ≥ n$$ for every pair of non-adjacent vertices $v$, $w$, then $G$ is Hamiltonian." From this theorem, ...
J P's user avatar
  • 665
3 votes
0 answers
41 views

Graph class where Hamiltonian Path is polynomial and Path cover is NP-complete?

Path cover asks, what is the minimal number k such that G can be covered by k vertex-disjoint paths. (Path cover of G has size 1 if and only if G has a Hamiltonian path). Is there a graph class (...
Nikola 's user avatar
1 vote
1 answer
142 views

Why is reduction from Hamiltonian cycle to Hamiltonian path wrong?

Wiki link states that you are able to reduce from HC to HP by vertex cleaving. In the other direction, the Hamiltonian cycle problem for a graph G is equivalent to the Hamiltonian path problem in the ...
Peter HU's user avatar
  • 141
1 vote
0 answers
52 views

Is Petersen's graph an Hamiltonian one? [duplicate]

Petersen's Graph Is there a path of length $10$ in the Petersen's graph? If so, is it true that Petersen's graph would be Hamiltonian? Is the fact that each vertex has degree $3$ fundamental to ...
J P's user avatar
  • 343
2 votes
0 answers
29 views

Three-dimensional analog to a discrete two-dimensional spiral

Starting at some point in an infinite 2D grid, there is a simple and intuitive path to visit every other point exactly once using only unit-length movements in the directions of the basis vectors. It'...
klkj's user avatar
  • 95
1 vote
0 answers
39 views

Does every smooth manifold have a Hamiltonian triangulation?

Call a triangulation of a smooth manifold Hamiltonian if its 1-skeleton has a Hamiltonian cycle. I have several questions about these that I haven't been able to find answers to. First, every smooth ...
JLA's user avatar
  • 6,484
0 votes
0 answers
23 views

Struggling to Derive First-Order Condition in Lucas (2004) on Optimal Control

I am reading Robert Lucas (2004), Life Earnings and Rural-Urban Migration, and I came across a rather peculiar optimal control problem that I'd like to ask about. Thank you! The objective function is $...
zz Matthew's user avatar
0 votes
0 answers
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 ...
Joan Grebol's user avatar
1 vote
1 answer
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 ...
weekly5112's user avatar
1 vote
0 answers
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 ...
Q the Platypus's user avatar
1 vote
0 answers
46 views

Open knight's tours on $n \times n \times \cdots \times n \subseteq \mathbb{Z}^k$ boards ($k \in \mathbb{N}-\{0,1\}$)

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,\...
Marco Ripà's user avatar
  • 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 ...
Raoul Luqué's user avatar
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 ...
Booker's user avatar
  • 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 ...
Manuel Ceballos Gonzalez's user avatar
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 ...
Mostafa Eid's user avatar
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 ...
slithy_tove's user avatar
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 ...
Bad at Mathematics's user avatar
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 ...
slithy_tove's user avatar
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 ...
slithy_tove's user avatar
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 ...
chunma's user avatar
  • 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 ...
agent_cracker103's user avatar
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 ...
Moobie's user avatar
  • 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,...
Alex-Github-Programmer's user avatar
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 ...
Sinocchi's user avatar
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 ...
Giuliano Cavallo's user avatar
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 ...
Luqus's user avatar
  • 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. }...
Mikel Solaguren's user avatar
3 votes
2 answers
172 views

Finding "Hamiltonian paths" in fixed-size integer partitions

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 ...
Tom Quinn's user avatar
  • 225

1
2 3 4 5
13