Saturation Numbers for Trees
Saturation Numbers for Trees
复制标题
DOI：
10.37236/180
复制
发表时间：
2009-07
期刊：
影响因子：
--
通讯作者：
J. Faudree;R. Faudree;R. Gould;M. Jacobson
中科院分区：
文献类型：
--
作者：
J. Faudree;R. Faudree;R. Gould;M. Jacobson
对于固定图 $H$，如果 $G$ 中没有 $H$ 的副本，则图 $G$ 是 $H$ 饱和的，但对于任何边 $e \notin G$，$G + e$ 中都有 $H$ 的副本。 $n$ 阶的 $H$ 饱和图的集合用 ${\bf SAT}(n,H)$ 表示，饱和数 ${\bf sat}(n, H),$ 是 ${\bf SAT}(n,H)$ 图中的最小边数。令 $T_k$ 为一棵有 $k$ 个顶点的树。某些树族的饱和度数 ${\bf sat}(n,T_k)$ 将被精确确定。将识别 ${\bf sat}(n, T_k) < n$ 的某些树类，并且将呈现 ${\bf SAT}(n,T_k)$ 中的图是森林的树 $T_k$。此外，还将呈现 ${\bf sat}(n,T_k) \geq n$ 的树族。将给出所有树类别的 ${\bf sat}(n,T_k)$ 的最大值和最小值。我们将讨论树的 ${\bf sat}(n,T_k)$ 和 ${\bf SAT} (n,T_k)$ 的一些性质。
For a fixed graph $H$, a graph $G$ is $H$-saturated if there is no copy of $H$ in $G$, but for any edge $e \notin G$, there is a copy of $H$ in $G + e$. The collection of $H$-saturated graphs of order $n$ is denoted by ${\bf SAT}(n,H)$, and the saturation number , ${\bf sat}(n, H),$ is the minimum number of edges in a graph in ${\bf SAT}(n,H)$. Let $T_k$ be a tree on $k$ vertices. The saturation numbers ${\bf sat}(n,T_k)$ for some families of trees will be determined precisely. Some classes of trees for which ${\bf sat}(n, T_k) < n$ will be identified, and trees $T_k$ in which graphs in ${\bf SAT}(n,T_k)$ are forests will be presented. Also, families of trees for which ${\bf sat}(n,T_k) \geq n$ will be presented. The maximum and minimum values of ${\bf sat}(n,T_k)$ for the class of all trees will be given. Some properties of ${\bf sat}(n,T_k)$ and ${\bf SAT} (n,T_k)$ for trees will be discussed.