Questions tagged [hamiltonian-path]
A path in a graph that visits each vertex exactly once.
496
questions
1
vote
1answer
27 views
Is there a technique to find a hamilton circuit in a graph?
My textbook goes in depth about how to show that a graph does NOT have a hamilton circuit, but one of its practice problems asks you to find a hamilton circuit in a graph that does have a hamilton ...
0
votes
0answers
32 views
Hamiltonian path, how to speed up?
Given an undirected graph with N nodes, each node has at most sqrt(2*N) edges.
I have ...
5
votes
1answer
49 views
Uniqueness of hamiltonian cycle
Let G be a graph on $n$ vertices, where $n \geq 8$ and with minimum degree at least $n/2$. Does $G$ have at least 2 distinct Hamilton cycles? (Two Hamilton cycles are said to be distinct if they ...
2
votes
1answer
59 views
That every 5-vertex path in the dodecahedron lies in a Hamiltonian cycle?
In this problem ,it occurred to me that erasing the vertices that are between the trajectory, it only remains to show that there is a Hamiltonian path from the first to the last vertex of the ...
2
votes
3answers
71 views
What is the difference between a Hamiltonian Path and a Hamiltonian Cycle?
The title says it all. I've seen confusing definitions of this, and would appreciate if someone can succinctly clear this up with definitions and examples.
0
votes
1answer
57 views
Why are there $40$ paths in a $3\times 3$ grid?
If I have a thread of length $4$ that I want to lay on a $2\times 2$, there are $8$ ways to do it, apparently. That because from every node I can go clockwise or counter clockwise, right?
But ...
0
votes
1answer
40 views
Karp reduction from HC to HP. What am I doing wrong?
I know there is this solution for Karp reduction from HC to HP in here (INDIRECTED graph).
But I was thinking about something else, and would like to know what you think about it.
I create 2 new ...
1
vote
0answers
32 views
Does every $r$-regular, $r$-edge-connected, bipartite graph contain a Hamiltonian path?
The following question is similar to another I recently asked, however, it restricts the graph class further by requiring regularity and edge-connectedness to be equal.
Given a $r$-regular, $r$-edge-...
4
votes
1answer
78 views
Does every regular, bipartite graph contain a Hamiltonian path?
This may be a rather straight-forward question; however, I am unable to arrive at an answer myself.
Given a $r$-regular, $k$-edge-connected, bipartite graph, will there always be a Hamiltonian path in ...
1
vote
0answers
21 views
Add smaller Hamiltonian circuits to make bigger one
Is it always possible to generate a Hamiltonian circuit by adding smaller ones?
For example, a 8x8 grid can be split into four 4x4 grids, each having a Hamiltonian circuit. In this case, it is ...
0
votes
0answers
34 views
Prove that in a full oriented connected graph there is a cycle passing through all the vertices [duplicate]
Prove that in a full oriented connected graph there is a cycle passing through all the vertices.
I tried to find contradictory example.But there are not any contridictions. I tried also to put ...
0
votes
1answer
38 views
Proof checking: Graph Theory
Question: Prove that if the number of vertices in graph $G$ is $n \geq 2$ and the sum of $2$ degrees is at least $n - 2$, then graph $G$ has $2$ disjoint simple paths that their union completes the ...
1
vote
1answer
48 views
Graph Theory: Question about union of 2 Paths
Q: Prove that if a graph $G$ has $n \geq 2$ vertices, and the sum of the degrees of 2 different vertices is at least $n-2$ (for any 2 different vertices), then the graph has 2 disjoint simple paths, ...
0
votes
1answer
36 views
Graph theory: Questions about Hamiltonian cycles.
Prove that if graph $G$ has $ n \geq 2$ vertices such that the sum of the degrees of $2$ different vertices is at least $ n- 2$, so there are $2$ different simple paths ('foreign' to one another) such ...
0
votes
1answer
17 views
Prove: if G has a closed hamilton walk then L(G) has one too.
L(G): L Line Graph If G is a graph with e ā 0 then the line graph of G, denoted āL(G)ā, is the graph having one vertex corresponding to each edge of G and such that two vertices of L(G) are joined by ...
1
vote
0answers
32 views
Prove that de-bruijn graph has Hamiltonian cycle?
Let $G_{2,n}$ be a de-bruijn graph.
We remove the vertex 11...11 and the vertex 00...00 and all edges connected to them.
Q: ...
1
vote
1answer
37 views
Hamiltonian path between two specific nodes
We have a simple undirected connected graph G and two specific nodes s and t. We delete a node and gets to a graph G' that it has a hamiltonian path between s and t.
What necessary conditions has to ...
0
votes
0answers
27 views
Can a disjoint union of two sets be a connected graph?
Can A ā B, where |A| ā |B|, be a complete graph? There is a lemma about Hamiltonian cycles which states:
If G = (A ā B| E) is a bipartite graph, |A| ā |B|, then there is no Hamiltonian cycle in G.
...
1
vote
1answer
34 views
How to show the following cubic graph is Hamiltonian?
Suppose we have a complete graph $K_{2n}$, where $n$ is an integer, and we number vertices counterclockwise as $1,2,\cdots,2n.$ Then we give weight to the edge connecting $u,v$ as $|u-v|$.
Now, ...
1
vote
1answer
43 views
How to decompose edges of $K_n$ into Hamiltonian paths?
Let $K_n$ be a complete graph with n vertices, where n is even
Show that $K_n$ can be decomposed into $\frac{(n-1)}{2}$ disjointed Hamiltonian paths on edges
My idea was to use Menger's theorem ...
2
votes
1answer
26 views
Can a Hamiltonian cycle of an undirected Cayley graph contain inverses of the generating elements?
Let $G$ be a finite group and $S$ be a subset of $G$. Let us define the Cayley graph of $G$ with respect to $S$ as follows, provided that $1 {\not\in} S$ and $S$ is inverse closed.
Definition:
The ...
1
vote
1answer
32 views
On the Condition for Hamiltonian Graph
In the Graph Theory lecture, I took an exercise as follows: For $\emptyset \neq S \subseteq V(G)$, let $t(S) = \lvert\overline{S} \cap N(S) \rvert / \lvert \overline{S} \rvert$. Let $\theta(G) = \min ...
2
votes
0answers
60 views
Factorization in Hamiltonian graphs [duplicate]
Show that for any integer $n \geq 0$, the complete graph with $2n + 1$ vertices can be $2$āfactorable into $n$ Hamiltonian cycles
A graph $G$ is 2-factorable if and only if it is 2r-regular for some ...
5
votes
1answer
119 views
How does Grinberg's theorem work?
Grinberg's theorem is a condition used to prove the existence of an Hamilton cycle on a planar graph. It is formulated in this way:
Let $G$ be a finite planar graph with a Hamiltonian cycle $C$, ...
3
votes
0answers
31 views
Does a longest cycle contain maximum number of each generating element
Let $G$ be a finite group and $S$ be a subset of $G$. We define the Cayley graph of $G$ with respect to $S$ as follows, provided that $1 {\not\in} S$ and $S$ is inverse closed.
Definition:
The Cayley ...
3
votes
1answer
48 views
Showing the square of given graph is not hamiltonian
In the Graph Theory lecture, there is a problem about the power of a graph and a hamiltonian cycle: For a simple graph $G$ and its vertex $x$, suppose that $G-x$ has at least tree non-trivial ...
0
votes
1answer
32 views
Hamiltonian path exists if each two nonadjacent vertices has sum of degrees equal to n-1
Here is a question from a textbook Iām reading,
prove that a simple graph with n vertices has a hamiltonian path if the sum of degree number of each two none adjacent vertices is n-1.
I know
A graph ...
2
votes
1answer
52 views
Are these bipartite graphs Hamiltonian graphs? And do they have a name?
Assume that $n = 2k + 1$, and
$$A = \{ \alpha \in \{\,0,1 \,\}^{n} \mid w(\alpha) = k + 1 \}$$
$$B = \{ \alpha \in \{\,0,1 \,\}^{n} \mid w(\alpha) = k \}$$
where $w(\cdot)$ is the Hamming weight.
...
0
votes
1answer
23 views
Does the single source shortest path always have the shortest edge in the graph? Why or why not? [closed]
*by single source shortest path, I mean the path that is the solution to the traveling salesperson problem
Does it also have the second shortest edge?
Also, what other general properties can be said ...
0
votes
0answers
22 views
if G has a Hamilton cycle, then G also has a Hamilton path.
How can I show that if G has a Hamilton cycle, then G also has a Hamilton path?
From my understanding, I feel like we can show it by removing an edge that is connected from the end to the start of ...
0
votes
2answers
45 views
Why is the complete graph $K_2$ not Hamiltonian?
Why is the complete graph $K_2$ not Hamiltonian?
A graph $G$ is said to be Hamiltonian if there exists a path in $G$ which visits every vertex exactly once.
Also a path is a sequence of vertices and ...
0
votes
1answer
22 views
Is Hamiltonian path solvable in nondeterministic log space?
Is Hamiltonian path solvable in nondeterministic log space?
Vertices are notated in base 2
Keep two counters
First counter is current vertex
Second counter implies max vertex encountered in ...
5
votes
0answers
30 views
Properties of prime sum graphs
The prime sum graph $P_n$ on the vertex set $V(P_n) = \{1,\dots, n\}$ has an edge $e = xy$ when $x+y$ is prime. It is easy to show that any such $P_n$ is bipartite (put odd numbers in one part and ...
2
votes
2answers
36 views
Is there a formal name of the “Hamiltonian property” of a node-weighted graphļ¼
Given a node-weighted graph $G = (V,E)$ with weight $w \colon V \to \mathbb{N}^{*}$.
The "Hamiltonian property" of $G$: There exists a cycle (path) $c$ that traverses the vertex $v_{i}$ exactly $w(v_{...
0
votes
1answer
19 views
What does C(n - 1, 2) edges mean in graph theory?
My graph theory book postulates the if a simple graph with n vertices has at least C(n - 1, 2) + 2 edges then the graph must be Hamiltonian.
This is probably true ...
2
votes
0answers
25 views
Hamiltonian path after removing a node
We have an undirected connected graph $G$ with a hamiltonian path between nodes $a$ and $b$, if we remove a node that this removing doesn't blemish the connectivity ($G$ is still connected and the ...
0
votes
0answers
24 views
Relationship between the generating elements given by the Hamiltonian cycle of a Cayley graph
Consider the Cayley graph of $\mathbb{Z}_3 \times \mathbb{Z}_5$ generated by the generating set $S=\{g_1=(1,0), g_2=(0,1)\}$. Then $|g_1|=3, |g_2|=5$.
Consider a Hamiltonian cycle, $ABCDEFGHIKJLMNO$. ...
1
vote
1answer
22 views
Is Hamiltonian path NL?
NL is what can be solved by a non-deterministic Turing machine in logspace.
Could you non-deterministically "guess" the correct Hamiltonian path in logspace, keeping track of the current vertex (log(...
0
votes
1answer
34 views
Why there's no hamiltonian cycle for a grid where $m$ and $n$ are odd?
I have read some of the discussions about the topic but while I understand that a grid $n$ x $m$ with $n$ or $m$ even ($n,m>1$) has always an hamiltonian cycle I don't get the reasoning behind the ...
0
votes
0answers
21 views
Can a bipartite graph not contain a Hamiltonian cycle?
Statement: any bipartite graph contains a Hamiltonian cycle.
My answer: No. A bipartite graph which have an odd number of vertices cannot contain a Hamiltonian cycle, since each simple cycle in a ...
4
votes
1answer
61 views
How to not find a Hamiltonian Cycle
Consider the following naive algorithm for finding Hamiltonian cycles on a simple undirected graph G with n vertices:
Choose an arbitrary vertex and mark it as vertex 1
Choose an arbitrary unmarked ...
0
votes
1answer
35 views
Is a directed complete graph Hamiltonian? (if there are no sink groups)
For some graph G that is complete (Kn) and directed (every edge ab can be traversed in only one way, either a -> b, or b -> a) and has no sink groups. Is G necessarily Hamiltonian? If so why?
Define ...
0
votes
1answer
60 views
Is there a cycle-free graph with a Hamiltonian circuit?
I have an question about graphs. Is there any graph in which there is no cycle, but it has a Hamiltonian circuit? I think there isn't such a graph.
Am I right?
Thanks for your answer in advance.
-1
votes
1answer
70 views
How many simple graphs (up to isomorphism) have 6 vertices and 8 edges and admit a Hamiltonian circuit
How many simple graphs (up to isomorphism) have 6 vertices and 8 edges and admit a Hamiltonian circuit?
Apparently the answer is 6, but how would you prove this?
0
votes
1answer
76 views
Let $G$ be connected graph $rā$regular, show that if $G$ complement is connected but is not Hamiltonian. Then $G$ is Hamiltonian
I've been stuck in this homewoork problem, and I've already asked my teacher and he told me that I have the idea by contradiction using Ore's Theorem and by watching $r$.
But I got some issues ...
1
vote
1answer
68 views
Probability that a sequence corresponds to a cycle in a graph
Suppose the random undirected graph $G$ is constructed as follows. $G$ starts off as $n$ distinct vertices, where $n$ is even. Independently for each of the possible pair of vertices, we add an ...
1
vote
1answer
33 views
Is it true that any hamilton graph with “k” vertices has k/2 as the maximum independent set?
A Hamilton graph is a graph that has a Hamiltonian cycle ,which means a cycle exists in this graph in which you can visit every vertex of graph exactly once .
My observation is : - Say for a(any) ...
1
vote
0answers
30 views
Find a hamiltonian path in $T^{3}$
The cube of a graph $T$, denoted $T^{3}$, is the supergraph of $T$ such that the edge $(u, v)$ is in $T^{3}$ if and only if there is a path between $u$ and $v$ in $T$ with three or fewer edges.
My ...
0
votes
1answer
51 views
Shortest Path Passing Through All Points When Start and End Points are Given
Assume we have a set of points $\{A,B,C,\dots,Z\}$ in a plane.
What is the shortest path which includes all points once, starts at $A$ and ends in $Z$ and $A \ne Z$
I am trying to identify if this ...
0
votes
0answers
15 views
What is the Mathematical Terminology for Gaussian Paths
I am looking for the terminology for the path object that is Gaussian in nature, in other-words the path has a mean along it direction and variance in perpendicular direction as illustrated by the ...
