Questions tagged [hamiltonian-path]

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

33 questions
Filter by
Sorted by
Tagged with
10k views

Prove that every tournament contains at least one Hamiltonian path.

A tournament is a directed graph with exactly one edge between every pair of vertices. (So for each pair (u,v) of vertices, either the edge from u to v or from v to u exists, but not both.) ...
6k views

How many knight's tours are there?

The knight's tour is a sequence of 64 squares on a chess board, where each square is visted once, and each subsequent square can be reached from the previous by a knight's move. Tours can be cyclic, ...
270 views

A $3 \times 3 \times 3$ cube has no Hamiltonian path starting at the corner.

We have a $3\times3\times 3$ cube which has $27$ cubes each $1\times1\times1$ stuck together as usual. $2$ cubes are neighbours if they have a common face. The corner cubes are the $8$ cubes at the ...
350 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 (...
705 views

Does every connected $r$-regular bipartite graph contain a Hamiltonian cycle?

Here's a quickie: Let $r\ge2$. Does every connected $r$-regular bipartite graph contain a Hamiltonian cycle? I've been playing around with this for almost an hour, but I can't prove it.
5k views

Maximum number of edges in a non-Hamiltonian graph

I need to show that the maximum number of edges of non-Hamiltonian, simple graph, on $n$ vertices noted by $t(n,H_n)$ is $\binom{n-1}{2} + 1$. It's essential to show the upper and lower bounds for ...
4k views

Proving that a graph of a certain size is Hamiltonian

For any graph with order $n \geq 3$, given that its size is $$m \geq \frac{\left(n-1\right)(n-2)}{2} + 2,$$ show that the graph is Hamiltonian. I know that if I can show that the degree sum of any ...
8k views

Number of edge disjoint Hamiltonian cycles in a complete graph with even number of vertices.

In a complete graph with $n$ vertices there are $\frac{n−1}{2}$ edge-disjoint Hamiltonian cycles if $n$ is an odd number and $n\ge 3$. What if $n$ is an even number?
526 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}}$ ...
2k views

A closed Knight's Tour does not exist on some chessboards

It is generally difficult to determine whether a (large) graph have no Hamilton cycle (As opposed to determining whether it has any Euler circuit). This example illustrates a method (which sometimes ...
431 views

277 views

Variation of TSP - Revisit Nodes

I have a problem where I have an symmetric graph and I want to find that shortest path that visits every node at least once (not exactly once). In order to solve this problem, I have found that we ...