| Autor: |
Diot, Emilie, Tavenas, Sébastien, Trotignon, Nicolas |
| Rok vydání: |
2013 |
| Předmět: |
|
| Zdroj: |
Applicable Analysis and Discrete Mathematics, 8:111-122, 2014 |
| Druh dokumentu: |
Working Paper |
| DOI: |
10.2298/AADM131128023D |
| Popis: |
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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
