# Questions tagged [hamiltonian-path]

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

587 questions
Filter by
Sorted by
Tagged with
51 views

### Hamilton cycle on chessboard

Suppose we have $8 \times 8$ chessboard such that two squares are adjacent iff they share a common side. In one move pawn can move to adjacent square. Prove that the pawn made a different number of ...
• 45
9 views

### What is the time complexity to finding the least weight for Hamiltonian cycle in complete graph without finding best tour?

As we know finding the best tour in complete graph with n nodes, or the Traveling Salesperson Problem solved by the dynamic programming algorithm in $n^2.2^n$ time ...
• 619
25 views

### An extension of Dirac Theorem

Following a related proof of Dirac theorem, I want to show that if $G$ is a balanced bipartite graph of order $n$ with minimum degree more than $n/4$, then $G$ has a Hamilton cycle. Dirac's theorem: ...
• 571
1 vote
28 views

### What is the necessary and sufficient condition for a graph to be a Hamiltonian Chordal Graphs?

Chordal Graph. A chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Hamiltonian ...
• 1,174
15 views

### Hamiltonian Cycle but Minimise Distance Between Nearest Point in Other Set

I have two sets of points in $\mathbb{R}^2$, let's call them red and blue. I would like to create a Hamiltonian Cycle, i.e., cycle going through all points once. This cycle should minimise the ...
40 views

• 70.1k
22 views

### Prove that these two connected Petersen subgraphs are Hamiltonian (or not).

I'm currently revisiting some graph theory and have ran into the following graph. I am to prove if it is Hamiltonian or not. To my knowledge there is no definite or "good" theorems to ...
1 vote
11 views

### Which requirements should a TSP matrix fulfill in order to be solved with Hungarian method?

I was reading about TSP problem in general & about Hungarian method in particular, and found a 6x6 matrix, where applying Hungarian method didn't give me an answer (solved by hand & checked on ...
67 views

### Hamiltonian Cycle and Euler Cycle

True/False: Let $G$ be a connected undirected graph such that all vertices have even degrees. Every Euler cycle in $G$ is also a Hamiltonian cycle if and only if $G$ is a cycle graph. I think this one ...
• 1
57 views

### How many different ways can single directed edge be added.... (graph theory)

Let G be the following directed graph: In how many different ways can a single directed edge be added to G3 so that there is a cycle of length 8 starting at vertex A? I tried a few ways of inserting ...
• 325
26 views

### Hamiltonian cycle with additional constraints

I could use a little guidance to solve the following mathematical problem. I have a fully connected graph with bidirectional edges of known weight > 0. The weight of an edge depends on the ...
• 111
1 vote
44 views

### Non hamiltonian cubic graphs

It is known that almost all cubic graphs are hamiltonian (see here) However, I did not find any information about non-hamiltonian cubic graphs online. If you know some properties/literature about non-...
• 231
36 views

### Non-isomorphic non-hamiltonian graphs

I have the following question: Find an infinite family of non-isomorphic graphs without hamiltonian paths such that $\delta(u) + \delta(v) \geq |V(G)| - 2$ for every non adjacent vertices $u, v$. I'...
23 views

### Size of a path defined on a Hamiltonian cycle

Let $G=(V,E)$ (Such that $\vert V\vert$) be a Hamiltonian cubic graph and $v\in V$. We represent a graph as a cycle with vertices labeled in such a way that $(0,\ldots ,n-1)$ is a Hamiltonian cycle ...
• 231
44 views

### Prove that, if all perfect matchings in G are pairwise disjoint, than every two perfect matchings contain the edge set of a hamiltonian cycle in G.

I have no idea how to prove this one. It looks like common sense, but I don't know hot to proceed with the proof.
72 views

### Minimal collection of paths that visit all vertices of a subgraph

Assume we have a weighted, directed Graph $G$ with vertices $V$. There are vertices named START and END in the graph. Among all possible paths from START to END, I want to select paths that, together, ...
24 views

### Algorithm for finding a hamilton cycle in graph with tree width bounded

Show that the Hamiltonian Cycle problems can be solved in time $k^{O(k)}n$ on an $n$-vertex graph given together with its tree decomposition of width at most $k$. I am learning tree width related ...
256 views

### Does the graph contain a Hamiltonian and an Euler cycle?

Question: Let $G=(V_n,E_n)$ such that: G's vertices are words over $\sigma=\{a,b,c,d\}$ with length of $n$, such that there aren't two adjacent equal chars. An edge is defined to be between two ...
• 862
1 vote
58 views

• 153
25 views

### How to calculate the period of Hamiltonian by using its eigenvalues?

I am studing how the solutions for analytic functions evolve with time by using Hamiltonian matrix,and I want to Know the periodic of the path of zeros . I used this relation $exp(iTH)=I$ if when ...
### Why are the total (non-distinct) Hamiltonian circuits in complete graph $K_n$ $=$ $(n−1)!$
I came across this answer on a very similar question which says: Total (non-distinct) Hamiltonian circuits in complete graph $K_n$ is $(n−1)!$ This follows from the fact that starting from any vertex ...