核心亮点
本文的核心目标是深入研究饱和数sat(n, St+1,t+1)的值，其中St+1,t+1被称为平衡双星，它由两个不相交的星图St+1（即K1,t）的中心通过一条边连接而成。我们证明了新的上下界：tn/2 + ε ≤ sat(n, St+1,t+1) ≤ tn/2 + (t+1)/2，其中当n ≡ 0 (mod t+1)时ε=0，否则ε=1。我们还确定了达到新上界的图结构。此外，当n ≡ 1 (mod (t+1))且n ≥ ((t+2)(t+3)2+ 6t - 5)/4时，我们确定了t=3和t=4情况下的精确饱和数值。
引言
对于一个固定的图H，如果图G不包含H的拷贝，但添加G的任何一条缺失边e都会在G+e中创建至少一个H的拷贝，则称G是H-饱和的。H的饱和数，记为sat(n, H)，是所有具有n个顶点的H-饱和图中边数的最小值。
饱和数的研究始于Erd?s、Hajnal和Moon的一个优美结果，他们计算了完全图的饱和数并确定了达到此数值的唯一图。受该结果推动，饱和数得到了广泛关注和发展。我们建议读者参阅Gould的一篇精彩的综述论文。
一般来说，对于一个图H，我们可以研究所有H-饱和图的共同性质来得到其饱和数的下界。另一方面，由于饱和数是所有H-饱和图中边数的最小值，构造一个边尽可能少的H-饱和图可以提供上界。然而，这始终具有挑战性，因为饱和数不具有单调性。Kászonyi和Tuza确定了一个星图Sk的饱和数sat(n, Sk)，它在所有具有k个顶点的树中具有最大的饱和数，而具有最小饱和数的树结构与星图非常相似，记为S'k，通过对Sk-1的一条边进行细分得到。即使Sk是S'k+1的子图，对于n>k≥4，我们有sat(n, Sk) > sat(n, S'k+1)。这个结果特别表明，我们不能简单地通过从已知的饱和图中删除边来构建新的饱和图，这大大增加了确定sat(n, H)精确值的难度。尽管文献中在很长一段时间内已知的结果很少，但近年来发表了几篇关于H=K3,3、H是一些不相交路径的并集或H是不相交的K1,k（其中k≥4）的并集的饱和数的论文。
我们在本文中的主要目标是研究sat(n, St+1,t+1)的值，其中St+1,t+1是一个平衡双星，通过连接两个不相交的星图K1,t的中心而获得。2009年，Faudree等人获得了sat(n, S3,3)的精确值。一般来说，他们给出了sat(n, St+1,t+1)的下界和上界：
定理1 [4] 对于n ≥ (t+1)3，有 (tn/2) ≤ sat(n, St+1,t+1) ≤ (tn/2) + (t(t+2))/2。
受上述结果启发，我们专注于改进定理1中的上下界，并探索当t≥3时sat(n, St+1,t+1)的更多精确值。令l(t) = ((t+2)(t+3)2+ 6t - 5)/4。我们的主要结果如下：
定理2 对于n ≥ l(t) 且 t ≥ 3，有 (tn/2) + ε ≤ sat(n, St+1,t+1) ≤ (tn/2) + (t+1)/2，其中当n ≡ 0 (mod t+1)时ε=0，否则ε=1。
注意到当t≥3时，(t+1)3≥ ((t+2)(t+3)2+ 6t - 5)/4，因此定理2改进了定理1中的上下界。实际上，我们对于上界的证明不需要条件n ≥ l(t)。以下两个定理表明，当t很大时，定理2中的上界可能比某些特定平衡双星的饱和数精确值大得多。
定理3 当t ≥ 3是奇数且n ≥ l(t)时，如果n ≡ 1 (mod (t+1))，则有sat(n, St+1,t+1) = (tn/2) + 3/2。
定理4 当t是偶数且n ≥ l(t)时，对于t ≥ 4，有sat(n, St+1,t+1) = (tn/2) + 1，当且仅当n ≡ 1 (mod (t+1))；或者对于t=4，有sat(n, St+1,t+1) = (tn/2) + 1，当且仅当n ≡ 2 (mod (t+1))。
以下两个定理表明，当t较小时，定理2中的上界可能非常接近某些特定平衡双星的饱和数精确值。
定理5 当n ≥ l(3)时，我们有：
(1) 如果n ≡ 0 (mod 4)，则sat(n, S4,4) = (3n)/2；
(2) 如果n ≡ 1, 3 (mod 4)，则sat(n, S4,4) = (3n)/2 + 3/2；
(3) 如果n ≡ 2 (mod 4)，则sat(n, S4,4) = (3n)/2 + 2。
定理6 当n ≥ l(4)时，我们有：
(1) 如果n ≡ 0 (mod 5)，则sat(n, S5,5) = 2n；
(2) 如果n ≡ 1, 2 (mod 5)，则sat(n, S5,5) = 2n + 1；
(3) 如果n ≡ 3, 4 (mod 5)，则sat(n, S5,5) = 2n + 2。
本文其余部分组织如下：在第2节中，我们介绍一些符号并给出证明主要结果所需的结构性引理。在第3节中，我们证明定理2，在第4节中，我们分别展示定理3、4、5和6中给出的图的饱和数精确值。
准备工作和一些引理
设G = (V(G), E(G))是一个图。对于任何e ? E(G)，G+e是通过添加e得到的图。设S是图G的一个顶点集。由S诱导的图，记为G[S]，是由顶点集S以及仅与S中顶点关联的所有边构成的G的子图。我们将用G-S表示G[V(G)-S]。对于G的任意顶点x，NG(x)表示x在G中的邻居集合。对于G的一个顶点子集S，NG(S) = {x ∈ V(G) | 存在某个y ∈ S使得xy ∈ E(G)}，e(G)表示G的边数。对于G的两个不相交顶点集S1, S2，我们用G[S1, S2; E']表示由顶点集S1∪ S2和边集E' ? {uv | u ∈ S1, v ∈ S2}构成的G的二分（部）子图。当上下文清楚时，我们省略下标G。
下界和上界
在本节中，我们将首先利用引理7和引理8构造具有e(G) = (tn/2) + ((t+1)/2)的St+1,t+1-饱和图，以建立定理2中的上界。请注意，我们的构造不需要条件n ≥ l(t)。令t ≥ 3且n = n' + k(t+1)，其中k = 0, 1, 2, ...，且2t+2 ≤ n' ≤ 3t+2。构造基于n'和t分为三种情况。
情况1. n'是奇数。
令n' = 2t + 1 + 2m (m ≥ 1)，并定义G1m为一个阶为n'的St+1,t+1-饱和图。G1m的结构如图1所示。
顶点集V(G1m) = {x, y} ∪ A ∪ B ∪ C，其中A = {a1, a2, ..., at-1}，B = {b1, b2, ..., bm}，C = {c1, c2, ..., cm}。边集E(G1m)包含以下边：顶点x与A ∪ B中的所有顶点相连；顶点y与A ∪ C中的所有顶点相连；集合A本身构成一个团（即A中任意两点相连）；对于每个i (1 ≤ i ≤ m)，顶点bi与ci相连；并且在B和C中，除了已描述的边之外没有其他边。可以验证G1m是St+1,t+1-饱和的，并且其边数为e(G1m) = (t * n')/2 + (t+1)/2。
情况2. n'是偶数且t是奇数。
令n' = 2t + 2 + 2m (m ≥ 0)，并类似地定义G2m。其构造与情况1类似，但顶点集包含额外的顶点，并调整连接关系以确保饱和性，边数同样满足e(G2m) = (t * n')/2 + (t+1)/2。
情况3. n'是偶数且t是偶数。
令n' = 2t + 2 + 2m (m ≥ 0)，定义G3m。其构造需特别处理以确保在t为偶数时的饱和性，最终边数仍满足e(G3m) = (t * n')/2 + (t+1)/2。
对于一般的n = n' + k(t+1)，我们可以通过取上述构造的Gim(i=1,2,3 取决于情况) 并与k个不相交的完全图Kt+1的并集相结合，得到一个新的St+1,t+1-饱和图G。可以证明G的边数为e(G) = (t * n)/2 + (t+1)/2。这就建立了定理2的上界。
对于下界，我们需要利用H-饱和图的结构性质。通过分析任意St+1,t+1-饱和图G，考虑其最大度顶点、非边（缺失边）的添加如何强制产生St+1,t+1，以及对顶点度数和图的分割进行精细的计数论证，我们可以推导出e(G) ≥ (t * n)/2 + ε，其中ε如定理2所定义。详细的证明涉及对G的顶点进行划分，并利用引理7和引理8中关于饱和图邻域性质的关键结论。
一些特定平衡双星的精确值
在本节中，我们将证明定理3、4、5和6，这些定理给出了一些特定平衡双星的饱和数精确值。
定理3和定理4的证明
图4展示了达到定理3和定理4中边数的构造，其中n = ((t+ε)/2)(t+1) + 1，当t为偶数时ε=2，当t为奇数时ε=3。实际上，图F1（见图4）由(t+ε)/2个拷贝的(Kt+1- e)和一个顶点w组成，w与每个Kt+1中边e的两个端点相邻。现在，对于n > ((t+ε)/2)(t+1) + 1，我们观察到F1∪ kKt+1是St+1,t+1-饱和的，并且其边数恰好等于定理3和4中声称的数值（即(tn)/2 + 3/2 对于t为奇数，或(tn)/2 + 1 对于t为偶数且满足同余条件）。为了证明这就是饱和数（即最小值），我们需要证明没有边数更少的St+1,t+1-饱和图存在。这通过反证法完成：假设存在一个边数更少的饱和图G'，然后利用G'必须满足的结构性质（例如，由引理7和8导出的性质）以及n满足的同余条件，推导出矛盾。关键的步骤在于分析G'中可能存在的“特殊”顶点（如高度数顶点或属于多个团的顶点）及其邻接关系，并通过精确的边计数证明e(G')不可能低于我们构造中给出的数值。对于定理4中“当且仅当”的部分，证明需要展示当n不满足所述同余条件时，饱和数的精确值会有所不同（通常更大），这可以通过提供对应情况的更优构造或证明下界提高来实现。
定理5和定理6的证明
对于t=3（S4,4）和t=4（S5,5）的情况，证明思路类似但更为具体。我们针对n模4或模5的不同余数，分别给出达到所述边数的精确图构造（这些构造通常是前述一般构造在特定t值下的实例化或变体）。然后，证明这些边数就是饱和数，即没有更少的边数可能。证明依赖于针对t=3和4时St+1,t+1结构的特殊性，对任意饱和图G进行详尽的结构分析。我们考虑G的最大度Δ(G)。通过引理7，我们知道Δ(G) ≤ t+1。然后我们区分Δ(G) = t+1 和 Δ(G) ≤ t的情况。对于每种情况，我们分析高度数顶点的邻域、图中团的结构、以及非边的存在如何迫使St+1,t+1出现。通过对顶点集合进行巧妙划分（例如，根据顶点度数、或根据它们是否属于某个特定的团或星的中心），并利用饱和性对每一部分顶点之间的边施加限制，我们可以得到一个关于G的总边数e(G)的下界不等式。将这个下界与n满足的特定同余条件相结合，经过一系列代数运算和情况排除，最终可以证明e(G)至少等于我们构造中给出的数值。对于t=3和4，可能的情况数量有限，使得这种逐一分析是可行的。证明中会大量用到图的基本性质（如握手引理）、饱和性的定义、以及之前章节中证明的关于St+1,t+1-饱和图的一般引理。
结论
在本文中，我们深入研究了平衡双星图St+1,t+1的饱和数问题。我们的主要贡献在于显著改进了已知的上下界，给出了更紧致的范围tn/2 + ε ≤ sat(n, St+1,t+1) ≤ tn/2 + (t+1)/2。我们不仅通过构造证明了上界是可以达到的，还解决了几类特定情况下的精确值问题。特别是，对于t=3和t=4，我们完全确定了sat(n, S4,4)和sat(n, S5,5)关于n模4或模5的余数的精确公式。对于更大的t，当n满足特定同余条件（n ≡ 1 mod (t+1)）时，我们也给出了精确值。这些结果丰富了我们对树状图，特别是双星图饱和行为的理解，并为解决更复杂图的饱和数问题提供了新的工具和视角。未来的工作可以探索非平衡双星或其他树状图的饱和数，或者进一步缩小一般t情况下上下界之间的间隙。
