On induced saturation for paths

Abstract

For a graph H, a graph G is H-induced-saturated if G does not contain an induced copy of H, but either removing an arbitrary edge from G or adding an arbitrary non-edge to G creates an induced copy of H. Depending on the graph H, an H-induced-saturated graph does not necessarily exist. In fact, (Martin and Smith, 2012) showed that P4-induced-saturated graphs do not exist, where Pk denotes a path on k vertices. Given that it is easy to construct Pk-induced-saturated graphs for k∈{2,3}, (Axenovich and Csikós, 2019) asked whether such graphs exist or not for k≥5. Recently, Räty (2020) constructed a graph that is P6-induced-saturated. In this paper, we show that there exists a Pk-induced-saturated graph for infinitely many values of k. To be precise, for each positive integer n, we construct infinitely many P3n-induced-saturated graphs. Furthermore, we also show that the Kneser graph K(n,2) is P6-induced-saturated for every n≥5.