Questions tagged [hamiltonian-path]

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

414 questions
Filter by
Sorted by
Tagged with
34 views

Graph theory: decompositions and Hamiltonian graph

13 people who are not superstitious wish to have dinner together at a round table for a few nights so that each person has different neighbours every night. For how many nights can they do this? ...
50 views

Show that undirected connected 3-regular graph with 8 vertices has Hamiltonian path

Let be $G=\langle V,E\rangle$ undirected and connected 3-regular graph with 8 vertices. Prove that $G$ has Hamiltonian path. I am trying to prove the above claim, however I don`t know how to develop ...
51 views

Hamiltonian path in $S_n$?

Say $S_n$ is the symmetric group. Define a graph $G$ by $G=(S_n,E)$, where there is an edge from $\sigma_1$ to $\sigma_2$ if and only if $\sigma_2=t\sigma_1$ for some transposition $t$. Is there a ...
42 views

Show that $G$ is not Hamiltonian.

Suppose that $G$ is a graph with $pq$ vertices where $p$ and $q$ are primes and $2<p<q$. If $(p-1)(q-1)$ vertices of $G$ have degree $p+q-1$ and all other vertices have degree $pq-1$, show ...
49 views

34 views

A Hamiltonian cycle generated by lame rooks moves

I have got this problem at high-school math-contest seminar on Graph Theory Let us have a chessboard, where one black and one white lame rooks stand. Lame rook can move to edge-adjacent field only. ...
25 views

Hamilton Cycle Proof Verification

Explain why there is no Hamilton cycle in the graph attached below. Then, show that if any pair of non-adjacent vertices in the same graph are joined by an edge, then the resulting graph has a ...
57 views

$n^{th}$ Dimensional Prime Nexus Conjecture (Hamilton's Path & Cycle)

The system and proposition of Prime Nexus - We have to arrange $n>1$ Distinct natural numbers in a sequence such that the adjacent elements sums upto any Prime number. Convenience is when we set ...
36 views

Travelling salesman problem visiting different nodes different times [closed]

Hi I am trying to solve a more complicated travelling salesman problem (shortest path visiting all nodes in a directed graph), where (1) I need to revisit different nodes for different times, (2) I ...
50 views

How to find the number of cycles and set of nodes in each cycle in an undirected, connected and loopless graph?

This question could be repetetive. I tried to look up for some posts, most of them are to check whether a graph contains a cycle or not. Assume there is no multiple edge. My problem is I need to find ...
25 views

Induction Proof On “Tree with Nodes as Cycles” Graph

So I have one question about defining the type of graph I was working on: Define A Graph - Tree Graph With "Cycles" as Nodes A short summary for the graph I would like to define as G=(V,E): ...
69 views

Define A Graph - Tree Graph With “Cycles” as Nodes

I am working on my thesis and I would like to have a proper definition for this type of graph: "Tree Graph With Nodes As Cycles" I would like to define a graph similar to a "simple tree", but some of ...
50 views

34 views

How to show that there exists a tournament of size n with a certain number of Hamiltonian paths? [duplicate]

Assuming a tournament of size $n$ is a choice of orientation for each edge of $K_n$, show that there exists a tournament of size $n$ with at least $\dfrac{n!}{2^{n-1}}$ Hamiltonian paths. This ...