$P_n$-induced-saturated graphs exist for all $n\ge 6$

Abstract

Let $P_n$ be a path graph on $n$ vertices. We say that a graph $G$ is $P_n$-induced-saturated if $G$ contains no induced copy of $P_n$, but deleting any edge of $G$ as well as adding to $G$ any edge of $G^c$ creates such a copy. Martin and Smith (2012) showed that there is no $P_4$-induced-saturated graph. On the other hand, there trivially exist $P_n$-induced-saturated graphs for $n=2,3$. Axenovich and Csikós (2019) ask for which integers $n\ge 5$ do there exist $P_n$-induced-saturated graphs. Räty (2019) constructed such a graph for $n=6$, and Cho, Choi and Park (2019) later constructed such graphs for all $n=3k$ for $k\ge 2$. We show by a different construction that $P_n$-induced-saturated graphs exist for all $n\ge 6$, leaving only the case $n=5$ open.

5 pages, 2 figures; added note about the case n=5 being solved in previously unpublished work of different authors