论文标题
饱和问题有规律性限制
Saturation problems with regularity constraints
论文作者
论文摘要
对于图$ f $，我们说另一个图$ g $是$ f $ - 饱和，如果$ g $是$ f $ - f $ - f $ - f $ - $ g $，将任何边缘添加到$ g $都会创建$ f $的副本。我们研究给定的图形$ f $和整数$ n $，无论是否存在常规$ n $ vertex $ f $饱和图，如果这样做，则该图的最小边缘数量是多少。我们主要关注$ f $是完整图的情况，例如，在$ n $顶点上存在$ k_3 $饱和的常规图。 我们还研究了这个问题的两个放松版本：当我们只要求不应该存在$ g $的常规$ f $ fule-free Supergraph时，或者当我们丢弃$ f $ fo $的条件时，只需要任何新添加的边缘就应该创建$ f $的新副本。
For a graph $F$, we say that another graph $G$ is $F$-saturated, if $G$ is $F$-free and adding any edge to $G$ would create a copy of $F$. We study for a given graph $F$ and integer $n$ whether there exists a regular $n$-vertex $F$-saturated graph, and if it does, what is the smallest number of edges of such a graph. We mainly focus on the case when $F$ is a complete graph and prove for example that there exists a $K_3$-saturated regular graph on $n$ vertices for every large enough $n$. We also study two relaxed versions of the problem: when we only require that no regular $F$-free supergraph of $G$ should exist or when we drop the $F$-free condition and only require that any newly added edge should create a new copy of $F$.
