2025-11-21T06:28:15.048096

Some results on minimum saturated graphs

Zhang, Cui, Hu et al.

Let $G$ be a graph and $\mathcal{F}$ be a family of graphs. We say a graph $G$ is $\mathcal{F}$-saturated if $G$ does not contain any member in $\mathcal{F}$ and for any $e\in E(\overline{G})$, $G+e$ creates a copy of some member in $ \mathcal{F}$. The saturation number of $\mathcal{F}$ is the minimum number of edges of an $\mathcal{F}$-saturated graphs with $n$ vertices, denoted by $\sat(n,\mathcal{F})$. If $\mathcal{F}=\{F\}$, then we write it as $\sat(n,F)$ for short. In this paper, we determine the exact value of $\sat(n,\{K_3,P_k\})$, and as its application, we obtain two bounds of $\sat(n,K_3\cup P_k)$ for $k\ge 10$ and sufficiently large $n$. Furthermore, $\sat(n,K_1\lor F)$ is determined, where $F$ is a linear forest without isolated vertices.

academic

Some results on minimum saturated graphs

基本信息

论文ID: 2510.10458
标题: Some results on minimum saturated graphs
作者: Chenke Zhang, Qing Cui, Jinze Hu, Erfei Yue, Shengjin Ji
分类: math.CO (组合数学)
发表时间: 2025年10月12日 (arXiv预印本)
论文链接: https://arxiv.org/abs/2510.10458

摘要

本文研究图的饱和数问题。对于图 $G$ 和图族 $\mathcal{F}$ ，如果 $G$ 不包含 $\mathcal{F}$ 中的任何成员，且对任意边 $e \in E(\overline{G})$ ， $G+e$ 都会创建 $\mathcal{F}$ 中某个成员的副本，则称 $G$ 是 $\mathcal{F}$ -饱和的。 $\mathcal{F}$ 的饱和数定义为具有 $n$ 个顶点的 $\mathcal{F}$ -饱和图的最小边数，记为 $\text{sat}(n,\mathcal{F})$ 。本文确定了 $\text{sat}(n,\{K_3,P_k\})$ 的精确值，并应用此结果获得了当 $k \geq 10$ 且 $n$ 充分大时 $\text{sat}(n,K_3 \cup P_k)$ 的两个界。此外，还确定了 $\text{sat}(n,K_1 \vee F)$ ，其中 $F$ 是不含孤立顶点的线性森林。

研究背景与动机

问题背景

饱和数问题是极值图论中的重要研究方向，由Erdős等人在1964年首次提出。该问题研究的核心是：对于给定的禁用子图族 $\mathcal{F}$ ，如何构造具有 $n$ 个顶点且边数最少的 $\mathcal{F}$ -饱和图。

研究意义

理论价值: 饱和数问题连接了极值图论和结构图论，为理解图的结构提供了新的视角
应用前景: 在网络设计、编码理论等领域有重要应用
技术挑战: 对于复合禁用结构（如 $K_3 \cup P_k$ ），现有方法难以给出精确结果

现有工作局限性

对于单个禁用图的饱和数已有较多研究，但对于图族的饱和数研究相对较少
$K_3 \cup P_k$ 的饱和数仅有上界结果，缺乏精确值
图的连接操作（如join操作）对饱和数的影响缺乏系统性研究

核心贡献

确定了 $\text{sat}(n,\{K_3,P_k\})$ 的精确值: 对于 $k \geq 10$ 且 $n \geq a_k^1$ ，证明了 $\text{sat}(n,\{K_3,P_k\}) = n - \lfloor n/a_k^1 \rfloor$
建立了 $\text{sat}(n,K_3 \cup P_k)$ 的紧界: 证明了 $2 + \text{sat}(n,\{K_3,P_k\}) \leq \text{sat}(n,K_3 \cup P_k) \leq 6 + \text{sat}(n,\{K_3,P_k\})$
解决了join图的饱和数问题: 完全确定了 $\text{sat}(n,K_1 \vee F) = (n-1) + \text{sat}(n-1,F)$ ，其中 $F$ 是不含孤立顶点的线性森林
引入了新的图结构分析方法: 通过"层"的概念系统分析了 $\{K_3,P_k\}$ -饱和树的结构

方法详解

任务定义

给定正整数 $n$ 和图族 $\mathcal{F}$ ，求具有 $n$ 个顶点的 $\mathcal{F}$ -饱和图的最小边数 $\text{sat}(n,\mathcal{F})$ ，并刻画所有达到此最小值的极值图。

核心技术方法

1. 层次结构分析

定义: 对于直径为 $s \geq 2$ 的树 $T$ ，设其最长路径为 $P_{s+1} = v_1v_2\cdots v_{s+1}$ ，定义：

1-层：包含中间的一个或两个顶点
$i$ -层：到1-层距离为 $i-1$ 的顶点集合

关键树结构:

$T_k$ : 经典的 $P_k$ -饱和树
$T_k^0$ : 新引入的 $\{K_3,P_k\}$ -饱和树，包含 $\lceil\frac{k-2}{2}\rceil$ 层
$T_k^1$ : 另一类 $\{K_3,P_k\}$ -饱和树，包含 $\lfloor\frac{k}{2}\rfloor$ 层

2. 饱和性验证方法

对于树 $T$ 和任意非邻接顶点对 $(u,v)$ ，通过以下策略证明 $T+uv$ 包含 $K_3$ 或 $P_k$ ：

情况分析:

若 $u,v$ 在同一路径上且 $l(u) \geq l(v)+3$ ，构造长度至少为 $k-1$ 的路径
若 $u,v$ 在不同路径上，找到公共顶点 $w$ ，构造相应的长路径

技术创新点

1. 最小饱和树的刻画

引理2.3: 对于 $k \geq 10$ ，如果 $T$ 是 $\{K_3,P_k\}$ -饱和树且不是星图，则 $T_k^0 \subseteq T$ 或 $T_k^1 \subseteq T$ ，且 $e(T_k^0) > e(T_k^1)$ 。

2. 分离策略

通过分别考虑禁用 $K_3$ 和 $P_k$ 的约束，巧妙地将复合问题分解为更易处理的子问题。

3. 构造性证明

构造具体的图 $G_0$ 和 $H_0$ ，证明其分别达到 $\text{sat}(n,\{K_3,P_k\})$ 和相应的上界。

主要结果

定理1.1 ( $\{K_3,P_k\}$ 的饱和数)

陈述: 若 $n \geq a_k^1$ 且 $k \geq 10$ ，则 $\text{sat}(n,\{K_3,P_k\}) = n - \lfloor n/a_k^1 \rfloor$ 。

证明思路:

构造图 $G_0 = G_1 \cup G_2 \cup \cdots \cup G_t$ ，其中 $G_1$ 是 $\{K_3,P_k\}$ -饱和树， $G_i$ 是 $T_k^1$ 的副本
证明 $G_0$ 是 $\{K_3,P_k\}$ -饱和的且边数为 $n - \lfloor n/a_k^1 \rfloor$
通过反证法证明任何 $\{K_3,P_k\}$ -饱和图的边数不少于此值