Questions tagged [hamiltonian-path]
A path in a graph that visits each vertex exactly once.
414
questions
0
votes
1answer
34 views
Graph theory: decompositions and Hamiltonian graph
13 people who are not superstitious wish to have dinner together at a round table for a few nights so that each person has different neighbours every night. For how many nights can they do this?
...
1
vote
1answer
50 views
Show that undirected connected 3-regular graph with 8 vertices has Hamiltonian path
Let be $G=\langle V,E\rangle$ undirected and connected 3-regular graph with 8 vertices. Prove that $G$ has Hamiltonian path.
I am trying to prove the above claim, however I don`t know how to develop ...
3
votes
2answers
51 views
Hamiltonian path in $S_n$?
Say $S_n$ is the symmetric group. Define a graph $G$ by $G=(S_n,E)$, where there is an edge from $\sigma_1$ to $\sigma_2$ if and only if $\sigma_2=t\sigma_1$ for some transposition $t$.
Is there a ...
1
vote
1answer
42 views
Show that $G$ is not Hamiltonian.
Suppose that $G$ is a graph with $pq$ vertices where $p$ and $q$ are primes and $2<p<q$.
If $(p-1)(q-1)$ vertices of $G$ have degree $p+q-1$ and all other vertices have degree $pq-1$, show ...
1
vote
0answers
49 views
Algorithm to construct $k$ edge-disjoint Hamiltonian cycles
Consider an undirected graph $G=(V,E)$, where $V=\{1,2,\ldots, n\}$, and initially $E=\varnothing$. Now take the following steps:
In the $1$st round, add undirected edges $(1,2)$, $(2,3)$, $\ldots$, $...
1
vote
0answers
39 views
Hamilton cycle problem on group's Cayley graph. Determining a function $G^n \to \Bbb{Z}[G]$.
Let $G$ be a finite group and $G^n$ be the direct product of $n$ copies of $G$. Let $f_g: G^n \to \Bbb{Z}, \forall \ g\in G$ be such that there exists at least one $x \in G^n$ such that $f_g(x) = 1, \...
2
votes
1answer
34 views
A Hamiltonian cycle generated by lame rooks moves
I have got this problem at high-school math-contest seminar on Graph Theory
Let us have a chessboard, where one black and one white lame rooks stand. Lame rook can move to edge-adjacent field only. ...
1
vote
1answer
25 views
Hamilton Cycle Proof Verification
Explain why there is no Hamilton cycle in the graph attached below. Then, show that if any pair of non-adjacent vertices in the same graph are joined by an edge, then the resulting graph has a ...
3
votes
1answer
57 views
$n^{th}$ Dimensional Prime Nexus Conjecture (Hamilton's Path & Cycle)
The system and proposition of Prime Nexus -
We have to arrange $n>1$ Distinct natural numbers in a sequence such that the adjacent elements sums upto any Prime number. Convenience is when we set ...
1
vote
1answer
36 views
Travelling salesman problem visiting different nodes different times [closed]
Hi I am trying to solve a more complicated travelling salesman problem (shortest path visiting all nodes in a directed graph), where
(1) I need to revisit different nodes for different times,
(2) I ...
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):
...
2
votes
2answers
69 views
Define A Graph - Tree Graph With “Cycles” as Nodes
I am working on my thesis and I would like to have a proper definition for this type of graph:
"Tree Graph With Nodes As Cycles"
I would like to define a graph similar to a "simple tree", but some of ...
2
votes
1answer
50 views
Existence of Hamiltonian Path using minimum and maximum degrees
In a simple graph $G$ with $n$ nodes, let $c<\deg(V)<C \space \forall$ nodes $V$, for given constants $c<C<{n}$. Let the total number of edges in $G$ be $E$. What is the maximum value of $...
1
vote
0answers
40 views
Efficient hamiltonian path through neighboring squares
My knowledge of Number/Graph theory is very limited. I'm sorry if someone can find this answer posted elsewhere quickly, I spent some time searching but don't know enough to know what to search.
The ...
1
vote
0answers
45 views
Symmetric difference of Hamilton circuits in planar cubic graphs
The answer to math.stackexchange.com/questions/3235317/every-cubic-3-connected-hamiltonain-graph-has-three-hamiltonian-cycles-with-spec?rq=1 points out that the cube graph contains no three Hamilton ...
1
vote
1answer
38 views
double tours embedding of nonhamiltonian bicubic graphs
Can Georges Graph
(or any other nonhamiltonian bicubic graph ) be embedded on an oriented surface of genus -2, i.e. a double torus?
If it helps, it would have $F=E+\chi-V=75-2-50=23$ faces...
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 (...
-1
votes
1answer
36 views
Hamilton path reduction to Hamilton cycle
HAMILTON PATH: given a directed graph $G$ and $2$ nodes start and end does there exist a hamilton path from start to end?
HAMILTON CYCLE: given a directed graph $G$ and $1$ node start, does there ...
8
votes
1answer
211 views
Does knowing a graph has a Hamiltonian Cycle make it easier to find the cycle?
Given a simple and connected graph $G=(V, E)$. I know it's NP-Complete to determine if $G$ has a Hamiltonian Cycle (HC). But if we know $G$ indeed contains an HC, can we find the cycle in poly-time?
0
votes
2answers
40 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 ...
2
votes
0answers
9 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
44 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
40 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
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
1answer
41 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
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
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
228 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
42 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
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 ...
1
vote
1answer
57 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
23 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
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$ $(...
1
vote
1answer
30 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 ...
1
vote
1answer
45 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
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
37 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
122 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
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 ...
1
vote
1answer
79 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
16 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
197 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
63 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
29 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{\...
