P_{n}-induced-saturated graphs exist for all n \geq 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'{o}s (2019) ask for which integers

n g e q 5

do there exist

P_{n}

-induced-saturated graphs. R"{a}ty (2019) constructed such a graph for

n = 6

, and Cho, Choi and Park (2019) later constructed such graphs for all

n = 3 k

for

k g e q 2

. We show by a different construction that

P_{n}

-induced-saturated graphs exist for all

n g e q 6

, leaving only the case

n = 5

open.

This page was built for publication: $P_{n}$-induced-saturated graphs exist for all $n \geq 6$