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
1
vote
0answers
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,...
1
vote
1answer
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.
1
vote
0answers
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. ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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. ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
57 views

What is the probability of no cycles length $n$ in a simple, directed Erdos-Renyi graph with $n$ vertices?

What is the probability of having no cycles with length $n$ (touching all vertices) in a simple, directed Erdos-Renyi graph with $n$ vertices? For example, if $n=2$, then the probability is $1-P(...
1
vote
1answer
2k views

The number of Hamiltonian cycles in the complete bipartite graph

I know that in the complete bipartite graph $K_{n,n}$ , there is $\frac{n!(n-1)!}{2}$ or $n!(n-1)!$ Hamilton cycles. wiki says first, wolfram says the second one. I know that there is $2n$ ways to ...
1
vote
0answers
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 ...
1
vote
1answer
206 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 ...
1
vote
0answers
24 views

Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that

Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that $$c(\tau(a),\tau(1))+\sum_{i=1}^{a-1} c(\tau(i),\tau(i+1))\leq b $$ Prove ...
1
vote
2answers
645 views

Hamiltonian path in a complement of a tree

T is a tree on n-vertices for which the greatest degree is smaller than n-1, prove that the complement of T has a Hamiltonian path. I was trying to achieve Ore's inequality, this is what I have ...
1
vote
0answers
57 views

Least number $k$ , such there is no graph with $n$ nodes and $k$ hamilton-cycles

Let $f(n):=$min{ $ k \in N$: There is no graph with $n$ nodes and $k$ hamilton-cycles} for $n\ge 3$ The values I found out so far : $$f(3)=2$$ $$f(4)=2$$ $$f(5)=3$$ $$f(6)=9$$ $$f(7)=13$$ $$f(8)...
1
vote
0answers
173 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 ...
1
vote
0answers
205 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?
1
vote
0answers
435 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 ...
0
votes
1answer
50 views

How to find the number of cycles and set of nodes in each cycle in an undirected, connected and loopless graph?

This question could be repetetive. I tried to look up for some posts, most of them are to check whether a graph contains a cycle or not. Assume there is no multiple edge. My problem is I need to find ...
0
votes
0answers
25 views

Induction Proof On “Tree with Nodes as Cycles” Graph

So I have one question about defining the type of graph I was working on: Define A Graph - Tree Graph With "Cycles" as Nodes A short summary for the graph I would like to define as G=(V,E): ...
0
votes
0answers
37 views

Are Hamilton Cycles Petrie Polygons w.r.t. the Local Orientation?

Consider planar cubic bipartite graphs. The graph has a 3-edge coloring due to the 4-coloring theorem. By that and its planarity the vertices have an induced orientation. Now traverse the graph's (...
0
votes
1answer
48 views

Finding a Hamiltonian Cycle from a perfect matching on a the bipartite graph

A disjoint vertex cycle cover can be found by a perfect matching on the bipartite graph constructed from the original graph (L) and its copy (R) and with L original graph edges replaced by ...
0
votes
0answers
12 views

Determine the minimum number of robot teams

I have completed parts $a$ and $b$, but I am stuck on how to show my work for part $c$. I believe the minimum number of robot teams is $3$, but I'm not sure how I got that answer. How do I start this ...
0
votes
1answer
29 views

Hamiltonian Cycles of a graph

Prove if this statement is true: every graph consisting of two edge-disjoint Hamiltonian paths contains a Hamiltonian cycle. Two edge-disjoint Hamiltonian paths means all vertices can be connected ...
0
votes
1answer
35 views

Short explanation for hamiltonian cycles in $Q_3$

The task is to find the count of hamiltonian cycle in $Q_3$. So I know the answer is $6$, but i don't know why or how to get it. My first attempt was simple: I start from edge $6$, and I have $3$ $(...
0
votes
0answers
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 ...
0
votes
0answers
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$ ...
0
votes
1answer
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, ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
45 views

is it possible to move a knight on a chessboard such that it completes every permissible move exactly once?

a move between two squares is counted as one regardless of the direction. basically, we want to prove that a knight started from any position in a 8*8 chessboard can go to all the possible places in ...
0
votes
0answers
20 views

Hamiltonian cycles and paths in a graph

I want to present you a lemma, that I've almost proved, but i'm stuck at the very end of it. Lemma If vertex $v$ of a graph $G$ is not isolated and degree of every vertex except $v$ is $\geq k$ (for $...
0
votes
0answers
33 views

A Hamilton graph having a Hamilton cycle that traverse an edge more than once.

I was asked to draw a Hamilton graph having a Hamilton cycle that traverse an edge more than once. My first impression of this question was: what? I mean if we are not allowed to visit a vertex more ...
0
votes
1answer
329 views

Number of Hamiltonian cycles in complete graph Kn with constraints

I am currently working on a exercice which aims to count the number of hamiltonian cycles in a complete graph. Since it is a completely new topic to me, I struggle to think about how to solve the ...
0
votes
0answers
43 views

Difference between hamiltonian and pre-hamiltonian path?

What is the difference between a hamiltonian path and a pre-hamiltonian path? Or it is the same? How do I show that a digraph G contains a pre-hamiltonian path?
0
votes
0answers
12 views

Pseudo hamiltonian connected property of a graph

Is there a connection between pseudo hamiltonian connectedness and hamiltonicity of graphs?
0
votes
1answer
141 views

if G does not have vertices of odd degree, then there are disjoints cycles by edges

Show that if G does not have vertices of odd degree, then there are disjoints cycles by edges $C_{1}, C_{2}, C_{3},...C_{m}$ such that $E(G)=E(C_{1}) \cup E(C_{2})\cup ...\cup...\cup E(C_{M})$ I ...
0
votes
0answers
39 views

Euler and Hamilton graphs

i would like to know about this. If it is Euler and Hamilton. As i see because it is $u_0$ unti $u_{19}$ it isn't Euler. Also, it is Hamilton because if we erase the edges we see it. Is this right or ...
0
votes
0answers
30 views

Are there any software or libraries(in some language) which draws all the planar graphs given the number of vertices?

I am working on interrelationships between planar and Hamiltonian graphs and for the purpose I need planar graphs for inspection. Since their number grows asymptotically, I cannot approach it manually....
0
votes
0answers
128 views

NP-completeness certificate of a Hamiltonian path

A Hamiltonian path is a path in a directed , edge positive valued finite graph which visits every vertex exactly once and returns to the original vertex. This should be a NP-complete problem, but I do ...
0
votes
1answer
300 views

Proof with induction on $n$ so that the complete graph $K_n$ has $(n-1)!$ hamilton cycle for all $n \geq 3$.

I came up with this solution, but I'm not sure if it's right. Could you check if there is something missing? In the Hamilton cycle, every visit to a node is only exactly one time. Base case: $K_n$ ...
0
votes
1answer
84 views

Finding Hamiltonian cycle for $N\times M$ grid where $N$ is even

This is the solution provided for the problem. However when I follow it, I am not getting the correct path. I assumed $N=4$ and $M=3$ and started with $k=0$ and got this path: $$(0, 1) \to (0, 2) \to ...
0
votes
1answer
254 views

constraints to the hamiltonian path: can one tell if a path is hamiltonian by looking at it?

A few days ago, the channel Numberphile released this video on the square-sum problem. The show later released this follow-up video on how they proved that every number from 25 to 91 can have ...
0
votes
1answer
54 views

$K_n$ for odd $n$ $ϵ$ $Z_+$ is a disjoint union (of edges) of collections of Hamiltonian cycles

Show that (the edges) in the complete graph $K_n$ for odd $n$ $ϵ$ $Z_+$ is a disjoint union (of edges) of collections of Hamiltonian cycles. Further, show that (the edges) in the complete graph $K_n$ ...
0
votes
0answers
267 views

Prove that if $T$ is tournament that is not transitive then $T$ has at least three hamiltonian paths.

Prove that if $T$ is tournament that is not transitive then $T$ has at least three hamiltonian paths. Proof: I am not sure how to start this proof. If it is not transitive then I think the tournament ...