Questions tagged [hamiltonian-path]

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

396 questions
Filter by
Sorted by
Tagged with
362 views

How many routes are there from $A$ to $B$ that cross every node exactly once?

Imagine an $n \times n$ grid, we start on one corner of the grid in square $A$, and need to reach the opposite corner to square $B$. The rules are, you can only move to an adjacent square, you can't ...
86 views

Ambiguity regarding the definition of 'path' in graph theory

While going through the Introductory chapter of 'Graph Theory' by Bondy and Murty, I came across the definition of 'path' that says it's a sequence of vertices in such a way that two vertices are ...
200 views

Dijkstra’s algorithm / path is this done correctly?

im doing this assignment and it seems as if my teacher has made a mistake. according to me in order to find the minimum spanning treee from a-z , you start from a and then go to : a,f,d,c,b,e,z,g ...
45 views

Existence of fair parallel queues

I just spent a few days at a major theme park. The queue for one particular ride (involving pirates) bifurcated upon entry; the two sides wound independently through a maze and emerged next to each ...
30 views

Do hamiltonian paths exist on n-valent, simple, connected, planar graphs, where n>2?

I don't know to much about graph theory, so was wondering about the posted question. If it is too much perhaps you may know the answer if n is even? Any help is appreciated. Also, this is my first ...
1k views

Generate all De Bruijn sequences

There are several methods to generate a De Bruijn sequence. Is there a general algorithm to create all unique (rotations are counted as the same) De Bruijn sequences for a binary alphabet of length $n$...
138 views

Hamiltonian bipartite graphs

Let $G$ be a bipartite graph with $n$ vertices and independent sets $U$ and $V$ such that $\vert U\vert=\vert V\vert=k=\frac{n}{2}>2$. I want to show that if $d(v)>\frac{k}{2}$ for every ...