Detecting wheels
classification
💻 cs.DM
math.CO
keywords
cyclegraphleastwheelwhosecomplexitycontainsdetecting
read the original 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 $G$ and whose question is "does $G$ contains a wheel as an induced subgraph" is NP-complete. We also settle the complexity of several similar problems.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.