# Questions tagged [hamiltonian-path]

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

395 questions
282 views

### Greatest number of edges in a graph not containing a hamilton path

Inspired by the question, where the greatest number of edges in a hamiltonian graph was asked, I have a similar question, but for hamilton paths. How many edges can a simple undirected graph contain,...
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 ...
160 views

### Conditions for a $2$-connected graph to be hamiltonian?

Let G be a simple undirected graph. If G is connected, and every vertex has degree $2$, then G is hamiltonian. (In fact, G only consists of the hamilton-circle) Are there some weaker sufficient ...
727 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 ...
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 ...
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 ...
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 (...
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....
132 views

### Studying Hamiltonian PDEs - Where to start?

I first got in contact with Hamiltonian PDEs when I wrote my first thesis about the Nash-Moser-Theorem as some books mentioned them as a field of application of this theorem. As those examples were ...
79 views

### Hamiltonian cycle adjacency sum Proof

Let $C$ be a Hamiltonian cycle on a graph with vertices labeled {$1,...,9$}. Prove that there are $3$ vertices adjacent in $C$ whose labels sum to at least $12$. I understand why this fact is true by ...
7k 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?
767 views

### Hamiltonian paths in bipartite graphs

Is there a way to find the exact number of Hamiltonian paths in special cases of bipartite graphs, for example, the K(n,n) complete bipartite graph for n ≥ 3? Thanks.
81 views

### Hamiltonian form of PDE

I am quite new in this field and I was wondering what does exactly mean to write a PDE (in 2 or 3 dimensions) in an Hamiltonian form. More in detail, is there any standard procedure to write a given ...
43 views

### Making a graph Hamiltonian by stacking it up

Consider a graph $G$. As usual, denote a path graph of length $n$ as $P_{n}$, and $\times$ is for Cartesian product of graph. If $G$ is Hamiltonian (ie. have a Hamiltonian cycle) then it is easy to ...
128 views

### Is there away to swap adjacent items in a sequence, such that each permutation occurs once?

Let's us say you have a finite sequence of things. Some are identical, some distinct. For example: $$\langle 2,5,7,2,3\rangle$$ Now, under what conditions can each permutation of a sequence be ...
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.
90 views

165 views

### Question on hamiltonian graph

Can anyone give me an example of a Hamiltonian graph $H$ of order $n=2k$ for some $k\geq 2$ where $k$ vertices have degree $2$, no two vertices of which are adjacent, while the remaining vertices have ...
201 views

### Complete tripartite graph hamiltonian

Let $G_{a,b,c}$ be a complete tripartite graph. For what values of $a, b$ and $c$ is $G_{a,b,c}$ Hamiltonian?
3k views

### Graph Theory: How do we know Hamiltonian Path exists in graph where every vertex has degree ≥3?

I am trying to prove that if every node of a graph G has degree of at least 3 then G contains a cycle and a chord. My current approach is as follows: Separate the graph G into connected components ...
413 views

### Are there necessary and sufficient conditions of a graph to decompose into two Hamiltonian cycles?

Let $G$ be a graph. Definition: $G$ is decomposable into two Hamiltonian cycles if the edge set $E(G)$ can be partitioned into two disjoint Hamiltonian cycles. Obviously, if $G$ is decomposable into ...
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 ...
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 ...