Does the addition of a new vertex always guarantee a Hamiltonian path or cycle?

Click For Summary
SUMMARY

The discussion centers on the relationship between Hamiltonian cycles (HC) and Hamiltonian paths (HP) in graph theory. It establishes that if a graph G has a Hamiltonian cycle, it necessarily has a Hamiltonian path. The forum participants explore the implications of adding a new vertex to a graph G, which connects to all existing vertices, forming a new graph G'. If G' has a Hamiltonian cycle, then G has a Hamiltonian path. Conversely, if G' does not have a Hamiltonian cycle, G cannot have a Hamiltonian path.

PREREQUISITES
  • Understanding of Hamiltonian cycles and paths in graph theory
  • Familiarity with NP-completeness concepts
  • Knowledge of graph construction techniques
  • Experience with algorithm design and analysis
NEXT STEPS
  • Study the algorithm for determining Hamiltonian cycles (HC) in graphs
  • Research the implications of NP-completeness in computational problems
  • Explore graph theory concepts related to Hamiltonian paths (HP)
  • Learn about graph transformations and their effects on properties
USEFUL FOR

Mathematicians, computer scientists, algorithm designers, and students studying graph theory and NP-completeness.

atrus_ovis
Messages
99
Reaction score
0
Watching this lecture from nptel about NP completeness:
http://www.youtube.com/watch?v=76n4BjlL1cs&feature=player_embedded

-We have an algorithm, HC , which given a graph tells us whether or not it has a hamiltonian cycle.
-We want to use it in order to create an algorithm that determines whether an input graph has a hamiltonian path.


If the input has a HC, then it has a HP as well.Okay.

But around 29:00, it is stated:

If the input doesn't have a HC (the output of HC algorithm is a "no"), we add a vertex to it that connects to all other vertices in the graph.If that new gragh G' has a HC, then the original graph G has a HP.
But thinking about this, how bout this example?

edit:in the pic, i meant to say that "graph G doesn't have a HP"
 

Attachments

  • ham.JPG
    ham.JPG
    9.4 KB · Views: 531
Last edited:
Technology news on Phys.org
You've misunderstood what the goal is. The goal is to find out whether G has a HP.
See: http://www.youtube.com/watch?v=76n4BjlL1cs&feature=youtu.be#t=21m08s"

The input is the Graph G' which consists of the original Graph G and the additional vertex u connected to all vertices of G.

We want to find out if G has a HP by using the following theorem:
G has a HP iff G' has a HC

In your example, let us pretend that we do not know whether G has a HP.
So, we form G' and use it as an input for HC. Now, there are two possible outcomes:
(i) HC says: yes, G' has a HC. It then follows that G has an HP.
(ii) HC says: no, G' has no HC. It then follows that G has no HP.
 
Last edited by a moderator:

Similar threads

Hamiltonian Path - Induction Proof
  • · Replies 4 ·
Replies
4
Views
4K
Euler's path same as Hamiltonian cycle
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Finding the chromatic number of a graph with biconnected components
  • · Replies 1 ·
Replies
1
Views
2K
MHB Does the graph G with varying vertex degrees have an Eulerian path?
  • · Replies 3 ·
Replies
3
Views
2K
Graduate Which Papers Will Shape Future Quantum Gravity Research?
  • · Replies 2 ·
Replies
2
Views
4K
Graduate How Does the Ford-Fulkerson Algorithm Determine Maximum Flow in a Network?
  • · Replies 1 ·
Replies
1
Views
2K