论文标题
$ p_ {n} $ - 所有$ n \ geq 6 $都存在诱导的饱和图
$P_{n}$-induced-saturated graphs exist for all $n \geq 6$
论文作者
论文摘要
令$ p_ {n} $为$ n $顶点上的路径图。我们说，如果$ g $包含$ p_ {n} $的诱导副本，则图$ g $是$ p_ {n} $ - 饱和的，但是删除$ g $的任何边缘，并添加到$ g $ g $ of $ g^{c} $的任何边缘都会创建此类副本。 Martin和Smith（2012）表明，没有$ p_ {4} $ - 诱发的图形。另一方面，存在$ p_ {n} $的$ p_ {n} $ - 诱导的饱和图，$ n = 2,3 $。 Axenovich andCsikós（2019）询问哪个整数$ n \ geq 5 $ do do存在$ p_ {n} $ - 诱导的饱和图。 Räty（2019）为$ n = 6 $构建了这样的图表，Cho，Choi和Park（2019）随后构建了所有$ n = 3k $的图形，for $ k \ geq 2 $。我们通过不同的结构显示$ p_ {n} $ - 所有$ n \ geq 6 $都存在诱导的饱和图，仅保留case $ n = 5 $打开。
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 \geq 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 \geq 2$. We show by a different construction that $P_{n}$-induced-saturated graphs exist for all $n \geq 6$, leaving only the case $n=5$ open.
