arXiv Open Access 2013

Detecting wheels

Emilie Diot Sébastien Tavenas Nicolas Trotignon

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DM math.CO

Penulis (3)

Emilie Diot

Sébastien Tavenas

Nicolas Trotignon

Format Sitasi

APA MLA BibTeX

Diot, E., Tavenas, S., Trotignon, N. (2013). Detecting wheels. https://arxiv.org/abs/1308.6433

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2013
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓