Questions tagged [hamiltonian-path]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
16 views

An FPT algorithm for Hamiltonian cycle running parameterized by treewidth

I'm looking for an algorithm that solves the Hamiltonian cycle problem parameterized by treewidth. In particular, I'm curious about such an algorithm running in $tw(G)^{O(tw(G))}⋅n$ time. But I can't ...
0
votes
0answers
15 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 ...
4
votes
3answers
229 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 ...
1
vote
1answer
35 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 $...
0
votes
0answers
50 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
1answer
30 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 ...
0
votes
2answers
105 views

Does the following graph have a Hamiltonian path? [closed]

See the graph Through tracing through the vertices of the graph, I'm pretty sure that there is no Hamiltonian path. However, I'm not quite sure how to give a logical argument proving that there is no ...
0
votes
0answers
21 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.

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 ...
4
votes
1answer
74 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 ...
4
votes
1answer
37 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 ...
0
votes
0answers
11 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 &...
2
votes
1answer
53 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\}$...
0
votes
0answers
14 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 ...
0
votes
1answer
44 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 ...
3
votes
3answers
72 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 ...
2
votes
1answer
44 views

Graph Theory, Hamiltonian Cycles

Let $a, b \geq 3$ and let $G$ consist of two complete subgraphs $G_a$ and $G_b$ that share exactly two vertices. How many Hamiltonian cycles are in $G$? I was close! As answered below, $(K_a - 2)! * (...
1
vote
1answer
51 views

Does this given Graph is Planar Graph, does it contain Eulerian, Hamiltonian Cycle?

Let $G(V,E)$ be a Graph such that: $$V=\left \{ X\in P(\left \{ 1,2,3,4,5,6,7,8 \right \}) \ |\ \left | X \right |=4\right \}$$ $$E=\left \{ \left \{ X,Y \right \}\in V\times V \ |\ \left | X\Delta Y ...
0
votes
1answer
73 views

Prove that if G is hamiltonian then Line graph of G is hamiltonian too [duplicate]

Prove that if G is hamiltonian then Line graph of G is hamiltonian too I know that we have a closed path with all vertices included then because every edge in this path is connected to two other edges ...
2
votes
1answer
30 views

If a Graph have Eulerian Cycle and Hamiltonian Path, does it mean that the Graph have Hamiltonian Cycle?

Let $G$ be a Graph that have Eulerian Cycle and Hamiltonian Path, does it mean that $G$ must have Hamiltonian Cycle? I tried to find a counter example but I always got stuck since when I notice an ...
0
votes
0answers
32 views

How many different Hamiltonian Cycles in the graph$ K_{n,n}$

Let $K_{n,n}$ undirected graph with $n \geq 3$, how many different Hamiltonian Cycles in $K_{n,n}$? Note that different cycles means that their edges set are different. I will be glad for an answer, ...
1
vote
1answer
48 views

Proof of Chvátals Theorem

I was looking through multiple criteria for Hamiltonian circuits and read several papers such as the following from the university of Manchester. I was particulary intrigued by a theorem Wolframs Math ...
0
votes
0answers
14 views

Applications of Hamiltonian Decompositions

A Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. What are some applications of Hamiltonian decompositions? In what ways are they important ...
0
votes
1answer
45 views

No Hamiltonian Cycle

I want to prove that a simple graph that is 3-regular and has edge chromatic index 4 does not have a Hamiltonian cycle. After some research, I have found that the Petersen graph fits the criteria and ...
0
votes
0answers
22 views

Relation of the product of elements in the quotient graph to two Hamiltonian cycles differing in one edge

Lemma: Let $G$ be a finite group and $S$ be a generating set of $G$. Suppose, $N$ is a cyclic normal subgroup of $G$ $(s_1N, \cdots , s_n N)$ is a Hamiltonian cycle in $Cay(G/N,S)$ the product $s_1 ...
0
votes
0answers
9 views

Cyclical paths and deformation-dependent orientation

The points of a unit circle may be traversed either clockwise or counterclockwise without a traveller reversing direction, moving only "forward." If a unit circle is deformed to have a ...
0
votes
0answers
18 views

Hamiltonian cycles in a quotient graph and original graph

I am currently reading regarding Hamiltonian cycles and I came across the following. "Suppose, $N$ is a cyclic normal subgroup of $G$, such that $|N|$ is a prime power. $<s^{-1}t> = N$, ...
0
votes
0answers
8 views

Proofing that $|EX(n,P_k)|$ = 1

Let $P_k$ be path at size k vertexes , and $EX(n,P_k)$ the group of all unqiue graphs that dosent contain $P_k$ as a sub graph and have maximum amount of edges possible. Need to proof that there is ...
0
votes
2answers
50 views

Hamilton Graph is 2-connected

Show that a Hamiltonian graph is 2-connected. But the reverse is not true. Give an example for reverse. This guestion is my profesor's. I'm having difficulty in proving the above statement. Hoew can I ...
1
vote
1answer
30 views

How do I figure this out using Dirac's theorem?

I know that Dirac's theorem states “If $G$ is a graph with $n$ vertices, $n \geq 3$, each of degree at least $n/2$, then $G$ is Hamiltonian”, but how do I use this to prove that a graph with $99$ ...
0
votes
2answers
76 views

Determine if the graph is Hamiltonian using Dirac's theorem [closed]

I know that Dirac's theorem states “If $G$ is a graph with $n$ vertices, $n \geq 3$, each of degree at least $n/2$, then $G$ is Hamiltonian”, but how do I use this to prove that a graph with $99$ ...
2
votes
1answer
46 views

Is it true that $G^2$ is always hamiltonian?

Given a connected graph $G$, define $G^2$ to be a graph with same vertex set as $G$ and edge between two vertices $u$ and $v$ iff the distance between $u$ and $v$ in $G$ is at most $2$. Is it true ...
1
vote
0answers
27 views

Algorithm for a directed long path and disconnected sets

I'm looking at this algorithm, and I want to get something similar that leaves me with a "long directed path", and two weakly disconnected components (meaning there are no edges from one ...
0
votes
2answers
87 views

Degree sequence in a maximal planar graph

Two isomorphic 9 vertex graphs Given the ordered degree sequence of a hamiltonian circuit in a maximal planar graph. Can we have different maximal planar graphs with the same ordered degree sequence? ...
1
vote
1answer
88 views

Ultra-Hamiltonian cycle

Ultra-Hamiltonian cycling is defined to be a closed walk that visits every vertex exactly once, except for at most one vertex that visits more than once. Question:- Prove that it is NP-hard to ...
1
vote
0answers
48 views

simple graph with n vertices and hamiltonian cycle

we have a simple graph with n vertices and hamiltonian cycle, prove it has 2 even subgraphs T,S such as each edge of G is at least in one of T or S. part 2: if n is even , prove it has 2 odd subgraphs ...
0
votes
0answers
31 views

Is there any new developments on the Barnette's conjecture?

When I searching for interesting math problems. I find there is a graph theory conjecture called the Barnette's conjecture. The statement is: Is every bipartite simple polyhedron Hamiltonian? A early ...
1
vote
1answer
43 views

How to find a Hamilton cycle contains the edge 37 in K11 graph?

Let $V(K_{2n+1}) = \{0, 1, 2, ..., 2n-1, x\}$. We have a standard way of decomposing $K_{2n+1}$ into Hamilton cycles. In $K_{11}$, which "standard" Hamilton cycle contains the edge $37$?
1
vote
1answer
25 views

Sequence of elements representing a Hamiltonian cycle and the generating element of a subgroup

Let $S$ be a subset of a finite group $G$. The Cayley graph $Cay(G,S)$ can be defined as the graph whose vertices are the elements of $G$, with an edge joining $g$ and $gs$, for every $g \in G$ and $s ...
5
votes
0answers
58 views

Are there topological invariants for this path-finding game?

There is a game I've seen recently (link; note that I have no affiliation with this game) which involves finding a Hamiltonian path connecting a graph of points, as illustrated below. ...... The ...
1
vote
0answers
31 views

Constructing a Hamiltonian cycle for 6-dominos

This may be the wrong forum, as it's sort of about programming also. I'm trying to encode a directed Hamiltonian cycle for a standard set of 28 6-dominos. The difficulty I am having is trying to keep ...
2
votes
1answer
51 views

On existence of an hamiltonian path in cartesian power of directed cycle graph

Is it true, and if so, how to show it, that there is a Hamiltonian path in the cartesian power of a directed cycle graph (i.e. the iterated cartesian/box product $\square$) $C_n^{\square r}$ where $n, ...
3
votes
1answer
164 views

what is a path called that visits every vertex of a graph at least once?

As I understand it, a Hamiltonian path visits every vertex of a graph exactly once. Is there a name for a path which visits every vertex at least once? Some graphs may be such that a cycle visiting ...
0
votes
1answer
34 views

Value of a hamiltonian path along a function closely related to the hamiltonian function

Consider $T^*M$ with the canonical symplectic structure. Let $H:T^*M\rightarrow \mathbb{R}$ be an hamiltonian function and $h:\mathbb{R}\rightarrow \mathbb{R}$ a smooth function. Let $\gamma(t)$ be ...
0
votes
1answer
65 views

Hamiltonian Paths and Next Neighbor Algorithm in Complete Graphs

In a complete graph, can the next neighbor algorithm (NNA) ever produce the most optimal Hamiltonian path? The NNA is close enough to the most optimal path to be used in real-life applications, but is ...
0
votes
0answers
87 views

How I can shortly prove that you can have a closed knight's tour on the 6x6 chessboard?

On the website, the explanation that a knight's tour on a $6\times6$ board is possible is the continued proof of around $1\frac{1}{2}$ pages! It will be great if one of you could provide a simple, ...
1
vote
1answer
88 views

Question about closed knight's tours for n x m chessboard

Is there a simple mathematical algorithm where you can get a CLOSED knight' tour on an n x m chessboard? I need a way to prove that it is mathematically possible or impossible to have a closed knight'...
1
vote
1answer
59 views

A graph theory problem from mobile games

Example game interface This is the question that comes to my mind when I play a game called QuickyRoute,which essentially a Hamilton graph problem,the game will randomly generate a number of points,...
0
votes
1answer
36 views

Verifying some properties of Hamiltonian Graphs

I want to verify these two properties of Hamiltonian graphs: Graph having multiple Hamiltonian cycles can have different cycle lengths or all are of same length? i.e. All Hamiltonian cycles have same ...
0
votes
0answers
13 views

which similar np hard problem can be used to reduce timetabling problem?

I have a set of courses and each courses have a set of classes. Each classes have a set of timings available with some penalty. I wanted to schedule each classes to any of the timings of its with a ...
0
votes
1answer
34 views

Hamiltonian path- Lower bound of optimal solution

I am trying to find an algorithm with polynomial run time that calculates the lower bound of the optimal solution on the Hamiltonian Path problem( a lower bound to the sum weight of the hamiltonian ...

1
2 3 4 5
12