\(P_n\)-induced-saturated graphs exist for all \(n \geqslant 6\) (Q2215464)

Summary: 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. \textit{R. R. Martin} and \textit{J. J. Smith} [Discrete Math. 312, No. 21, 3096--3106 (2012; Zbl 1251.05082)] 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\). \textit{M. Axenovich} and \textit{M. Csikós} [ibid. 342, No. 4, 1195--1212 (2019; Zbl 1405.05117)] ask for which integers \(n \geqslant 5\) do there exist \(P_n\)-induced-saturated graphs. \textit{E. Räty} [ibid. 343, No. 1, Article ID 111641, 3 p. (2020; Zbl 1429.05107)] constructed such a graph for \(n=6\), and \textit{E.-K. Cho} et al. [Eur. J. Comb. 91, Article ID 103204, 12 p. (2021; Zbl 1458.05170)] later constructed such graphs for all \(n=3k\) for \(k \geqslant 2\). We show by a different construction that \(P_n\)-induced-saturated graphs exist for all \(n \geqslant 6\), leaving only the case \(n=5\) open.