Questions tagged [hamiltonian-path]
A path in a graph that visits each vertex exactly once.
587
questions
-1
votes
1
answer
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
0
votes
0
answers
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
0
votes
0
answers
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
0
answers
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
0
votes
0
answers
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 ...
- 253
0
votes
0
answers
40
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!}...
0
votes
0
answers
18
views
Path Lengths and Random Walk - Generalization of the Uncut Spaghetti Game
The following is a kind of generalization of the interesting Uncut Spaghetti game (https://mathpickle.com/project/uncut-spaghetti-number-patterns/):
Consider a 2D integer lattice where each point has ...
- 541
2
votes
0
answers
36
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 ...
- 479
0
votes
0
answers
29
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$ ?
...
- 673
1
vote
0
answers
30
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 ...
- 121
1
vote
1
answer
79
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
154
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
59
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
112
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
156
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 ...
0
votes
0
answers
29
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
105
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 ...
- 331
1
vote
1
answer
355
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 ...
- 155
2
votes
1
answer
41
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.
- 85
0
votes
1
answer
28
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 ...
- 85
0
votes
1
answer
106
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
19
votes
0
answers
277
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 ...
- 191
0
votes
0
answers
50
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 ...
- 377
6
votes
1
answer
102
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
52
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
121
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 ...
- 454
2
votes
1
answer
44
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)...
- 70.1k
0
votes
0
answers
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 ...
- 15
1
vote
0
answers
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 ...
- 11
0
votes
0
answers
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
2
votes
1
answer
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
0
votes
0
answers
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
0
answers
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
0
votes
0
answers
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'...
0
votes
0
answers
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
0
votes
1
answer
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.
0
votes
1
answer
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, ...
0
votes
0
answers
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 ...
- 11
2
votes
3
answers
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
1
answer
58
views
A multigraph $G$ has even no of Hamiltonian paths
Following Corollary is taken from : HAMILTONIAN CYCLES AND UNIQUELY EDGE COLOURABLE GRAPHS
Definition (Stick) : A path $s= e_1,...,e_m$ in $G$,where the end vertices of the edge $e_i$ are $v_i$ and $...
- 189
0
votes
0
answers
54
views
How Many Paths Go From Point A to B Such That Every Space is Passed Through Once
Given the following grid where it is only possible to move between squares that share an edge, how many paths are there that visit every single square exactly once?
From what I can think of, I know ...
0
votes
1
answer
35
views
Prove that $\Delta(G)\le \frac{n-1}{2}$
I have to prove that if graph $G$ is not Hamiltonian, but $G-v$ is Hamiltonian for every $v\in V(G)$ then $\Delta(G)\le \frac{n-1}{2}$. I tried to prove this with contradiction. So, first if we assume ...
- 503
0
votes
0
answers
31
views
Show that if either N is even and M > 1 or M is even and N > 1, then the N × M grid is Hamiltonian. [duplicate]
The grid in question is undirected.
The length of the Hamiltonian cycle should be even which should be possible in this grid since any N × M grid is bipartite. Besides this, I am not able to grasp any ...
- 45
4
votes
1
answer
184
views
Is there an algorithm giving the shortest path visiting all nodes in a directed weighted graph?
I am looking for an algorithm mentioned in the title. The graph is complete, i.e. every two nodes have two edges in between with different directions.
I tried Traveling salesman method, but it gives a ...
- 195
4
votes
1
answer
54
views
Is there a specific name for this necessary condition of Hamiltonian graphs?
My professor told me that almost every graph theory textbook lists the following as a necessary condition for a graph to be Hamiltonian:
Let G be a graph. Every subset S of vertices of G has the ...
- 53
0
votes
0
answers
17
views
how to calculate the period of Hamiltonian from its eigenvalues
I want to calculat the period of Hamiltonian by using its eigenvalues.
I have the Hamiltonian,
\begin{align*}
%\[
H=
\begin{bmatrix}
\lambda_1 & 0 & 0\\
0 & \lambda_2 & 0 \\
0 & 0 &...
- 9
2
votes
1
answer
204
views
Count Hamiltonian Cycles in directed torus graph
Here we define "torus graph" to be a directed graph with vertex set $V=\mathbb Z_n\times\mathbb Z_m$ and edge set $$E=\{(x,y)\to(x+1,y)\mid(x,y)\in V\}\\\cup\{(x,y)\to(x,y+1)\mid(x,y)\in V\}$...
- 153
0
votes
0
answers
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 ...
- 9
0
votes
1
answer
78
views
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 ...
- 133
3
votes
3
answers
203
views
Difficulty in understanding the proof of Petersen Graph is non hamiltonian as given in graph theory text by Chartrand and Zhang
I was going through the text : A First Course in Graph Theory by Chartrand and Zhang where I could not understand a few statements in the proof. Below is the excerpt:
Theorem 6.4 : Petersen graph is ...
- 727