Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [hamiltonian-path]

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

A Hamilton path (or Hamiltonian path) in a graph is a path that visits each vertex exactly once. Similarly, a Hamilton cycle in a graph is a cycle that visits each vertex exactly once.

We can talk about directed and undirected Hamilton paths/cycles, within directed and undirected graphs.

The Hamilton path problem, i.e., determining whether or not an input graph has a Hamilton path, is NP-Complete.

629 questions
1
vote
1 answer

Prove that no hamilton circuit for the graph exists

To prove this, I decided to start with vertex e, then two cases occur Case 1: Use d-e-f, delete b-e and e-h at e. Use a-b-c and g-h-i. Delete at d, d-a (prevent subcircuit). Use g-d-e. Then at g, delete n-g and g-l. Use k-n-a and i-l-j. Delete at…
user827508
1
vote
1 answer

Prove that no Hamilton circuit exists (Find number of cases)

So my question is this. My instructor says that when trying to prove that a Hamilton circuit doesn't exist, you should pick a vertex that's "easy to work with" I.E. a vertex with the least branching paths. They then said that I should show all…
user827508
1
vote
2 answers

Hamiltonian path in a complement of a tree

T is a tree on n-vertices for which the greatest degree is smaller than n-1, prove that the complement of T has a Hamiltonian path. I was trying to achieve Ore's inequality, this is what I have written so far:
Asya Olshansky
  • 189
0
votes
1 answer

Question on hamiltonian graph

Can anyone give me an example of a Hamiltonian graph $H$ of order $n=2k$ for some $k\geq 2$ where $k$ vertices have degree $2$, no two vertices of which are adjacent, while the remaining vertices have degree $3$ or more? Does this question needs a…
user109260
  • 101
  • 1
0
votes
0 answers

A polynomial time algorithm for Finding a Hamiltonian path in an undirected graph - searching for a counter example

I have the below algorithm that appears to find a Hamiltonian path in undirected graphs (if one exists). I've tested with every graph I could find or come up with and it appears to work. I've included an example of it working on a decision problem…
Ben
  • 1
0
votes
1 answer

Prove that $\Delta(G)\le \frac{n-1}{2}$

I have to prove that if graph $G$ is not Hamiltonian, but $G-v$ is Hamiltonian for every $v\in V(G)$ then $\Delta(G)\le \frac{n-1}{2}$. I tried to prove this with contradiction. So, first if we assume that $\Delta(G)\ge \frac{n+1}{2}$, and let $v$…
Trevor
  • 533
0
votes
2 answers

Determine if the graph is Hamiltonian using Dirac's theorem

I know that Dirac's theorem states “If $G$ is a graph with $n$ vertices, $n \geq 3$, each of degree at least $n/2$, then $G$ is Hamiltonian”, but how do I use this to prove that a graph with $99$ edges on $15$ vertices is Hamiltonian? Should I use a…
Aren Kam
  • 21
0
votes
0 answers

Tensor product $G\times K_n$

Let $G$ be a Hamiltonian graph and $K_n$ the complete graph on $n$ vertices. Are there results about that the graph $G\times K_n$ is Hamiltonian or not? Thanks.
MarY
  • 1
0
votes
2 answers

Minimum Nodes for Hamiltonian Path

Sorry if this has been asked before but I wonder how to detect minimum number of nodes for given Hamiltonian Path for fixed endpoints. Lets say below is a Hamiltonian path from $1$ to $16$; Full Path And if we keep endpoints ($1$ is start and 16 is…
Joseph
  • 23
  • 3
0
votes
1 answer

Hamiltonian cycle equivalence?

If we have an undirected graph, is the existence of a Hamiltonian cycle in the graph equivalent to finding a subset of edges S in the graph such that every vertice appears in exactly two different edges in S?
Måns Nilsson
  • 323
0
votes
1 answer

Give two distinct codes for $n = 4 $

gray codes for $n = 4 $. Attempt : The codes for $n = 4 $ : $0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111$ $0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001,…
user273952
  • 319