Questions tagged [hamiltonian-path]

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

130 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
79 views

Find a Hamiltonian circuit in a given Hamiltonian graph.

I am wonder if there is a polynomial time algorithm(may be probabilistic) that can compute a Hamiltonian circuit in a graph which is known as Hamiltonian graph without other assumption. If there is,...
36 views

For a graph G with greater than or equal to 3 vertices, prove that G is Hamitonian if there is a Hamiltonian path between every pair of vertices

As the title of the question states, a proof for this proposition will be highly appreciated. The proof can either be inductive or, explained in plain English.
26 views

Finite universal numbers

Given an alphabel $\Sigma$, a sequence $\bar{s}$ in $\Sigma^*$ is said to be k-universal if it contains all sub-sequences of $\Sigma^k$. I am interested by the smallest of these k-universal sequences. ...
503 views

Dijkstra algorithm under constraint

I have N vertices one being the source. I would like to find the shortest path that connects all the vertices together (so a N-steps path) with the constraint that all the vertices cannot be visited ...
40 views

Equation relating extremal properties of graphs to probability of a cycle existing

Does some function exist that takes a desired probability of a certain cycle existing in a random graph as input and outputs the extremal properties of a graph to achieve that probability? For ...
1k views

Traveling Salesman with paths instead of points

I have a rectangular area filled with vector paths (an SVG document, to be precise). Starting at the origin, I need to visit every part of every path. For an open path, like a line or an arc, I would ...
28 views

Graph Theory - Does a graph have an eulerian circuit if its edges can be divided into groups, each having a hamiltonian circuit?

Let $G=(V,E)$ be a graph. Its edges can be divided into several groups such that each group has a Hamiltonian Circuit of the original graph $G$. Does $G$ have an Eulerian Circuit? I said yes. ...
78 views

Can it be proven that more than one vertex can individually be removed from a strong tournament and still be strong?

One vertex can be removed from the vertex set, V(T), of a strong tournament, T, so long as |V(T)| is greater than or equal to 4. Any strong tournament has (at least) one Hamilton for every k, where k ...
38 views

Let $C_n$, $C_m$ two cycles, show that $C_n * C_m$ is hamiltonian. Conclude saying that if $G$ and $H$ are hamiltonian then $G x H$ is hamiltonian

Hi I need to prove this: Let $C_n$, $C_m$ two cycles, show that $C_n * C_m$ is hamiltonian. Conclude saying that if $G$ and $H$ are hamiltonian then $G x H$ is hamiltonian But i really don't know ...
146 views

Knights tour dfs search with look ahead

After Using a basic depth first search I was wondering if there was any way to predict a dead end before one becomes apparent? As I know I can stop there becoming multiple dead ends as in a single ...
147 views

Show that if any $k+1$ vertices of $k-$connected graph with at least 3 vertices span at least one-edge, then the graph is hamiltonian.

Show that if any $k+1$ vertices of $k-$connected graph with at least 3 vertices span at least one-edge, then the graph is hamiltonian. I know that a graph $G$ is said to be $k-$connected if there ...
102 views

Proving a game has a winning strategy over a graph $G$ if and only if $G$ has no perfect matching

Two people play a game over a graph $G$ choosing alternately different vertices $v_1,v_2,...$ such that, for every $i>0$, $v_i$ is adjacent to $v_{i-1}$. The last player capable of choosing a ...
57 views

127 views

Reduce Hamiltonian Path Decision Problem To Hamiltonian Cycle Decision Problem

Person A requires that he determine whether or not a particular graph G = (V,E) has a Hamiltonian path from vertex a to vertex b. His colleague Person B has implemented a function that takes an ...
15 views

Proof of equivalence of S-TSP solution with TSP solution (metric instances)

I am wondering where could I find proof for following S-TSP to TSP transformation. S-TSP (Steiner Travelling Salesman Problem) def: Let $G=(V, E)$ be a non-directed weighted graph. Let $V' \subset V$ ...
29 views

Graph which is Bipartite, has an Euler circuit, but not a Hamiltonian circuit

Is there a graph which is bipartite, has an Euler circuit, but not a Hamiltonian circuit? I know the answer is yes, but if you consider something like this: I don't think this would be bipartite, ...
48 views

Prove that the connected circulant regular graphs of degree at least three contain all even cycles.

This is the question I am trying to solve, but while researching about circulant graph I came across Paley's graph of order 13. Now clearly when looking at this graph which is an example of circulant ...
46 views

Hamiltonian circuit

Prove that a graph that posses a Hamiltonian circuit must have no pendant vertices. To prove this, each vertex in a graph, that also has a hamiltonian circuit, much acquire at least two edges in ...
25 views

Hamiltonian paths and cycles of rook graph on $n\times2$ chessboard

According to OEIS, there are closed form for directed Hamiltonian paths (A096121) and Hamiltonian cycles (A276356) of rook graph on $n\times2$ chessboard. Are there papers which include proof of those ...