Questions tagged [hamiltonian-path]

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

Filter by
Sorted by
Tagged with
-1 votes
1 answer
51 views

Hamilton cycle on chessboard

Suppose we have $8 \times 8$ chessboard such that two squares are adjacent iff they share a common side. In one move pawn can move to adjacent square. Prove that the pawn made a different number of ...
user avatar
0 votes
0 answers
9 views

What is the time complexity to finding the least weight for Hamiltonian cycle in complete graph without finding best tour?

As we know finding the best tour in complete graph with n nodes, or the Traveling Salesperson Problem solved by the dynamic programming algorithm in $n^2.2^n$ time ...
user avatar
0 votes
0 answers
25 views

An extension of Dirac Theorem

Following a related proof of Dirac theorem, I want to show that if $G$ is a balanced bipartite graph of order $n$ with minimum degree more than $n/4$, then $G$ has a Hamilton cycle. Dirac's theorem: ...
user avatar
  • 571
1 vote
0 answers
28 views

What is the necessary and sufficient condition for a graph to be a Hamiltonian Chordal Graphs?

Chordal Graph. A chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Hamiltonian ...
user avatar
  • 1,174
0 votes
0 answers
15 views

Hamiltonian Cycle but Minimise Distance Between Nearest Point in Other Set

I have two sets of points in $\mathbb{R}^2$, let's call them red and blue. I would like to create a Hamiltonian Cycle, i.e., cycle going through all points once. This cycle should minimise the ...
user avatar
0 votes
0 answers
40 views

"Partial" factorials

Other than double factorials and triple factorials, what is known about factorials which are missing some of their factors? For example, $1344=2 \times 3 \times 4 \times 7 \times 8$ which is $\frac{8!}...
user avatar
0 votes
0 answers
18 views

Path Lengths and Random Walk - Generalization of the Uncut Spaghetti Game

The following is a kind of generalization of the interesting Uncut Spaghetti game (https://mathpickle.com/project/uncut-spaghetti-number-patterns/): Consider a 2D integer lattice where each point has ...
user avatar
  • 541
2 votes
0 answers
36 views

Probabiity of a graph containg hamiltonian cycle with given probabily for and edge between any two vertices.

Consider a non-oriented graph with n vertices: {1 ... n}. Let $ p \in [0,1]$ is the probability of having an edge between any two vertices. The probability of having an edge is the same for any two ...
user avatar
0 votes
0 answers
29 views

Hamiltonian Cycle and vertex degrees

Assume we have a graph $G=(V,E)$. Denote by $C$ a Hamiltonian cycle in $G$. Is it true to say that the degree of every vertex in $C$ is $2$, and for every vertex in $C$ its degree on $G$ is also $2$ ? ...
user avatar
1 vote
0 answers
30 views

list of unique elements formed by concatenating permutations of initial lists

I already asked the question on StackOverflow, but I thoughted more about the problem, and my question is now not about programming but graph theory. I would like to combine several lists, the result ...
user avatar
  • 121
1 vote
1 answer
79 views

Prove Herschel graph is nonhamiltonian

Let us denote by $c(G)$ the number of components of graph $G$. Theory: For a hamiltonain graph we have $c(G-S)\leq|S|$ for any set $S$ of vertices of $G$. How can I show that Herschel graph is ...
user avatar
3 votes
1 answer
154 views

Let $T$ be a tournament directed graph (round robin). Prove that there is an odd number of Hamiltonian paths in the graph

Let $T$ be a tournament directed graph (round robin). Prove that there is an odd number of Hamiltonian paths in the graph. I am aware that this question may be considered a duplicate of this one: The ...
user avatar
4 votes
1 answer
59 views

Is there a graph with 2-factor that is not hamiltonian?

If a graph $G$ has a 2-factor it means it is a 2-regular subgraph that contains all vertices of $G$. Isn't it a hamiltonian cycle? because it is 2-regular so it is a cycle and it contains all vertices ...
user avatar
  • 576
5 votes
1 answer
112 views

Prove that if $G$ is a graph of order $101$ and $δ(G) = 51$, then every vertex of $G$ lies on a cycle of length $27$

Prove that if $G$ is a graph of order $101$ and $δ(G) = 51$, then every vertex of $G$ lies on a cycle of length $27$ (Chapter 3 Exercise 16.a Chromatic Graph Theory,Gary Chartrand, Ping Zhang) ...
user avatar
2 votes
1 answer
156 views

Simple graph with $G$ with $n$ vertices, satisfying $d(u)+d(v)\ge n-2$ for every two non-adjacent vertices $u,v$, wtih no Hamiltonian path

A simple graph $G$ with $n$ vertices in which the sum of degrees of every two non-adjacent vertices is at least $n-1$ has a Hamiltonian path. As described here, one can add a new vertex $w$ and ...
user avatar
0 votes
0 answers
29 views

Can we convert 'possible bipartite' question to 'max flow' question

Ok, I am in dangerous waters :) I just began looking into popular graph interview questions and came across this classical one ...
user avatar
  • 101
6 votes
2 answers
105 views

Suppose E is a set of non adjacent edges of G and $\delta(G)\ge\frac{n+e}{2}$.Show that there is a Hamiltonian cycle that contains all the edges of E.

Suppose that $E$ is a set of non adjacent edges of graph $G$ that $\delta(G) \ge \frac{n+e}{2}$ where $|E|=e$. Show that there is a Hamiltonian cycle that contains the edges of $E$. I know that if the ...
user avatar
  • 331
1 vote
1 answer
355 views

If $deg(u)+deg(v) \ge n-1$ for $u$ and $v$ are non adjacent vertices, then G has Hamiltonian path

Hamiltonian path is a path that contains all of the vertices of the graph. I know that if $deg(u)+deg(v) \ge n$ for every two non adjacent vertices $u$ and $v$ then the graph has Hamiltonian cycle and ...
user avatar
  • 155
2 votes
1 answer
41 views

Every bipartite Eulerian graph is a Hamilton graph

This is a true/false question I'm trying to solve to prepare for my exam. Could someone confirm my answer and help me prove it? What I think: false, but I can not come up with an example.
user avatar
  • 85
0 votes
1 answer
28 views

Are all 4-regular Hamiltonian graphs Euler graphs?

This is a true/false question I'm trying to solve to prepare for my exam. Could someone confirm my answer? What I think: true, because the graph then has only even degrees and the graph is also ...
user avatar
  • 85
0 votes
1 answer
106 views

Necessary condition for Hamiltonian path

Determining a graph does not contain Hamiltonian path is very difficult. See for example this particular graph. This sufficient condition for Hamiltonian path found in this link ClickHere does not ...
user avatar
  • 41
19 votes
0 answers
277 views

Proving the number circle internet meme, where sum of each adjacent numbers is a perfect square

I came across this internet meme and one of my friend mentioned that he thinks that such number circle would always exists for any big enough integer. We tried to prove the hypothesis, but could not ...
user avatar
  • 191
0 votes
0 answers
50 views

Is it possible to arrange handshakes in this way?

I am reading Eulerian graphs from this pdf. In page 210, exercise 9.5.7, I am stuck at following problem. Each of 8 persons in a room has to hand shake with every other person as per the following ...
user avatar
6 votes
1 answer
102 views

Is there a graph with all vertices having degree 3 or greater that doesn't have a hamiltonian path?

Is there an example of a simple, undirected graph with all vertices having degree 3 or greater that doesn't have a hamiltonian path? I've seen this question appear in the title of this post, but then ...
user avatar
1 vote
0 answers
52 views

Monotone chromatic index of oriented hypercube

Edge coloring is right if any adjacent edges have different color. Right edge coloring is monotone if a color of an edge outcoming from vertex $v$, is bigger than the color of any incoming edge into ...
user avatar
0 votes
1 answer
121 views

Does there exist a tournament with exactly two Hamiltonian paths?

A tournament is a complete directed graph. A Hamiltonian path is a path that crosses each vertex exactly once. My conjecture is no. I have tried using induction, proof by contradiction, all to no ...
user avatar
2 votes
1 answer
44 views

Hamiltonian graphs with high degree and high girth

Given integers $d\ge2$ and $k\ge3$, is there a Hamiltonian (simple) graph $G$ with minimum degree $\delta(G)=d$ and girth $g(G)\ge k$? And if so, what is the minimum number of vertices, call it $N(d,k)...
user avatar
  • 70.1k
0 votes
0 answers
22 views

Prove that these two connected Petersen subgraphs are Hamiltonian (or not).

I'm currently revisiting some graph theory and have ran into the following graph. I am to prove if it is Hamiltonian or not. To my knowledge there is no definite or "good" theorems to ...
user avatar
1 vote
0 answers
11 views

Which requirements should a TSP matrix fulfill in order to be solved with Hungarian method?

I was reading about TSP problem in general & about Hungarian method in particular, and found a 6x6 matrix, where applying Hungarian method didn't give me an answer (solved by hand & checked on ...
user avatar
0 votes
0 answers
67 views

Hamiltonian Cycle and Euler Cycle

True/False: Let $G$ be a connected undirected graph such that all vertices have even degrees. Every Euler cycle in $G$ is also a Hamiltonian cycle if and only if $G$ is a cycle graph. I think this one ...
user avatar
  • 1
2 votes
1 answer
57 views

How many different ways can single directed edge be added.... (graph theory)

Let G be the following directed graph: In how many different ways can a single directed edge be added to G3 so that there is a cycle of length 8 starting at vertex A? I tried a few ways of inserting ...
user avatar
  • 325
0 votes
0 answers
26 views

Hamiltonian cycle with additional constraints

I could use a little guidance to solve the following mathematical problem. I have a fully connected graph with bidirectional edges of known weight > 0. The weight of an edge depends on the ...
user avatar
  • 111
1 vote
0 answers
44 views

Non hamiltonian cubic graphs

It is known that almost all cubic graphs are hamiltonian (see here) However, I did not find any information about non-hamiltonian cubic graphs online. If you know some properties/literature about non-...
user avatar
  • 231
0 votes
0 answers
36 views

Non-isomorphic non-hamiltonian graphs

I have the following question: Find an infinite family of non-isomorphic graphs without hamiltonian paths such that $\delta(u) + \delta(v) \geq |V(G)| - 2$ for every non adjacent vertices $u, v$. I'...
user avatar
0 votes
0 answers
23 views

Size of a path defined on a Hamiltonian cycle

Let $G=(V,E)$ (Such that $\vert V\vert$) be a Hamiltonian cubic graph and $v\in V$. We represent a graph as a cycle with vertices labeled in such a way that $(0,\ldots ,n-1)$ is a Hamiltonian cycle ...
user avatar
  • 231
0 votes
1 answer
44 views

Prove that, if all perfect matchings in G are pairwise disjoint, than every two perfect matchings contain the edge set of a hamiltonian cycle in G.

I have no idea how to prove this one. It looks like common sense, but I don't know hot to proceed with the proof.
user avatar
0 votes
1 answer
72 views

Minimal collection of paths that visit all vertices of a subgraph

Assume we have a weighted, directed Graph $G$ with vertices $V$. There are vertices named START and END in the graph. Among all possible paths from START to END, I want to select paths that, together, ...
user avatar
0 votes
0 answers
24 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 ...
user avatar
2 votes
3 answers
256 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 ...
user avatar
  • 862
1 vote
1 answer
58 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 $...
user avatar
0 votes
0 answers
54 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 ...
user avatar
0 votes
1 answer
35 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 ...
user avatar
  • 503
0 votes
0 answers
31 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. [duplicate]

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 ...
user avatar
  • 45
4 votes
1 answer
184 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 ...
user avatar
  • 195
4 votes
1 answer
54 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 ...
user avatar
  • 53
0 votes
0 answers
17 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 &...
user avatar
  • 9
2 votes
1 answer
204 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\}$...
user avatar
  • 153
0 votes
0 answers
25 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 ...
user avatar
  • 9
0 votes
1 answer
78 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 ...
user avatar
3 votes
3 answers
203 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 ...
user avatar

1
2 3 4 5
12