Motivated by an application in condensed matter physics and quantum information theory, we prove that every non-null even-hole-free claw-free graph has a simplicial clique, that is, a clique K such that for every vertex v∈K, the set of neighbours of v outside of K is a clique. In fact, we prove the existence of a simplicial clique in a more general class of graphs defined by forbidden induced subgraphs.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Induced subgraphs
- Simplicial clique