Abstract
A theta in a graph is an induced subgraph consisting of two nonadjacent vertices joined by three disjoint paths. A prism in a graph is an induced subgraph consisting of two disjoint triangles joined by three disjoint paths. This paper gives a polynomial-time algorithm to test whether a graph has an induced subgraph that is either a prism or a theta.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1164-1186 |
| Number of pages | 23 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 22 |
| Issue number | 3 |
| DOIs | |
| State | Published - 2008 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Mathematics
Keywords
- Detection algorithm
- Induced subgraph
- Prism
- Theta