Questions tagged [hamiltonian-path]

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

Filter by
Sorted by
Tagged with
20
votes
3answers
7k 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, ...
16
votes
1answer
324 views

Covering pairs with permutations

Consider an $n \times n$ matrix $M_n$ with the following properties: Each row is a permutation of $A_n \equiv \{1, 2, ..., n\}$. Every ordered pair $(i,j)$, $i,j \in A_n$, $i \neq j$, appears as a ...
13
votes
1answer
390 views

Who has a winning strategy in the hamilton-circle-game?

The game starts with a graph with $n$ vertices and no edges. The players alternately add edges until the graph contains a hamilton-circle. The player who made the last move loses. Who has a winning ...
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.) ...
11
votes
2answers
799 views

Can a bipartite graph have many Hamiltonian paths but no Hamiltonian cycle?

Can a bipartite graph with at least three vertices have the following properties simultaneously: Every vertex is the initial vertex of some Hamiltonian path. The graph contains no Hamiltonian cycle. ...
10
votes
3answers
3k views

Is this graph Hamiltonian?

I know that a Hamiltonian graph has a path that visits each vertex once. But I am not sure how to figure out if this one does. Obviously I can try and trace various different paths to see if one works ...
9
votes
1answer
823 views

What is the maximum number of edges in an $n$-vertex non-Hamiltonian graph of minimum degree at least $2$?

Q: What is the maximum number of edges in an $n$-vertex non-Hamiltonian (simple) graph of minimum degree at least $2$? This question relates to Maximum number of edges in a non-Hamiltonian graph ...
9
votes
0answers
119 views

How many hamilton paths can a non-hamiltonian graph have?

What is the maximum number of hamilton paths a graph with $n$ vertices can have without having a hamiton cycle ? If my turbo pascal program works well, the first few values for $3,4,...$ vertices ...
8
votes
1answer
213 views

Does knowing a graph has a Hamiltonian Cycle make it easier to find the cycle?

Given a simple and connected graph $G=(V, E)$. I know it's NP-Complete to determine if $G$ has a Hamiltonian Cycle (HC). But if we know $G$ indeed contains an HC, can we find the cycle in poly-time?
8
votes
1answer
714 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.
8
votes
2answers
260 views

Chance of Hamiltonian Path in Sudoku cell

Checking the correctness of a daily Sudoku I'd just finished, I noticed a curious pattern in one of the 3x3 cells: 1 9 3 8 2 4 7 6 5 Note that each of the ...
8
votes
1answer
375 views

All 4-connected planar graphs are Hamiltonian-connected

I started reading Thomassen's paper A Theorem on Paths in Planar Graphs, where he proves one of Plummer's conjectures: Every $4$-connected planar graph is Hamiltonian-connected. Context. Recall that ...
8
votes
2answers
399 views

Hamiltonian Weighted Graph and Decision Problems

I ran into a question on previous Mid-Exam. anyone could clarify me? Problem A: Given a Complete Weighted Graph G, find a Hamiltonian Tour with minimum weight. Problem B: Given a Complete Weighted ...
7
votes
1answer
169 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 ...
7
votes
0answers
131 views

The number of Hamiltonian paths in a tournament is always odd?

A tournament is defined as an orientation of a complete graph. Prove or disprove the following statement: In a tournament, there are exactly an odd number of Hamiltonian paths. In all cases I’ve ...
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 ...
6
votes
2answers
392 views

Finding a Hamiltonian cycle for the set of RGB colors?

I'm consulting on an art project where a question about colors came up. Consider the RGB colors as a graph. The nodes are ordered triples $(r, g, b)$ where each entry is an integer from $[0, 255]$....
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 ...
6
votes
2answers
375 views

How many routes are there from $A$ to $B$ that cross every node exactly once?

Imagine an $n \times n$ grid, we start on one corner of the grid in square $A$, and need to reach the opposite corner to square $B$. The rules are, you can only move to an adjacent square, you can't ...
6
votes
2answers
323 views

Prove that if $G$ is a tree, then $G^3$ is Hamiltonian.

The graph $G^n$ is a graph obtained by connecting every pair of vertices $a,b$ in $G$ with $d(a,b) \le n$. Prove that if $G$ is a tree, then $G^3$ is Hamiltonian. If $G$ is tree and $G^n$ is ...
6
votes
1answer
1k views

Proof that there is no closed knight tour on a $3\ \times\ 8$ - board

I want to prove that there is no closed knight tour on a $3\ \times\ 8$ - board by deleting $s$ vertices of the corresponding knight graph to get a graph with more than $s$ connected components (...
6
votes
1answer
83 views

Is this the smallest graph with the desired properties?

The above graph has the following properties : $1$) Every vertex is start vertex of some hamiltonian path. $2$) It contains no hamiltonian cycle. $3$) It has no cycle of length $3$. $4$) It is planar....
6
votes
1answer
524 views

Homework - Proof: Is this particular graph Hamiltonian?

I have a homework for my class to Combinatorics and Graphs which I'm not sure how to finish. The task: Let G be a simple graph on 14 vertices, with 4 vertices having degree 5 and 10 vertices having ...
6
votes
0answers
69 views

Do the two order-4 Latin square graphs have the same number of Hamilton cycles?

A Latin square graph of a Latin square $L=(L_{ij})$ of order $n$ has $n^2$ vertices $(i,j)$ and edges between distinct vertices $(i,j)$ and $(i',j')$ whenever (a) $i=i'$, (b) $j=j'$, or (c) $L_{ij}=L_{...
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
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 ...
5
votes
2answers
235 views

Playing Doublets with the Primes

Lewis Carroll's famous game of Doublets is well known. In it you are asked to transform a given word into another by changing only one letter at a time, forming a genuine new word (not a proper name) ...
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. ...
5
votes
1answer
508 views

A connected simple graph $G$ has $14$ vertices and $88$ edges. Prove $G$ is Hamiltonian, but not Eulerian…

A connected simple graph $G$ has $14$ vertices and $88$ edges. Prove $G$ is Hamiltonian, but not Eulerian. -I almost feel like you have to prove these two parts separately. I understand that to be ...
5
votes
1answer
197 views

Random graphs with a hamiltonian path

Suppose we randomly choose a graph with $n$ vertices in the following manner: each edge is included with probability $\frac12$. Thus, each graph has the same probability of being chosen, and there are ...
5
votes
1answer
65 views

Is there a path through the “flipbook” of the game 504?

Inspired by discussion on this forum. For background, the game 504 is named as such because there are 504 possible "variations" formed by picking 3 modules from a possible 9 (where order is important)....
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 ...
5
votes
1answer
325 views

Probability of finding a Hamilton circuit in a graph

In short, I would like to know either/both the probability that there exists a Hamiltonian circuit within a graph, or the number of circuits expected to exist. (Without actually finding all the ...
5
votes
0answers
44 views

NP-Complete proof of deciding if a graph has another Hamiltonian Circuit

I need to prove as an exercise that the following problem is NP-Complete: Given a graph and an already existing Hamiltonian Circuit in that graph, decide if the graph has another Hamiltonian Circuit ...
4
votes
1answer
1k views

(Graph Theory) Prove that $H_n$ has a Hamiltonian cycle for $n$ ≥ 2.

Where $H_n$ is the graph that has a vertex for each n-digit binary sequence such that 2 vertices are connected if their binary sequences are different in exactly 1 digit. Attempt: By induction on n ...
4
votes
3answers
4k views

Hamilton paths/cycles in grid graphs

Let G be a grid graph with m rows and n columns, i.e. m = 4, n = 7 is shown here: For what values of m and n does G have a Hamilton path, and for what values of m and n does G have a Hamilton cycle? ...
4
votes
1answer
4k views

How To Tell If A Graph is A Hamiltonian?

So, I can look at this graph and tell that it is not a Hamiltonian, but I do not know the actual mathematical reason why. I can see that if you start on one vertex, then it would be impossible to ...
4
votes
3answers
20k views

Proving Hamiltonian Cycle is NP Complete

I'm trying to learn Complexity classes.I want to show Hamiltonian cycle is NP Complete. The text tells me that Inorder to prove NP-Completeness we first show it belongs to NP,by taking a certificate....
4
votes
1answer
444 views

Prove that every 8-regular graph has 4-and 2-regular spanning subgraph!

Prove that every $8$-regular graph has $4$- and $2$-regular spanning subgraphs. Note: A graph is spanning subgraph, if it contains every vertex of the original graph. Furthermore this example's from ...
4
votes
1answer
62 views

Listing the elements of a covering for a closed disk by open disks

This problem is somewhat related to some homework I had recently. However, as stated, I don't know if a solution yet exists. I asked some friends and some of my professors, but none of them know how ...
4
votes
1answer
13k views

How many Hamiltonian circuits are there in a complete graph with n vertices? [duplicate]

How many Hamiltonian circuits are there in a complete, undirected and simple graph with $n$ vertices? The answer written in my book is: $$\frac{\left(n-1\right)!}{2}$$ What is the combinatorial ...
4
votes
3answers
4k views

Graph Theory: Trees, leaves and cycles

So, a vertex is called a leaf if it connected to only one edge. a) Show that a tree with at least one edge has at least 2 leaves. b) Assume that G = (V, E) is a graph, V ≠ Ø, where every vertex ...
4
votes
1answer
344 views

Reduction Algorithm from Prime Factorization To Hamiltonian Path Problem

How would you go about creating a reduction algorithm that would allow you to solve prime number factorization using Hamiltonian path finding? Context: I was reading on P vs. NP and it heavily relies ...
4
votes
1answer
497 views

How many ways to visit 4 cities so that each city is visited exactly 4 times without visiting the same city twice in a row?

The inclusion-exclusion principle doesn't work. Example of good path is: $$ 1\to 2\to 1\to 4\to 3\to 2\to 1\to 4\to 3\to 2\to 1\to 3\to 2\to 4\to 3\to 4$$ This one isn't: $$ 1\to 2\to 1\to 1\to 3\...
4
votes
1answer
66 views

Let $G = (V,E)$ be a tree, then $G$ is a caterpillar graph $\iff$ The line graph of $G$ contains a Hamiltonian path.

Here the line graph $L(G)$ of $G$ is defined by $L(G) := (E,\{ef : e,f \in E, e \bigcap f \neq \oslash\})$. I think I have an argument for the forward direction. If G is a caterpillar graph on $n$ ...
4
votes
0answers
165 views

Prove or disprove that a graph made by $n$ straight lines is Hamiltonian.

Given $n$ lines, no two of which are parallel and no more than two intersect at the same point. Construct a graph with the intersection of lines as vertices and the line segments as edges. Prove or ...
4
votes
0answers
210 views

Hamiltonian path on a chessboard with prescribed endpoints

On an 8 x 8 chessboard consider two squares to be adjacent if and only if they share a common side. All paths below will consist of steps which join one square to an adjacent one. Under these ...
4
votes
0answers
47 views

Existence of fair parallel queues

I just spent a few days at a major theme park. The queue for one particular ride (involving pirates) bifurcated upon entry; the two sides wound independently through a maze and emerged next to each ...
3
votes
1answer
124 views

How to calculate quantity of Hamilton cycles

If I have $n^2$ vertices and each vertex is adjacent to $2n-2$ vertices, how may I calculate the quantity of possible Hamilton cycles? Would I need to modify the computation if I stipulated that I'm ...
3
votes
2answers
176 views

Diameter of a graph consisting of Hamilton cycles

Imagine an undirected graph $G = (V,E)$ with $|V| = n$ nodes. Its unweighted edges $E$ are the union of $h$ random Hamiltonian cycles through all nodes, each generated iid uniformly at random from the ...