# Questions tagged [hamiltonian-path]

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

414 questions
Filter by
Sorted by
Tagged with
35 views

### What is a vertex-transitive graph? (Question about Lovász Conjecture)

I was reading about Lovász Conjecture and came across the following definition on Wikipedia of a vertex-transitive graph (see below). $\bullet$ It states that a graph is vertex-transitive if for any ...
46 views

### Hamiltonian circuit

Prove that a graph that posses a Hamiltonian circuit must have no pendant vertices. To prove this, each vertex in a graph, that also has a hamiltonian circuit, much acquire at least two edges in ...
25 views

### Hamiltonian paths and cycles of rook graph on $n\times2$ chessboard

According to OEIS, there are closed form for directed Hamiltonian paths (A096121) and Hamiltonian cycles (A276356) of rook graph on $n\times2$ chessboard. Are there papers which include proof of those ...
35 views

120 views

### Doubt on the definition of closure of a graph.

The closure of a graph $G$, denoted $cl(G)$ is defined to be the supergraph of $G$ obtained from $G$ by recursively joining pairs of nonadjecent vertices whose degree sum is atleast $n$ untill no ...
43 views

### Give me an example of a graph that has a Hamilton path that cannot be found with a greedy heuristic.

Give me an example of a graph that has a Hamilton path that cannot be found with a greedy heuristic. I have yet to find a graph that can fulfill these requirements, I thought a Peterson graph might ...
68 views

### Extraneous edges in hamiltonian graphs

I was wondering if this is already a solved question, it would save me a bunch of time if it is. Is it the case that in an undirected hamiltonian graph with N nodes, if some subset of our N nodes has ...
82 views

### A contradictory relation between probability and number of paths

Consider an urn containing $c$ balls, $\alpha$ of which are red, $\beta$ of which are blue, and $\gamma$ of which are green, and $\alpha+\beta+\gamma=c$. We perform $n$ trials with replacement of one ...
301 views

### Is any tree a Hamiltonian Graph

Hamiltonian path is a graph where every vertex is visited exactly once. And a tree can be anything, like a BST. I think that this answer is no because in a BST, it could find an element before ...
160 views

### 3-connected planar bipartite graph without a Hamiltonian path

I'm stuck with exercise 18.1.5 of Bondy & Murty's Graph Theory book which asks for an example of a 3-connected planar bipartite graph on fourteen vertices that is not traceable (that is, which has ...
39 views

### Euler and Hamilton graphs

i would like to know about this. If it is Euler and Hamilton. As i see because it is $u_0$ unti $u_{19}$ it isn't Euler. Also, it is Hamilton because if we erase the edges we see it. Is this right or ...
158 views

### How to generate a Penrose tessellation around a given tile?

Given a starting Penrose tile, I need to build a "spiraling" tessellation around it. The following picture illustrates the request: In this example, the starting tile is a "thin rhombus" (the pink ...
245 views

### Spiral path on a Penrose tiling

I would like to color a Penrose tiling by following a "spiral path", painting each tile according to a given color sequence. In this picture, I illustrate what I am looking for: The dashed line ...
Given a graph $G = (W \cup U, E)$ where $W = \{w_1, w_2, ..., w_n\}$, $U = \{u_1, u_2, ..., u_n\}$ and $E = \{\{w_i, u_j\}: 1 \leq i, j \leq n\}$. The task is to calculate the number of Hamiltonian ...