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

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 ...