Questions tagged [hamiltonian-path]

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

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

1
2 3 4 5
10