Questions tagged [hamiltonian-path]

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

Filter by
Sorted by
Tagged with
-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 ...
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. }...
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 ...
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 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 ...
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 ...
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 ...
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$. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ? ...
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 ...
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 ...
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 ...
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

1
2 3 4 5
13