# Questions tagged [hamiltonian-path]

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

128 questions
0answers
113 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 ...
0answers
76 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 ...
0answers
67 views

0answers
22 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 ...
0answers
21 views

0answers
24 views

### Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that

Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that $$c(\tau(a),\tau(1))+\sum_{i=1}^{a-1} c(\tau(i),\tau(i+1))\leq b$$ Prove ...
0answers
57 views

### Least number $k$ , such there is no graph with $n$ nodes and $k$ hamilton-cycles

Let $f(n):=$min{ $k \in N$: There is no graph with $n$ nodes and $k$ hamilton-cycles} for $n\ge 3$ The values I found out so far : $$f(3)=2$$ $$f(4)=2$$ $$f(5)=3$$ $$f(6)=9$$ $$f(7)=13$$ f(8)...
0answers
157 views

### Conditions for a $2$-connected graph to be hamiltonian?

Let G be a simple undirected graph. If G is connected, and every vertex has degree $2$, then G is hamiltonian. (In fact, G only consists of the hamilton-circle) Are there some weaker sufficient ...
0answers
199 views

### Complete tripartite graph hamiltonian

Let $G_{a,b,c}$ be a complete tripartite graph. For what values of $a, b$ and $c$ is $G_{a,b,c}$ Hamiltonian?
0answers
412 views

### Are there necessary and sufficient conditions of a graph to decompose into two Hamiltonian cycles?

Let $G$ be a graph. Definition: $G$ is decomposable into two Hamiltonian cycles if the edge set $E(G)$ can be partitioned into two disjoint Hamiltonian cycles. Obviously, if $G$ is decomposable into ...