Abstract
A \emph{wheel} is a graph made of a cycle of length at least~4 together with a vertex that has at least three neighbors in the cycle. We prove that the problem whose instance is a graph and whose question is "does contains a wheel as an induced subgraph" is NP-complete. We also settle the complexity of several similar problems.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.