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

Vojtěch Dvořák¹

¹University of Cambridge

The electronic journal of combinatorics, Tome 27 (2020) no. 4

Résumé

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 \geqslant 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 \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.

Détail

DOI : 10.37236/9579

Classification : 05C75
Mots-clés : saturation, induced subgraphs, Boolean formulas