Questions tagged [hamiltonian-paths]

A path in a graph is said to be Hamiltonian if it visits each vertex exactly once.

2 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3
votes
0answers
52 views

Problem of determining if a $4$ connected graph has $k$ Hamiltonian cycles

Definition: Define the $k$-HamiltonianCycles problem as the decision problem that asks if a given graph has at least $k$ distinct Hamiltonian cycles. Question: Is there some constant $k$ so that the $...
1
vote
0answers
51 views

Reduction of irregular graphs, to regular graphs, while preserving hamiltonicity

I am wondering if this is a topic that has had research done... If I could reduce irregular graphs to regular graphs (including replacing redundant node clusters with dummy nodes), while ensuring ...