# Questions tagged [hamiltonian-path]

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

396 questions
Filter by
Sorted by
Tagged with
51 views

24 views

### number of edges to build all hamiltonian paths in complete digraph

I'd like to compute the number of edges necessary to build all Hamiltonian paths in a complete digraph. My thoughts so far: Let $N$ be the number of nodes. number of Hamiltonian paths: $N!$ ...
97 views

### Hamiltonian Ore Property Proof, why must be connected?

If G has order $n \ge 3$ and for all pairs of distinct vertices $x$ and $y$ that are not adjacent, $deg(x)+deg(y) \ge n$ then the graph is Hamiltonian. Here is the beginning of the proof: We ...
90 views

### Meeting People at a Party Hamiltonian Graph

Ten people came to my party. Each person meets at least 6 other people, except for my friend Ben who only meets four people. We make a graph H where each person is represented by a vertex, and put an ...
360 views

### Show that there is a path of length k in G

Let G be a connected simple graph with $n \geq 3$ vertices. Suppose that there is a positive integer $k \leq n$ such that $d(u) + d(v) \geq k$ for every pair of non-adjacent vertices $u$ and $v$. Show ...
566 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 ...
797 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 ...
548 views

### prove that a graph with p vertices and $2+(p-1)(p-2)/2$ edges is hamiltonian

A Hamiltonian graph is a graph which has a Hamiltonian cycle. A Hamiltonian cycle is a cycle which crosses all of the vertices of a graph. According to Ore's theorem , if $p \ge 3$ we have this : ...
222 views

### Hamiltonian cycle [closed]

Assume $A_k$ be an undirected graph with $2^k$ vertices, $\forall k > 1$,$k \in Z^+$. We use k-digit binary bit strings to label the vertices of $A_k$, where the labels of adjacent vertices diff ...
203 views

### Hamiltonian Graph Problem

I've been going about the proof of the Snark Graph's (https://en.wikipedia.org/wiki/Snark_(graph_theory)) non-Hamiltonicity. I understand that a snark is connected, bridgeless ( removing any edge ...
137 views

### Pullback of a Hamiltonian

I understand that a Hamiltonian vector field $H$ creates a Hamiltonian flow $\phi_t$. Now, in order to prove that the Hamiltonian is conserved one uses the following \begin{eqnarray*} \frac{d}{dt}\...
591 views

98 views

### Correctly quoting a Hamilton Circuit

This might come across as a slightly petty question. Apologies for this, I am only asking as I have an exam on Graph Theory soon and want to make sure I do things correctly. The definition of a ...
411 views

### Hamilton cycles for bipartite graphs

I know that a hamilton cycle exists for a bipartite graph $K_{m,n}$ if and only if $m=n$ But my question is why is it not possible to have a bipartite graph if $m=n=1$ I mean we would go from $x$ to ...
60 views

### Traveling Salesman with exceptions

Assume a regular TSP problem with n cities. However, in this particular problem, we do not have to visit all the n cities, only a specific subset of them, m, where m<=n. The cities in n but not in ...
319 views

### Is it necessary for hamiltonian cycle to cover all the vertices of the graph??

I have read the definition on wikipedia and it says: In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each ...
117 views

### Finding a Hamiltonian cycle for $Q_4$

A hyper cube $Q_n$ is a graph that have the length-n binary sequences as its vertices. Two vertices are adjacent if they differ in one entry. I found a Hamilton cycle for $Q_3$ as follows 000 \to ...
200 views

### when are Kneser graphs connected?

For the kneser graphs $K(n,k)$. The vertices of $K(n, k)$ are all $k-$subsets of the set $\{1, 2 ,......,n \}$ and two vertices are adjacent to each other if and only if the $k-$subsets are ...
995 views

### Ore theorem vs Dirac theorem- when to use what?

Yesterday I asked a question about how to find hamiltonian paths and circuits in a graph, and I got the following answer: According to the theorem of Ore (to find paths): Let $G$ be a (...
1k views

### can we use vertex degree to detect hamilton path and hamilton circuit?

Hamilton path: goes through every node/vertex exactly once. Hamilton circuit: goes through every vertex exactly one and ends at the starting node/vertex. So i am wondering is possible to use degree ...