Problem Detail: Can you help me with this problem ?
Given an undirected graph $G$ and an integer $n$, prove that determining whether the graph has wheel on $n$ vertices $W_{n}$ (a wheel $W_{i}$ is such that $i$ nodes form a cycle and a $i+1$st node is connected to all other nodes, resulting in $2i$ edges) is NP-complete.
Asked By : 372
Answered By : Aryabhata
Hint: Hamiltonian Cycle is $NP$-Complete.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11505 Ask a Question Download Related Notes/Documents
