Questions tagged [hamiltonian-path]

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

Filter by
Sorted by
Tagged with
12
votes
2answers
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.) ...
20
votes
3answers
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, ...
0
votes
3answers
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 ...
1
vote
1answer
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 (...
8
votes
1answer
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.
5
votes
4answers
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 ...
6
votes
3answers
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 ...
2
votes
3answers
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?
2
votes
2answers
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}}$ ...
2
votes
2answers
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 ...
1
vote
1answer
431 views

Prove $P_m X P_n$ is Hamiltonian if and only if at least one of $m,n$ is even

How to prove "Prove $P_m X P_n$ (graph cartesian product) is Hamiltonian if and only if at least one of $m,n$ is even" Graph cartesian product is Grid graph, if I figure out $P_2 X P_2$ it will be $...
1
vote
2answers
841 views

Hamiltonian and non-Hamiltonian connected graph using the same degree sequence

I'm trying to find out if it is possible to construct a connected Hamiltonian and a connected non-Hamiltonian graph using the same degree sequence. For disconnected graphs it would be easier, I could ...
7
votes
2answers
7k views

Proof of Hamilton Cycle in a Complete Bipartite Graph

For a complete Bipartite graph K(m,n) has a Hamilton cycle if and only if m=n. I want to know if the following proof technique is correct. My proof will consider using proof by contradiction. Assume ...
3
votes
0answers
158 views

How to generate a Penrose tessellation around a given tile?

Given a starting Penrose tile, I need to build a "spiraling" tessellation around it. The following picture illustrates the request: In this example, the starting tile is a "thin rhombus" (the pink ...
0
votes
1answer
491 views

Probability of choosing a graph with Hamiltonian cycle

Given $N$ labeled points in a plane one can construct $2^{N(N-1)/2}$ graphs(Unweighted, undirected) with them. Is there any theorem that gives the probability of choosing at random from these a graph ...
5
votes
3answers
1k views

Pigeonhole Principle to Prove a Hamiltonian Graph

I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it's indeterminable with minimal information: A graph has 17 vertices and 129 edges. ...
2
votes
1answer
2k views

Show that 3-regular graph (with Hamiltonian cycle) has chromatic index 3

I would like to show the following: Show that if a regular graph with degree 3 has a Hamiltonian cycle, then it has an edge colouring with three colours. Is it correct to use the following ...
2
votes
1answer
248 views

Spiral path on a Penrose tiling

I would like to color a Penrose tiling by following a "spiral path", painting each tile according to a given color sequence. In this picture, I illustrate what I am looking for: The dashed line ...
1
vote
1answer
79 views

How to convert a maximal planar graph to a regular planar multigraph?

Given a maximal planar graph (coming from the convex hull of a set of points on a sphere), I want to add edges until it is regular (all vertices touch the same number of edges), while keeping it ...
7
votes
1answer
168 views

Is there a name for graphs with the following property?

The property of the graph is the following: For any vertex, there is a hamiltonian path starting with this vertex, but the graph is not hamiltonian. The following graph is a small example: Important ...
6
votes
0answers
134 views

Is there a relationship between local prime gaps and cyclical graphs?

By defining the following algorithm I was able to generate some interesting graphs using the values of the gaps between consecutive primes: Start in any prime $p_i$, this will be the initial ...
5
votes
1answer
137 views

Provable Hamiltonian Subclass of Barnette Graphs

Given a bicubic planar graph consisting of faces with degree $4$ and $6$, so called Barnette graphs. We can show that there are exactly six squares. Kundor and I found six types of arrangements of the ...
3
votes
1answer
490 views

Finding the number of Hamiltonian cycles for a cubical graph

A problem I'm working on reduced to finding a closed loop that visited every node of a cube. I remembered this was called a Hamiltonian cycle, and so I needed to find the number of Hamiltonian cycles. ...
3
votes
1answer
36 views

Prove a lower limit of $|E(G)|$ where for any $u,v\in G$, there exists a Hamilton path

Define a "Hamilton-connected graph $G$" as For any vertices $u, v \in G$, a Hamilton path exists, where the two ends of the path are vertices $u$ and $v$. Try to prove that if $G$ is a Hamilton-...
2
votes
2answers
959 views

Clarifying Dirac's theorem

Theorem : If $G$ is a simple graph with $n$ vertices with $ n ≥ 3$ such that the degree of every vertex in G is at least $ n/2$, then $G$ has a Hamilton circuit. In this if $n$ is odd, should I ...
2
votes
1answer
3k views

Prove Dirac's Theorem by induction on the number of vertices

Dirac's Theorem says: If a connected graph $G$ has $n \ge 3$ vertices and $\delta(G) \ge \frac{n}{2}$, then $G$ is Hamiltonian. Now I want to prove this theorem by induction on $n$. For $i=3$,...
1
vote
0answers
82 views

A contradictory relation between probability and number of paths

Consider an urn containing $c$ balls, $\alpha$ of which are red, $\beta$ of which are blue, and $\gamma$ of which are green, and $\alpha+\beta+\gamma=c$. We perform $n$ trials with replacement of one ...
1
vote
1answer
2k views

The number of Hamiltonian cycles in the complete bipartite graph

I know that in the complete bipartite graph $K_{n,n}$ , there is $\frac{n!(n-1)!}{2}$ or $n!(n-1)!$ Hamilton cycles. wiki says first, wolfram says the second one. I know that there is $2n$ ways to ...
1
vote
2answers
307 views

Prove that $G$ with 21 vertices with at least 200 edges is Hamiltonian

I'm stuck with this question. 1. Let G be a simple graph on 21 vertices with at least 200 edges. Show that G is Hamiltonian. I tried to use Dirac's theorem to prove it but it is inconclusive because ...
0
votes
1answer
260 views

How many Hamiltonian cycles are there in a complete graph that must contain certain edges?

Consider a complete graph $G$ that has $n \geq 4$ vertices. Each vertex in this graph is indexed $[n]=\{1,2,3, \dots n\}$ In this context, a Hamiltonian cycle is defined solely by the collection of ...
0
votes
1answer
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 ...
0
votes
1answer
603 views

dirac's theorem not work

I am studing graph theory specifically hamiltonian cycles I have a doubt with a exercise, it is a connected simple graph with 13 vertices, the book says that this graph has a hamilton cycle(truly it ...
-1
votes
1answer
288 views

hamiltonian cycle need assistance [duplicate]

so I'm trying to complete this question for uni and am stuck. show that G = (V, E) has no Hamiltonian cycle, where the vertices are V = {a, b, c, d, e, f, g} and the edges are E = {ab, ac, ad, bc, ...