# Questions tagged [hamiltonian-path]

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

567 questions
Filter by
Sorted by
Tagged with
16 views

### An FPT algorithm for Hamiltonian cycle running parameterized by treewidth

I'm looking for an algorithm that solves the Hamiltonian cycle problem parameterized by treewidth. In particular, I'm curious about such an algorithm running in $tw(G)^{O(tw(G))}⋅n$ time. But I can't ...
15 views

### Algorithm for finding a hamilton cycle in graph with tree width bounded

Show that the Hamiltonian Cycle problems can be solved in time $k^{O(k)}n$ on an $n$-vertex graph given together with its tree decomposition of width at most $k$. I am learning tree width related ...
229 views

### Does the graph contain a Hamiltonian and an Euler cycle?

Question: Let $G=(V_n,E_n)$ such that: G's vertices are words over $\sigma=\{a,b,c,d\}$ with length of $n$, such that there aren't two adjacent equal chars. An edge is defined to be between two ...
35 views

9 views

### Cyclical paths and deformation-dependent orientation

The points of a unit circle may be traversed either clockwise or counterclockwise without a traveller reversing direction, moving only "forward." If a unit circle is deformed to have a ...
18 views

### Hamiltonian cycles in a quotient graph and original graph

I am currently reading regarding Hamiltonian cycles and I came across the following. "Suppose, $N$ is a cyclic normal subgroup of $G$, such that $|N|$ is a prime power. $<s^{-1}t> = N$, ...
8 views

### Proofing that $|EX(n,P_k)|$ = 1

Let $P_k$ be path at size k vertexes , and $EX(n,P_k)$ the group of all unqiue graphs that dosent contain $P_k$ as a sub graph and have maximum amount of edges possible. Need to proof that there is ...
50 views

### Hamilton Graph is 2-connected

Show that a Hamiltonian graph is 2-connected. But the reverse is not true. Give an example for reverse. This guestion is my profesor's. I'm having difficulty in proving the above statement. Hoew can I ...
30 views

### How do I figure this out using Dirac's theorem?

I know that Dirac's theorem states “If $G$ is a graph with $n$ vertices, $n \geq 3$, each of degree at least $n/2$, then $G$ is Hamiltonian”, but how do I use this to prove that a graph with $99$ ...
76 views

### Determine if the graph is Hamiltonian using Dirac's theorem [closed]

I know that Dirac's theorem states “If $G$ is a graph with $n$ vertices, $n \geq 3$, each of degree at least $n/2$, then $G$ is Hamiltonian”, but how do I use this to prove that a graph with $99$ ...
46 views

### Is it true that $G^2$ is always hamiltonian?

Given a connected graph $G$, define $G^2$ to be a graph with same vertex set as $G$ and edge between two vertices $u$ and $v$ iff the distance between $u$ and $v$ in $G$ is at most $2$. Is it true ...
27 views

### Algorithm for a directed long path and disconnected sets

I'm looking at this algorithm, and I want to get something similar that leaves me with a "long directed path", and two weakly disconnected components (meaning there are no edges from one ...
87 views

### Degree sequence in a maximal planar graph

Two isomorphic 9 vertex graphs Given the ordered degree sequence of a hamiltonian circuit in a maximal planar graph. Can we have different maximal planar graphs with the same ordered degree sequence? ...
88 views

### Ultra-Hamiltonian cycle

Ultra-Hamiltonian cycling is defined to be a closed walk that visits every vertex exactly once, except for at most one vertex that visits more than once. Question:- Prove that it is NP-hard to ...
48 views

### simple graph with n vertices and hamiltonian cycle

we have a simple graph with n vertices and hamiltonian cycle, prove it has 2 even subgraphs T,S such as each edge of G is at least in one of T or S. part 2: if n is even , prove it has 2 odd subgraphs ...
31 views

### Is there any new developments on the Barnette's conjecture?

When I searching for interesting math problems. I find there is a graph theory conjecture called the Barnette's conjecture. The statement is: Is every bipartite simple polyhedron Hamiltonian? A early ...
43 views

### How to find a Hamilton cycle contains the edge 37 in K11 graph?

Let $V(K_{2n+1}) = \{0, 1, 2, ..., 2n-1, x\}$. We have a standard way of decomposing $K_{2n+1}$ into Hamilton cycles. In $K_{11}$, which "standard" Hamilton cycle contains the edge $37$?
25 views

164 views

### what is a path called that visits every vertex of a graph at least once?

As I understand it, a Hamiltonian path visits every vertex of a graph exactly once. Is there a name for a path which visits every vertex at least once? Some graphs may be such that a cycle visiting ...
34 views

### Value of a hamiltonian path along a function closely related to the hamiltonian function

Consider $T^*M$ with the canonical symplectic structure. Let $H:T^*M\rightarrow \mathbb{R}$ be an hamiltonian function and $h:\mathbb{R}\rightarrow \mathbb{R}$ a smooth function. Let $\gamma(t)$ be ...
65 views

### Hamiltonian Paths and Next Neighbor Algorithm in Complete Graphs

In a complete graph, can the next neighbor algorithm (NNA) ever produce the most optimal Hamiltonian path? The NNA is close enough to the most optimal path to be used in real-life applications, but is ...
87 views

### How I can shortly prove that you can have a closed knight's tour on the 6x6 chessboard?

On the website, the explanation that a knight's tour on a $6\times6$ board is possible is the continued proof of around $1\frac{1}{2}$ pages! It will be great if one of you could provide a simple, ...
88 views

### Question about closed knight's tours for n x m chessboard

Is there a simple mathematical algorithm where you can get a CLOSED knight' tour on an n x m chessboard? I need a way to prove that it is mathematically possible or impossible to have a closed knight'...
59 views

### A graph theory problem from mobile games

Example game interface This is the question that comes to my mind when I play a game called QuickyRoute,which essentially a Hamilton graph problem,the game will randomly generate a number of points,...
36 views

### Verifying some properties of Hamiltonian Graphs

I want to verify these two properties of Hamiltonian graphs: Graph having multiple Hamiltonian cycles can have different cycle lengths or all are of same length? i.e. All Hamiltonian cycles have same ...