Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Questions tagged [hamiltonian-path]

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

132 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
828 views

### What is the maximum number of edges in an $n$-vertex non-Hamiltonian graph of minimum degree at least $2$?

Q: What is the maximum number of edges in an $n$-vertex non-Hamiltonian (simple) graph of minimum degree at least $2$? This question relates to Maximum number of edges in a non-Hamiltonian graph ...
119 views

### How many hamilton paths can a non-hamiltonian graph have?

What is the maximum number of hamilton paths a graph with $n$ vertices can have without having a hamiton cycle ? If my turbo pascal program works well, the first few values for $3,4,...$ vertices ...
131 views

### The number of Hamiltonian paths in a tournament is always odd?

A tournament is defined as an orientation of a complete graph. Prove or disprove the following statement: In a tournament, there are exactly an odd number of Hamiltonian paths. In all cases I’ve ...
7k views

### Proof of Hamilton Cycle in a Complete Bipartite Graph

For a complete Bipartite graph K(m,n) has a Hamilton cycle if and only if m=n. I want to know if the following proof technique is correct. My proof will consider using proof by contradiction. Assume ...
69 views

248 views

### Classification of maximally non-hamiltonian graphs?

A graph is called maximally non-hamiltonian, if it does not contain a hamilton-cycle, but no edge can be added without creating a hamilton-cycle. In other words, every pair of non-adjacent vertices ...
105 views

### Random Tournaments

A tournament is a directed graph in which every pair of vertices has exactly one directed edge between them—for example, here are two tournaments on the vertices {1,2,3}: (1,2,3) is a Hamiltonian ...
30 views

### Hamiltonian cycles in balanced bipartite graph - proof of theorem

does anyone have an idea how to proof this theorem? Let $B$ be a balanced bipartite graph of order $2n$, $n ≥ 2$, as defined below and $s, t$ be two integers in $[0, n − 1]$. Then $D_s ∪ D_t$ forms a ...
51 views

41 views

### Efficient hamiltonian path through neighboring squares

My knowledge of Number/Graph theory is very limited. I'm sorry if someone can find this answer posted elsewhere quickly, I spent some time searching but don't know enough to know what to search. The ...
47 views

### Symmetric difference of Hamilton circuits in planar cubic graphs

The answer to math.stackexchange.com/questions/3235317/every-cubic-3-connected-hamiltonain-graph-has-three-hamiltonian-cycles-with-spec?rq=1 points out that the cube graph contains no three Hamilton ...
24 views

### Chance of not finding an alternating Hamiltonian path in a colored graph in $n$ random walks

Introduction Given a random graph which can be constructed as follows: generate $s$ pairs of unconnected black edges and $2 \cdot s$ vertices connect these black edges using red edges, where the ...
199 views

### Show that the line graph of any quasi-cyclic graph contains a Hamiltonian cycle.

The definition I have been given for a quasi-cyclic graph is as follows: a graph $G=(V, E)$ is quasi-cyclic if $1)$ it contains a unique cycle $C=(V(C), E(C))$ and $2)$ for each edge $xy$ in $E$ at ...
32 views

### Combinatorial proof of Hamiltonian paths on the rook graph

We can be sure that number of Hamiltonian paths on the rook graph for any single cell on $n\times2$ chessboard equals  H(n+1) = \sum_{k=0}^{n} \binom{n}{k} \binom{k}{\lfloor{\...
23 views

### Graph Problem: find X path lengths which are closest to each other (similar to shortest path)

I have the following problem: 1 Start point 1 End point 7 Knots / waypoints which you have to visit in any order All 9 knots are connected with each other. All paths have to start at the start point ...
38 views

78 views

### Questions about an “almost” 4-connected graph

How would this graph be classified? And what properties does it have? What would be a natural thing to study with this graph? I know it has 40 nodes. It's undirected. It's planar if I'm not mistaken. ...