Questions tagged [hamiltonian-path]
A path in a graph that visits each vertex exactly once.
-2
votes
0answers
12 views
Hamiltonian Path Detection explanation
i want to understand those words : "a sufficient condition, which states that for a graph G, if the degree sum of all pairwise nonadjacent vertex-triples is greater than (1/2)*(3n−5), then G has a ...
0
votes
2answers
23 views
Why is hamiltonian path reduction to cycle wrong
Wikipedia link states that you are able to reduce HP to HC by adding a single vertex that is connected with all the edges. I understand the reason why the reduction from cycle to path works by adding ...
1
vote
0answers
8 views
Hamiltonian paths in cubic graphs with cyclically edge connectivity at least 5
Definitions A cubic graph (simple) $G$ is a 3-regular graph. An edge cut $K$ is cycle separating if $G-K$ is disconnected and at least two components of $G-K$ have circuits. A graph is cyclically ...
5
votes
0answers
31 views
NP-Complete proof of deciding if a graph has another Hamiltonian Circuit
I need to prove as an exercise that the following problem is NP-Complete:
Given a graph and an already existing Hamiltonian Circuit in that graph, decide if the graph has another Hamiltonian Circuit
...
2
votes
1answer
29 views
$G$ contains Hamiltonian circuit $\Leftrightarrow G + uv$ contains Hamiltonian circuit
We have graph $G$ and two not connected vertexes $u,v$ where
$$ \deg(u)+\deg(v) \ge n $$
Prove that $G$ contains Hamiltonian circuit $\Leftrightarrow G + uv$ contains Hamiltonian circuit
My ...
0
votes
0answers
18 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
1answer
38 views
How do we know that the prime sum graph defined in this paper has a perfect matching?
https://arxiv.org/pdf/1804.07104.pdf
I am reading this paper and trying to understand why Theorem 1.1 guarantees a perfect matching for the prime sum graph as stated at the bottom of page 2. Can ...
0
votes
0answers
11 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
24 views
Traveling sales man with alternating groups of destinations.
I am looking for an algorithm to determine the best route where the groups of destinations alternate.
For example: I have three stores and three warehouses. So I would like to visit a warehouse first,...
5
votes
2answers
215 views
Playing Doublets with the Primes
Lewis Carroll's famous game of Doublets is well known. In it you are asked to transform a given word into another by changing only one letter at a time, forming a genuine new word (not a proper name) ...
1
vote
1answer
35 views
Determine if a Hamiltonian Cycle exists?
Suppose I have a graph $G=(V, E)$. Removing a subset $R$ of edges from $G$ results in a new graph $G^\prime=(V, E\setminus R)$. The maximum number of edges in $R$ is $|E|$. Suppose I have the graph $G^...
1
vote
0answers
34 views
How to show that there exists a tournament of size n with a certain number of Hamiltonian paths? [duplicate]
Assuming a tournament of size $n$ is a choice of orientation for each edge of
$K_n$, show that there exists a tournament of size $n$ with at least $\dfrac{n!}{2^{n-1}}$
Hamiltonian paths.
This ...
0
votes
1answer
23 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 ...
1
vote
1answer
45 views
Proof that if graph has $\frac{(n-1)(n-2)}{2} + 2$ edged then contains hamiltonian cycle
Proof that if graph has $\frac{(n-1)(n-2)}{2} + 2$ edged then contains hamiltonian cycle
I think that it is good to use there induction:
Let check base of induction. For $ n= 3 $ I have
$$ |E| = \...
1
vote
0answers
22 views
Chance of not finding an alternating Hamiltonian path in a colored graph in $n$ random walks
Introduction
Given a random graph which can be constructed as follows:
generate $s$ pairs of unconnected black edges and $2 \cdot s$ vertices
connect these black edges using red edges, where the ...
0
votes
1answer
23 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$ $(...
1
vote
1answer
29 views
Finite Graph With Degree $\geq 2$
Show that a finite graph with all vertices with degree $\geq 2$ has a cycle that contains a vertex which is non-adjacent to any other vertices not contained in the cycle.
I tried to start at an ...
0
votes
0answers
32 views
Hamiltonian Cycle with n vertex graph
Let a n-vertex graph such that every pair of not adjacent vertices a & b has degree(x) + degree(y) $\geq$ n. Show the graph contains a Hamiltonian cycle.
By dirac's thm, a simple graph with n ...
0
votes
0answers
94 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
14 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
33 views
Are Euler trails and tours of a graph the same as Hamilton paths and cycles of the corresponding “edge graph”?
Is knowing information about Euler paths and Euler tours about a graph $G$ the same as knowing information about Hamilton paths and cycles of the graph $H$ obtained from $G$ such that vertices of $H$ ...
3
votes
1answer
115 views
How to calculate quantity of Hamilton cycles
If I have $n^2$ vertices and each vertex is adjacent to $2n-2$ vertices, how may I calculate the quantity of possible Hamilton cycles?
Would I need to modify the computation if I stipulated that I'm ...
0
votes
1answer
23 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
34 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 ...
1
vote
1answer
73 views
How to convert a maximal planar graph to a regular planar multigraph?
Given a maximal planar graph (coming from the convex hull of a set of points on a sphere), I want to add edges until it is regular (all vertices touch the same number of edges), while keeping it ...
0
votes
3answers
15 views
Would removing the max weighted edge from a Hamiltonian circuit result in a Hamiltonian path?
If I have a Hamiltonian circuit, assuming that cutting the max weighted edge resulted in a Hamiltonian path.
Is it guaranteed that the path would be minimal too?
1
vote
2answers
191 views
Show that the line graph of any quasi-cyclic graph contains a Hamiltonian cycle.
The definition I have been given for a quasi-cyclic graph is as follows: a graph $G=(V, E)$ is quasi-cyclic if $1)$ it contains a unique cycle $C=(V(C), E(C))$ and $2)$ for each edge $xy$ in $E$ at ...
0
votes
1answer
30 views
Finding number of two cycle multi-graphs [closed]
Consider directed graphs on n labelled vertices {1,2,...n}, where each vertex has exactly one edge coming in and exactly one edge going out. We allow self-loops. How many such graphs have exactly two ...
2
votes
1answer
52 views
Number of Hamiltonian cycles in a random graph
I want to show that $\mu_{n}(p)$, the expected number of Hamiltonian cycles in the random graph $G(n,p)$, is given by
$$\mu_{n}(p)=\frac{1}{2}(n-1)!p^{n}$$
We can easily show that the number of the ...
1
vote
1answer
36 views
Limiting behavior of the expected number of Hamiltonian cycles in the random graph $G(n, p)$.
So we have that the expected number of Hamiltonian cycles in the random graph $G(n,p)$ is given by:
$\mu_{n}(p)=\frac{1}{2}(n-1)!p^{n}$ for $n \geq 3$.
We now want to find lim$_{n\to \infty}\mu_{n}(...
1
vote
0answers
25 views
Combinatorial proof of Hamiltonian paths on the rook graph
We can be sure that number of Hamiltonian paths on the rook graph for any single cell on $n\times2$ chessboard equals
$$
H(n+1) = \sum_{k=0}^{n}
\binom{n}{k}
\binom{k}{\lfloor{\...
1
vote
1answer
31 views
What is a vertex-transitive graph? (Question about Lovász Conjecture)
I was reading about Lovász Conjecture and came across the following definition on Wikipedia of a vertex-transitive graph (see below).
$\bullet$ It states that a graph is vertex-transitive if for any ...
0
votes
1answer
32 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
24 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 ...
1
vote
1answer
34 views
Number of different graphs with this degree sequence
The set of degree sequences in question is:
$$ D_1=\{4^4,6^4,4^4\} $$
$$ D_2=\{4^4,6^4,6^4,4^4\} $$
$$ D_3=\{4^4,6^4,6^4,6^4,4^4\} $$
$$ D_4=\{4^4,6^4,6^4,6^4,6^4,4^4\} $$
$$ ... $$
$$ D_N=\{4^4,...
2
votes
0answers
12 views
Path / Graph problem with X nodes looking for Y paths with the most similar length.
I have the following graph / path problem:
There is exactly 1 start node and 1 end node.
There are also X (in this case 7) nodes, each connected to all other nodes and the start and end node with ...
1
vote
1answer
20 views
Graph Problem: find X path lengths which are closest to each other (similar to shortest path)
I have the following problem:
1 Start point
1 End point
7 Knots / waypoints which you have to visit in any order
All 9 knots are connected with each other.
All paths have to start at the start point ...
0
votes
0answers
41 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 ...
2
votes
1answer
38 views
What is the term for a graph in which each edge belongs to a Hamiltonian cycle?
Furthermore, are they any known results about these graphs, such as necessary or sufficient conditions for a graph to have this property?
0
votes
2answers
77 views
About the proof of a graph is not Hamiltonian.
Given the following graph:
https://i.stack.imgur.com/fg2Q9.png
Is this graph Hamiltonian or not?
The answer is no. What I tried to prove is by using the fact that: "if a vertex in the graph has ...
1
vote
1answer
55 views
Show that if $|G| \geq 5$ and for each pair of vertices $u,v$ there is an $u−v$ Hamilton path then $\kappa(G) \geq 3$
Show that if $G$ is a graph with $|G| \geq 5$ such that for each pair of vertices $u,v$ there is an $u−v$ Hamilton path in $G$, then $\kappa(G) \geq 3$
I do not really have any idea how to start this ...
2
votes
2answers
79 views
Prove that if a graph $G$ has a Hamilton path, then for every $S\subseteq V(G)$, the number of components of $G-S$ is at most $|S|+1$.
Prove that if a graph $G$ has a Hamilton path, then for every $S\subseteq V(G)$, the number of components of $G-S$ is at most $|S|+1$.
My solution (rough and incorrect): Consider a Hamilton path $P$ ...
2
votes
0answers
22 views
Number of open and closed rook's tours
Knight's tour is very well known problem, but what about rook's tour? On $n\times1$ chessboard there are obviously $n!$ open and $(n-1)!$ closed tours.
Is there a way to easily compute number of open ...
1
vote
0answers
32 views
Hamiltonian paths in graph
I have a theorem about Hamiltonian paths in graph, but I doubt it's possible.
Theorem If vertex $v$ of graph $G$ is not isolated, and degree of every other vertex is $\geq k$ for $k \geq 2$, and $|V| ...
0
votes
1answer
104 views
Every self-complementary graph contains a Hamiltonian path.
How to show that every self-complementary graph is traceable (contains a Hamiltonian path)?
Definitions:
Self-complementary graph
Hamiltonian-Path
Traceable Graph
0
votes
1answer
35 views
Diameter of a graph such that given independent vertices u, v, d(u) + d(v) ≥ n.
given my continuous struggle with proofs on graph theory, I come with another problem I do not know how to approach.
Given a graph G = (V, E) such that for any two non-neighboring vertices
u, v ∈ V ,...
2
votes
0answers
64 views
Is this graph Hamiltonian and how to prove it is not? [closed]
How to prove this graph is not Hamiltonian (does not contain a Hamiltonian cycle)?
I have already tried removing some vertices from the graph, but I cannot get more than 7 connected components after ...
0
votes
0answers
19 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 $...
8
votes
1answer
209 views
All 4-connected planar graphs are Hamiltonian-connected
I started reading Thomassen's paper A Theorem on Paths in Planar Graphs, where he proves one of Plummer's conjectures: Every $4$-connected planar graph is Hamiltonian-connected.
Context. Recall that ...
0
votes
1answer
43 views
Hamilton Paths in Complete graph $K_n$
In complete graph $K_n$, is it true that we can have at least $2*n$ Hamilton paths?
