# Questions tagged [hamiltonian-path]

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

496 questions
Filter by
Sorted by
Tagged with
27 views

### Is there a technique to find a hamilton circuit in a graph?

My textbook goes in depth about how to show that a graph does NOT have a hamilton circuit, but one of its practice problems asks you to find a hamilton circuit in a graph that does have a hamilton ...
32 views

### Hamiltonian path, how to speed up?

Given an undirected graph with N nodes, each node has at most sqrt(2*N) edges. I have ...
49 views

### Uniqueness of hamiltonian cycle

Let G be a graph on $n$ vertices, where $n \geq 8$ and with minimum degree at least $n/2$. Does $G$ have at least 2 distinct Hamilton cycles? (Two Hamilton cycles are said to be distinct if they ...
59 views

### That every 5-vertex path in the dodecahedron lies in a Hamiltonian cycle?

In this problem ,it occurred to me that erasing the vertices that are between the trajectory, it only remains to show that there is a Hamiltonian path from the first to the last vertex of the ...
71 views

### What is the difference between a Hamiltonian Path and a Hamiltonian Cycle?

The title says it all. I've seen confusing definitions of this, and would appreciate if someone can succinctly clear this up with definitions and examples.
57 views

### Why are there $40$ paths in a $3\times 3$ grid?

If I have a thread of length $4$ that I want to lay on a $2\times 2$, there are $8$ ways to do it, apparently. That because from every node I can go clockwise or counter clockwise, right? But ...
40 views

### Karp reduction from HC to HP. What am I doing wrong?

I know there is this solution for Karp reduction from HC to HP in here (INDIRECTED graph). But I was thinking about something else, and would like to know what you think about it. I create 2 new ...
32 views

### Does every $r$-regular, $r$-edge-connected, bipartite graph contain a Hamiltonian path?

The following question is similar to another I recently asked, however, it restricts the graph class further by requiring regularity and edge-connectedness to be equal. Given a $r$-regular, $r$-edge-...
78 views

### Does every regular, bipartite graph contain a Hamiltonian path?

This may be a rather straight-forward question; however, I am unable to arrive at an answer myself. Given a $r$-regular, $k$-edge-connected, bipartite graph, will there always be a Hamiltonian path in ...
21 views

### Add smaller Hamiltonian circuits to make bigger one

Is it always possible to generate a Hamiltonian circuit by adding smaller ones? For example, a 8x8 grid can be split into four 4x4 grids, each having a Hamiltonian circuit. In this case, it is ...
34 views

### Prove that in a full oriented connected graph there is a cycle passing through all the vertices [duplicate]

Prove that in a full oriented connected graph there is a cycle passing through all the vertices. I tried to find contradictory example.But there are not any contridictions. I tried also to put ...
38 views

### Proof checking: Graph Theory

Question: Prove that if the number of vertices in graph $G$ is $n \geq 2$ and the sum of $2$ degrees is at least $n - 2$, then graph $G$ has $2$ disjoint simple paths that their union completes the ...
48 views

### Graph Theory: Question about union of 2 Paths

Q: Prove that if a graph $G$ has $n \geq 2$ vertices, and the sum of the degrees of 2 different vertices is at least $n-2$ (for any 2 different vertices), then the graph has 2 disjoint simple paths, ...
36 views

### Graph theory: Questions about Hamiltonian cycles.

Prove that if graph $G$ has $n \geq 2$ vertices such that the sum of the degrees of $2$ different vertices is at least $n- 2$, so there are $2$ different simple paths ('foreign' to one another) such ...
17 views

### Prove: if G has a closed hamilton walk then L(G) has one too.

L(G): L Line Graph If G is a graph with e ≠ 0 then the line graph of G, denoted “L(G)”, is the graph having one vertex corresponding to each edge of G and such that two vertices of L(G) are joined by ...
32 views

### Prove that de-bruijn graph has Hamiltonian cycle?

Let $G_{2,n}$ be a de-bruijn graph. We remove the vertex 11...11 and the vertex 00...00 and all edges connected to them. Q: ...
37 views

### Hamiltonian path between two specific nodes

We have a simple undirected connected graph G and two specific nodes s and t. We delete a node and gets to a graph G' that it has a hamiltonian path between s and t. What necessary conditions has to ...
27 views

### Can a disjoint union of two sets be a connected graph?

Can A ⊎ B, where |A| ≠ |B|, be a complete graph? There is a lemma about Hamiltonian cycles which states: If G = (A ⊎ B| E) is a bipartite graph, |A| ≠ |B|, then there is no Hamiltonian cycle in G. ...
34 views

### How to show the following cubic graph is Hamiltonian?

Suppose we have a complete graph $K_{2n}$, where $n$ is an integer, and we number vertices counterclockwise as $1,2,\cdots,2n.$ Then we give weight to the edge connecting $u,v$ as $|u-v|$. Now, ...
43 views

### How to decompose edges of $K_n$ into Hamiltonian paths?

Let $K_n$ be a complete graph with n vertices, where n is even Show that $K_n$ can be decomposed into $\frac{(n-1)}{2}$ disjointed Hamiltonian paths on edges My idea was to use Menger's theorem ...
26 views

### Can a Hamiltonian cycle of an undirected Cayley graph contain inverses of the generating elements?

Let $G$ be a finite group and $S$ be a subset of $G$. Let us define the Cayley graph of $G$ with respect to $S$ as follows, provided that $1 {\not\in} S$ and $S$ is inverse closed. Definition: The ...
32 views

19 views

### What does C(n - 1, 2) edges mean in graph theory?

My graph theory book postulates the if a simple graph with n vertices has at least C(n - 1, 2) + 2 edges then the graph must be Hamiltonian. This is probably true ...
25 views

### Hamiltonian path after removing a node

We have an undirected connected graph $G$ with a hamiltonian path between nodes $a$ and $b$, if we remove a node that this removing doesn't blemish the connectivity ($G$ is still connected and the ...
24 views

### Relationship between the generating elements given by the Hamiltonian cycle of a Cayley graph

Consider the Cayley graph of $\mathbb{Z}_3 \times \mathbb{Z}_5$ generated by the generating set $S=\{g_1=(1,0), g_2=(0,1)\}$. Then $|g_1|=3, |g_2|=5$. Consider a Hamiltonian cycle, $ABCDEFGHIKJLMNO$. ...
22 views

### Is Hamiltonian path NL?

NL is what can be solved by a non-deterministic Turing machine in logspace. Could you non-deterministically "guess" the correct Hamiltonian path in logspace, keeping track of the current vertex (log(...
34 views

### Why there's no hamiltonian cycle for a grid where $m$ and $n$ are odd?

I have read some of the discussions about the topic but while I understand that a grid $n$ x $m$ with $n$ or $m$ even ($n,m>1$) has always an hamiltonian cycle I don't get the reasoning behind the ...
21 views

### Can a bipartite graph not contain a Hamiltonian cycle?

Statement: any bipartite graph contains a Hamiltonian cycle. My answer: No. A bipartite graph which have an odd number of vertices cannot contain a Hamiltonian cycle, since each simple cycle in a ...
61 views

### How to not find a Hamiltonian Cycle

Consider the following naive algorithm for finding Hamiltonian cycles on a simple undirected graph G with n vertices: Choose an arbitrary vertex and mark it as vertex 1 Choose an arbitrary unmarked ...
35 views

### Is a directed complete graph Hamiltonian? (if there are no sink groups)

For some graph G that is complete (Kn) and directed (every edge ab can be traversed in only one way, either a -> b, or b -> a) and has no sink groups. Is G necessarily Hamiltonian? If so why? Define ...
60 views

### Is there a cycle-free graph with a Hamiltonian circuit?

I have an question about graphs. Is there any graph in which there is no cycle, but it has a Hamiltonian circuit? I think there isn't such a graph. Am I right? Thanks for your answer in advance.
70 views

### How many simple graphs (up to isomorphism) have 6 vertices and 8 edges and admit a Hamiltonian circuit

How many simple graphs (up to isomorphism) have 6 vertices and 8 edges and admit a Hamiltonian circuit? Apparently the answer is 6, but how would you prove this?
76 views

### Let $G$ be connected graph $r−$regular, show that if $G$ complement is connected but is not Hamiltonian. Then $G$ is Hamiltonian

I've been stuck in this homewoork problem, and I've already asked my teacher and he told me that I have the idea by contradiction using Ore's Theorem and by watching $r$. But I got some issues ...
68 views

### Probability that a sequence corresponds to a cycle in a graph

Suppose the random undirected graph $G$ is constructed as follows. $G$ starts off as $n$ distinct vertices, where $n$ is even. Independently for each of the possible pair of vertices, we add an ...
33 views

### Is it true that any hamilton graph with “k” vertices has k/2 as the maximum independent set?

A Hamilton graph is a graph that has a Hamiltonian cycle ,which means a cycle exists in this graph in which you can visit every vertex of graph exactly once . My observation is : - Say for a(any) ...
30 views

### Find a hamiltonian path in $T^{3}$

The cube of a graph $T$, denoted $T^{3}$, is the supergraph of $T$ such that the edge $(u, v)$ is in $T^{3}$ if and only if there is a path between $u$ and $v$ in $T$ with three or fewer edges. My ...
Assume we have a set of points $\{A,B,C,\dots,Z\}$ in a plane. What is the shortest path which includes all points once, starts at $A$ and ends in $Z$ and $A \ne Z$ I am trying to identify if this ...