Some results on minimum saturated graphs

Basic Information

• Paper ID: 2510.10458
• Title: Some results on minimum saturated graphs
• Authors: Chenke Zhang, Qing Cui, Jinze Hu, Erfei Yue, Shengjin Ji
• Classification: math.CO (Combinatorics)
• Publication Date: October 12, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.10458

Abstract

This paper investigates the saturation number problem for graphs. For a graph $G$ and a graph family $\mathcal{F}$, $G$ is called $\mathcal{F}$-saturated if $G$ contains no member of $\mathcal{F}$, and for any edge $e \in E(\overline{G})$, the graph $G+e$ contains a copy of some member of $\mathcal{F}$. The saturation number of $\mathcal{F}$ is defined as the minimum number of edges in an $\mathcal{F}$-saturated graph with $n$ vertices, denoted $\text{sat}(n,\mathcal{F})$. This paper determines the exact value of $\text{sat}(n,\{K_3,P_k\})$, and applies this result to obtain two bounds for $\text{sat}(n,K_3 \cup P_k)$ when $k \geq 10$ and $n$ is sufficiently large. Furthermore, the paper determines $\text{sat}(n,K_1 \vee F)$, where $F$ is a linear forest with no isolated vertices.

Research Background and Motivation

Problem Background

The saturation number problem is an important research direction in extremal graph theory, first introduced by Erdős and colleagues in 1964. The core of this problem is: for a given family of forbidden subgraphs $\mathcal{F}$, how to construct an $\mathcal{F}$-saturated graph with $n$ vertices and the minimum number of edges.

Research Significance

1. Theoretical Value: The saturation number problem connects extremal graph theory and structural graph theory, providing new perspectives for understanding graph structures
2. Application Prospects: Important applications in network design, coding theory, and related fields
3. Technical Challenges: For composite forbidden structures (such as $K_3 \cup P_k$), existing methods struggle to provide exact results

Limitations of Existing Work

• Saturation numbers for single forbidden graphs have been extensively studied, but research on saturation numbers for graph families is relatively limited
• Only upper bounds are known for the saturation number of $K_3 \cup P_k$, lacking exact values
• The effect of graph join operations on saturation numbers lacks systematic investigation

Core Contributions

1. Determined the exact value of $\text{sat}(n,\{K_3,P_k\})$: For $k \geq 10$ and $n \geq a_k^1$, proved that $\text{sat}(n,\{K_3,P_k\}) = n - \lfloor n/a_k^1 \rfloor$
2. Established tight bounds for $\text{sat}(n,K_3 \cup P_k)$: Proved that $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\})$
3. Resolved the saturation number problem for join graphs: Completely determined $\text{sat}(n,K_1 \vee F) = (n-1) + \text{sat}(n-1,F)$, where $F$ is a linear forest with no isolated vertices
4. Introduced new graph structure analysis methods: Systematically analyzed the structure of $\{K_3,P_k\}$-saturated trees through the concept of "layers"

Detailed Methodology

Problem Formulation

Given positive integers $n$ and a graph family $\mathcal{F}$, find the minimum number of edges in an $\mathcal{F}$-saturated graph with $n$ vertices, denoted $\text{sat}(n,\mathcal{F})$, and characterize all extremal graphs achieving this minimum.

Core Technical Methods

1. Hierarchical Structure Analysis

Definition: For a tree $T$ with diameter $s \geq 2$, let its longest path be $P_{s+1} = v_1v_2\cdots v_{s+1}$. Define:

• Layer 1: Contains one or two central vertices
• Layer $i$: The set of vertices at distance $i-1$ from Layer 1

Key Tree Structures:

• $T_k$: The classical $P_k$-saturated tree
• $T_k^0$: A newly introduced $\{K_3,P_k\}$-saturated tree containing $\lceil\frac{k-2}{2}\rceil$ layers
• $T_k^1$: Another class of $\{K_3,P_k\}$-saturated trees containing $\lfloor\frac{k}{2}\rfloor$ layers

2. Saturation Verification Method

For a tree $T$ and any non-adjacent vertex pair $(u,v)$, prove that $T+uv$ contains $K_3$ or $P_k$ through the following strategy:

Case Analysis:

• If $u,v$ lie on the same path and $l(u) \geq l(v)+3$, construct a path of length at least $k-1$
• If $u,v$ lie on different paths, find a common vertex $w$ and construct the corresponding long path

Technical Innovations

1. Characterization of Minimum Saturated Trees

Lemma 2.3: For $k \geq 10$, if $T$ is a $\{K_3,P_k\}$-saturated tree that is not a star, then $T_k^0 \subseteq T$ or $T_k^1 \subseteq T$, and $e(T_k^0) > e(T_k^1)$.

2. Separation Strategy

By separately considering the constraints of forbidding $K_3$ and $P_k$, cleverly decompose the composite problem into more tractable subproblems.

3. Constructive Proof

Construct specific graphs $G_0$ and $H_0$, proving they achieve $\text{sat}(n,\{K_3,P_k\})$ and the corresponding upper bounds, respectively.

Main Results

Theorem 1.1 (Saturation Number of $\{K_3,P_k\}$)

Statement: If $n \geq a_k^1$ and $k \geq 10$, then $\text{sat}(n,\{K_3,P_k\}) = n - \lfloor n/a_k^1 \rfloor$.

Proof Strategy:

1. Construct graph $G_0 = G_1 \cup G_2 \cup \cdots \cup G_t$, where $G_1$ is a $\{K_3,P_k\}$-saturated tree and $G_i$ are copies of $T_k^1$
2. Prove that $G_0$ is $\{K_3,P_k\}$-saturated and has $n - \lfloor n/a_k^1 \rfloor$ edges
3. Use proof by contradiction to show that any $\{K_3,P_k\}$-saturated graph has at least this many edges

Theorem 1.2 (Bounds for $K_3 \cup P_k$)

Statement: For $k \geq 10$ and $n$ sufficiently large, $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\})$

Proof Highlights:

• Upper Bound: Construct graph $H_0$ containing $K_4$ and multiple copies of $T_k^1$, proving it is $(K_3 \cup P_k)$-saturated
• Lower Bound: Analyze the structure of $(K_3 \cup P_k)$-saturated graphs, utilizing connectivity and degree constraints

Theorem 1.3 (Saturation Number of Join Graphs)

Statement: Let $F$ be a linear forest with no isolated vertices. Then for sufficiently large $n$, $\text{sat}(n,K_1 \vee F) = (n-1) + \text{sat}(n-1,F)$

Proof Strategy:

1. Prove that any $(K_1 \vee F)$-saturated graph has diameter 2
2. Analyze the maximum degree, proving the existence of a central vertex
3. Use Lemma 4.2 to establish correspondence with $F$-saturated graphs

Technical Details Analysis

Proof of Key Lemmas

Core of Lemma 2.3's Proof:

• Determine $k-3 \leq s \leq k-2$ through diameter constraints
• Discuss cases $s = k-3$ and $s = k-2$ separately
• Derive degree constraints of trees using saturation conditions

Precision of Constructions

The extremal graphs constructed in the paper are not arbitrary but optimized according to the following principles:

1. Minimality: Each component is the minimum solution to the corresponding problem
2. Saturation: Adding any edge produces a forbidden structure
3. Modularity: Facilitates computation and analysis

Experimental Verification and Examples

Small Parameter Cases

For $k \leq 9$, the paper provides the corresponding minimum $\{K_3,P_k\}$-saturated trees in Proposition 5.1:

• $k = 5$: $T_1$
• $k = 6$: $T_2$ or $T_3$
• $7 \leq k \leq 8$: $T_k^0$
• $k = 9$: $T_9^1$ or $T_9^0$

Illustrative Examples

The paper provides multiple figures (Figures 1-5) clearly displaying various tree structures, facilitating understanding of abstract definitions.

Related Work

Historical Development

1. Erdős et al. (1964): First introduced the saturation number concept, determined $\text{sat}(n,K_p)$
2. Kászonyi and Tuza (1986): Studied saturation numbers of stars, paths, and other basic graphs
3. Recent Work: Chen et al. studied saturation numbers of forests; Li and Xu studied connected $K_3 \cup P_k$-saturated graphs

Positioning of This Paper's Contribution

This paper makes important progress in the following aspects:

• First exact determination of saturation numbers for $\{K_3,P_k\}$
• Improved upper bounds for saturation numbers of $K_3 \cup P_k$
• Systematically resolved saturation number problems for join graphs

Conclusions and Discussion

Main Conclusions

1. Completely resolved the saturation number problem for $\{K_3,P_k\}$ when $k \geq 10$
2. Provided tight bounds for saturation numbers of $K_3 \cup P_k$
3. Established general principles for how join operations affect saturation numbers

Limitations

1. Parameter Restrictions: Main results apply only to $k \geq 10$
2. Missing Exact Values: Exact values for $K_3 \cup P_k$ remain undetermined
3. Technical Complexity: Small parameter cases require separate treatment

Future Directions

The paper raises important open problems: Problem 2: For $k \geq 10$, does $\text{sat}(n,K_3 \cup P_k) = 6 + \text{sat}(n,\{K_3,P_k\})$ hold?

In-Depth Evaluation

Strengths

1. Theoretical Depth: Introduces hierarchical analysis methods, providing new tools for studying saturated graph structures
2. Technical Innovation: Cleverly separates composite constraints, simplifying complex problems
3. Complete Results: Not only provides numerical results but also characterizes all extremal graphs
4. Rigorous Proofs: Exhaustive case discussions with refined technical handling

Weaknesses

1. Lack of Uniformity: Different parameter ranges require different treatment methods
2. Computational Complexity: Parameter expressions for tree structures are relatively complex
3. Open Problems: Core conjecture (Problem 2) remains unresolved

Impact

1. Academic Value: Provides important advancement for saturation number theory
2. Methodological Contribution: Hierarchical analysis methods applicable to other extremal problems
3. Practical Utility: Provides theoretical support for network topology optimization and related applications

Applicable Scenarios

This research is applicable to:

• Theoretical research in extremal graph theory
• Network topology optimization design
• Graph construction problems in coding theory
• Constraint satisfaction problems in combinatorial optimization

References

The paper cites 27 related references, covering the main development trajectory of saturation number theory, including:

• Classical foundational works (Erdős, Bollobás, et al.)
• Recent important advances (Chen, Hu, et al.)
• Related technical methods (Cameron, Puleo, et al.)

Overall Assessment: This is a high-quality theoretical paper in combinatorial mathematics that achieves substantial progress in the important research direction of saturation numbers. The technical methods are innovative, the results have significant theoretical value, and they provide a solid foundation for subsequent research.