Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [hamiltonian-path]

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

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, ...
16
votes
1answer
294 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
362 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
1answer
9k 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
743 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
728 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
113 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
682 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
242 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
2answers
369 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 ...
8
votes
1answer
210 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 ...
7
votes
1answer
163 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
2answers
388 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
360 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
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
80 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
496 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
87 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 ...
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
132 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 ...
6
votes
1answer
6k 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 ...
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
215 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
1answer
479 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
145 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
2answers
278 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 ...
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
133 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
311 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
31 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
3answers
19k 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
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. ...
4
votes
1answer
408 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
11k 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
3k 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
322 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
466 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
61 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
160 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
198 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
45 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
944 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 ...
3
votes
3answers
3k 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? ...
3
votes
1answer
115 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
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 ...
3
votes
2answers
159 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 ...
3
votes
1answer
877 views

Proof: Gradient of a Hamiltonian System

I am trying to prove the following: Given that $f \in C^1(E) $ where E is a open simply connected subsets of the plane. Show that the system $\dot x=f(x)$ is a hamiltonian if and only if $\nabla \...
3
votes
0answers
144 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 ...