Detecting wheels
Diot, Emilie · Tavenas, Sébastien · Trotignon, Nicolas
Original · EN
A 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.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.