Questions tagged [hamiltonian-path]
A path in a graph that visits each vertex exactly once.
601
questions
-2
votes
1
answer
41
views
Why is it true that a connected graph with 500 vertices and 5000 edges does not have a Hamiltonian Cycle? [closed]
Why is it true that a connected graph with 500 vertices and 5000 edges does not have a Hamiltonian Cycle? How are you able to tell? Is this related to some theorem? I know that a Hamiltonian cycle ...
0
votes
1
answer
19
views
Finding path lengths by the power of adjacency matrix of an undirected graph
The same question was asked almost 7 years ago. It turned out to be a matter of terminology in different textbooks between the terms "path" and "walk". While the answers addressed ...
- 103
1
vote
0
answers
33
views
Maximum number of edges in a connected graph without Hamiltonian path
What is the maximum number of edges in a connected graph without Hamiltonian path?
I've searched the Internet on a while, and read the question Maximum number of edges in a non-Hamiltonian graph here,...
1
vote
1
answer
49
views
Hamiltonian paths in same degree graph
Suppose we have a connected graph, and all vertices of this graph have the same even degree.
Is it always true that this graph has a Hamiltonian path?
Furthermore, is it true if the degree $2k$, this ...
- 13
1
vote
1
answer
26
views
A Hamiltonian cycles (plural) problem?
I'll be brief. I have a set of n vertices in a complete weighted graph, some of these vertices can be thought of as power plants and the rest as cities, and I need to find the shortest way to connect ...
3
votes
1
answer
82
views
Proof that $n$ points on a plane cannot be connected with straight lines under a certain angle treshold
I have $n$ points on a two-dimensional coordinate plane. My goal is finding a path that visits every point once, with straight lines interconnection two points. Additionally, the angle of a line ...
- 35
1
vote
1
answer
20
views
$\nexists$ A hamiltonian closed trail $\Rightarrow $ $\exists x_0 \in V(G)$ such that $\textrm{#\{connected components of }G-\{x_0\}\} \geq 3 $
I'm trying to characterize the hamiltonian paths with the following property:
Given $G$ a connected graph and $K(G)$ the number of connected components of $G$ then
$\exists x_0 \in V(G) \textrm{ s.t. }...
- 485
3
votes
2
answers
146
views
Finding "Hamiltonian paths" in fixed-size integer partitions
For $ p_k(n) $, the partitions of $ n $ with exactly $ k $ parts, it's possible to order them such that each adjacent pair of partitions differ only by one, i.e. one can be transposed to the other by ...
- 225
3
votes
1
answer
58
views
Does every $3$-regular bipartite graph have a $4$-cycle?
Is it the case that every Hamiltonian bipartite $3$-regular graph has a $4$-cycle?
My intuition says 'yes', because one can form such a graph by taking a $n$-cycle and adding a matching to it. When ...
- 725
0
votes
1
answer
47
views
What method is used to find the number of Hamiltonian paths of a fan graph in this proof?
Theorem: The fan graph f_n+2 can be decomposed into 4n+2 Hamiltonian paths.
Proof:
Let f_n+2 be the fan graph with vertex set V: {z,v_1,v_2,..,v_n+1,v_n+2}.
Consider the vertex z. We construct a path ...
- 1
1
vote
0
answers
17
views
Does lowest edge weight algorithm works for non-complete graphs? (TSP)
I am not sure if I translated this algorithm's name but it is one of ways to solve TSP.
Algorithm does these steps:
it sorts edges by weights,
it chooses the lowest weight edge such that it will not ...
- 111
1
vote
0
answers
29
views
What is the probability of guessing a Hamiltonian cycle in the following graph
Would you give any hint to solve task?
"What is the probability of guessing a Hamiltonian cycle in the following graph?"
Pic:
https://i.stack.imgur.com/1Z3Qu.png
- 11
0
votes
1
answer
92
views
Travelling Salesman Problem
I am a bit confused with the following: We know that if P = NP then the TSP problem can be solved in polynomial time, whereas if P != NP there is no polynomial time approximation algorithm.
The ...
- 11
5
votes
1
answer
105
views
Length of shortest hamiltonian path in a circle
Let's say I have a circle of radius $r$.
I will place $N$ points inside this circle, and then find the shortest hamiltonian path going through all these points.
Of course, I know that this shortest ...
- 215
0
votes
0
answers
18
views
Asymptotic trajectory to origin implies instability in time reversible systems
I am reading the article "Instability of equilibrium points of some Lagrangian systems" by Freire, Garcia & Tal. And in the abstract it says:
"In this work we show that, if L is a ...
- 69
0
votes
1
answer
35
views
Does the shortest path have the correct order for some Hamiltonian path
Given $G= \langle V,E\rangle$ such that $|V|=n$ and that $G$ have a Hamiltonian path from $v_1$ till $v_n$
Let $v_{l_1},v_{l_2}, \cdots , v_{l_n}$ be the shortest path from $v_1$ till $v_n$ so $v_{...
- 2,856
0
votes
0
answers
23
views
Topological sort in tournament graph to find hamiltonian path
Suppose $G(V,E)$ is a tournament graph with directed edges.
It has $n $ vertices and $\binom{n}{2}$ directed edges.
An edge $uv$ means that $ u $ beat $v $ in the graph.
I proved that the graph has a ...
- 666
1
vote
1
answer
28
views
What kind of graph is this? Hamiltonian by association?
Here is an example of a connected cycle using the edges:
$ABC-BCD-BCE-CDE-BDE-ABE-ACE-ADE-ACD$
Here $ABC$ shares $BC$ with $BCD$, $BCD$ shares $BC$ with $BCE$, ... , $ACD$ shares $AC$ with $ABC$. ...
- 505
0
votes
0
answers
29
views
What does it mean by 'preassigned orientation'?
I want to solve the next exercise of graph theory:
Prove that a transitive tournament contains a Hamilton path with any preassigned orientation
My problem is that I don't understand what the exercise ...
- 325
1
vote
1
answer
38
views
Is a subdivision of a Hamilton Graph, a Hamilton Graph too?
How would I go about showing this? I think the answer is yes, as subdividing a graph doesn't affect the cycles it has: When going from node a to b, a subdivision of 1 will for example simply make you ...
- 11
0
votes
0
answers
154
views
Prove that there is a Hamiltonian path in the complete bipartite graph $K_{m,n}$ if and only if $|n-m| \leq 1$
The main concept of this question has to do with Paths in the Complete Bipartite Graph.
First I have proven that assuming $n \geq m \geq 1$, $K_{m,n}$ has at most $2m+1$ vertices. The main point to ...
- 67
0
votes
0
answers
40
views
Conversion of SDP relaxation of Travelling Salesman Problem (TSP) to standard SDP form
The standard SDP formulation is given as :
\begin{equation}
\begin{aligned}
\min_{X\in H^{n}} \quad& \langle X,M_{0} \rangle\\
\textrm{s.t.} \quad& l_{s} \leq \langle X, M_{s} \rangle \leq ...
2
votes
2
answers
189
views
Prove that if a tournament $T$ contains a cycle, then it contains two Hamiltonian paths
Prove that if a tournament $T$ contains a cycle, then it contains two Hamiltonian paths.
How can I prove that, I thought that since $T$ is a tournament it has a Hamiltonian path $P$, and since an ...
- 21
0
votes
1
answer
418
views
Graph problem about roads built between towns [closed]
There are 10 cities in a country. The Government starts to build direct roads between the cities, but with random access, it can build direct road between two cities even if there is already another ...
- 21
-1
votes
1
answer
104
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 ...
- 89
0
votes
0
answers
15
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
0
votes
0
answers
49
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: ...
- 701
1
vote
0
answers
70
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,272
0
votes
0
answers
25
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 ...
- 263
0
votes
0
answers
42
views
"Partial" factorials
Other than double factorials and triple factorials, what is known about factorials which are missing some of their factors? For example, $1344=2 \times 3 \times 4 \times 7 \times 8$ which is $\frac{8!}...
1
vote
0
answers
41
views
Probabiity of a graph containg hamiltonian cycle with given probabily for and edge between any two vertices.
Consider a non-oriented graph with n vertices: {1 ... n}.
Let $ p \in [0,1]$ is the probability of having an edge between any two vertices.
The probability of having an edge is the same for any two ...
- 489
0
votes
0
answers
47
views
Hamiltonian Cycle and vertex degrees
Assume we have a graph $G=(V,E)$. Denote by $C$ a Hamiltonian cycle in $G$.
Is it true to say that the degree of every vertex in $C$ is $2$, and for every vertex in $C$ its degree on $G$ is also $2$ ?
...
- 627
1
vote
0
answers
31
views
list of unique elements formed by concatenating permutations of initial lists
I already asked the question on StackOverflow, but I thoughted more about the problem, and my question is now not about programming but graph theory.
I would like to combine several lists, the result ...
- 63
1
vote
1
answer
281
views
Prove Herschel graph is nonhamiltonian
Let us denote by $c(G)$ the number of components of graph $G$.
Theory: For a hamiltonain graph we have $c(G-S)\leq|S|$ for any set $S$ of vertices of $G$.
How can I show that Herschel graph is ...
3
votes
1
answer
234
views
Let $T$ be a tournament directed graph (round robin). Prove that there is an odd number of Hamiltonian paths in the graph
Let $T$ be a tournament directed graph (round robin). Prove that there is an odd number of Hamiltonian paths in the graph.
I am aware that this question may be considered a duplicate of this one: The ...
4
votes
1
answer
84
views
Is there a graph with 2-factor that is not hamiltonian?
If a graph $G$ has a 2-factor it means it is a 2-regular subgraph that contains all vertices of $G$. Isn't it a hamiltonian cycle? because it is 2-regular so it is a cycle and it contains all vertices ...
- 576
5
votes
1
answer
192
views
Prove that if $G$ is a graph of order $101$ and $δ(G) = 51$, then every vertex of $G$ lies on a cycle of length $27$
Prove that if $G$ is a graph of order $101$ and $δ(G) = 51$, then every vertex
of $G$ lies on a cycle of length $27$
(Chapter 3 Exercise 16.a Chromatic Graph Theory,Gary Chartrand, Ping Zhang)
...
2
votes
1
answer
1k
views
Simple graph with $G$ with $n$ vertices, satisfying $d(u)+d(v)\ge n-2$ for every two non-adjacent vertices $u,v$, wtih no Hamiltonian path
A simple graph $G$ with $n$ vertices in which the sum of degrees of every two non-adjacent vertices is at least $n-1$ has a Hamiltonian path.
As described here, one can add a new vertex $w$ and ...
- 4,290
0
votes
0
answers
34
views
Can we convert 'possible bipartite' question to 'max flow' question
Ok, I am in dangerous waters :)
I just began looking into popular graph interview questions and came across this classical one
...
- 101
6
votes
2
answers
176
views
Suppose E is a set of non adjacent edges of G and $\delta(G)\ge\frac{n+e}{2}$.Show that there is a Hamiltonian cycle that contains all the edges of E.
Suppose that $E$ is a set of non adjacent edges of graph $G$ that $\delta(G) \ge \frac{n+e}{2}$ where $|E|=e$. Show that there is a Hamiltonian cycle that contains the edges of $E$.
I know that if the ...
- 337
1
vote
1
answer
1k
views
If $deg(u)+deg(v) \ge n-1$ for $u$ and $v$ are non adjacent vertices, then G has Hamiltonian path
Hamiltonian path is a path that contains all of the vertices of the graph. I know that if $deg(u)+deg(v) \ge n$ for every two non adjacent vertices $u$ and $v$ then the graph has Hamiltonian cycle and ...
- 139
2
votes
1
answer
73
views
Every bipartite Eulerian graph is a Hamilton graph
This is a true/false question I'm trying to solve to prepare for my exam. Could someone confirm my answer and help me prove it?
What I think: false, but I can not come up with an example.
- 95
0
votes
1
answer
30
views
Are all 4-regular Hamiltonian graphs Euler graphs?
This is a true/false question I'm trying to solve to prepare for my exam.
Could someone confirm my answer?
What I think:
true, because the graph then has only even degrees and the graph is also ...
- 95
0
votes
1
answer
338
views
Necessary condition for Hamiltonian path
Determining a graph does not contain Hamiltonian path is very difficult. See for example this particular graph.
This sufficient condition for Hamiltonian path found in this link ClickHere does not ...
- 41
22
votes
0
answers
504
views
Proving the number circle internet meme, where sum of each adjacent numbers is a perfect square
I came across this internet meme and one of my friend mentioned that he thinks that such number circle would always exists for any big enough integer. We tried to prove the hypothesis, but could not ...
- 321
0
votes
0
answers
55
views
Is it possible to arrange handshakes in this way?
I am reading Eulerian graphs from this pdf. In page 210, exercise 9.5.7, I am stuck at following problem.
Each of 8 persons in a room has to hand shake with every other person as per the following ...
- 5,041
6
votes
1
answer
503
views
Is there a graph with all vertices having degree 3 or greater that doesn't have a hamiltonian path?
Is there an example of a simple, undirected graph with all vertices having degree 3 or greater that doesn't have a hamiltonian path? I've seen this question appear in the title of this post, but then ...
1
vote
0
answers
69
views
Monotone chromatic index of oriented hypercube
Edge coloring is right if any adjacent edges have different color.
Right edge coloring is monotone if a color of an edge outcoming from vertex $v$, is bigger than the color of any incoming edge into ...
0
votes
1
answer
227
views
Does there exist a tournament with exactly two Hamiltonian paths?
A tournament is a complete directed graph. A Hamiltonian path is a path that crosses each vertex exactly once.
My conjecture is no. I have tried using induction, proof by contradiction, all to no ...
- 981
2
votes
1
answer
74
views
Hamiltonian graphs with high degree and high girth
Given integers $d\ge2$ and $k\ge3$, is there a Hamiltonian (simple) graph $G$ with minimum degree $\delta(G)=d$ and girth $g(G)\ge k$? And if so, what is the minimum number of vertices, call it $N(d,k)...
- 73.7k