Induced Saturation of $P_6$

Abstract

A graph $G$ is called $H$-induced-saturated if $G$ does not contain an induced copy of $H$, but removing any edge from $G$ creates an induced copy of $H$ and adding any edge of $G^c$ to $G$ creates an induced copy of $H$. Martin and Smith showed that there does not exist a $P_4$-induced-saturated graph, where $P_4$ is the path on 4 vertices. Axenovich and Csikós studied related questions, and asked if there exists a $P_n$-induced-saturated graph for any $n\ge 5$. Our aim in this short note is to show that there exists a $P_6$-induced-saturated graph.

Cited by in corpus (1)

• On induced saturation for paths