pith. sign in

arxiv: 2606.22011 · v2 · pith:UPY6OK5Knew · submitted 2026-06-20 · 🧮 math.CO

Saturation numbers for joins of graphs and characterization of extremal graphs

Xinying Hua , Yuejian Peng This is my paper

Pith reviewed 2026-06-26 11:47 UTC · model grok-4.3

classification 🧮 math.CO
keywords saturation numberH-saturated graphgraph joinK1 join Fextremal graphsisolated verticesmatching
0
0 comments X

The pith

Saturation number of K1 joined to F equals n-1 plus sat(n-1,F) when F contains a matching plus any isolates, but the equality fails for F equal to K_{p-1} union one isolate when p is at least 4.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper computes exact values of the saturation number sat(n, K1 ∨ F) for families of F that include isolated vertices. It shows the known upper bound sat(n, K1 ∨ F) ≤ n-1 + sat(n-1, F) is achieved with equality, together with complete lists of the minimum-edge extremal graphs, precisely when F is K2 union q isolated vertices or 2K2 union q isolated vertices. For F equal to K_{p-1} union one isolated vertex the same recursive equality does not hold once p reaches 4, and the exact saturation number is obtained instead by direct counting. The proofs proceed by exhaustive structural case analysis on the possible neighborhoods and components in any candidate saturated graph.

Core claim

The authors prove that sat(n, K1 ∨ (K_{p-1} ∪ K1)) admits an explicit closed form for every p, that this form differs from n-1 + sat(n-1, K_{p-1} ∪ K1) when p ≥ 4, and that the equality sat(n, K1 ∨ F) = n-1 + sat(n-1, F) together with the full list of extremal graphs holds for every q ≥ 1 when F is K2 ∪ qK1 or 2K2 ∪ qK1.

What carries the argument

The recursive comparison sat(n, K1 ∨ F) versus n-1 + sat(n-1, F), whose equality or failure is decided by whether the isolated vertices in F permit every minimum saturated graph on n-1 vertices to be extended by a single universal vertex without creating an earlier copy of the join.

If this is right

  • sat(n, K1 ∨ (K2 ∪ qK1)) equals n-1 plus the saturation number of K2 ∪ qK1 on n-1 vertices.
  • sat(n, K1 ∨ (2K2 ∪ qK1)) equals n-1 plus the saturation number of 2K2 ∪ qK1 on n-1 vertices.
  • All minimum saturated graphs are obtained by taking a minimum saturated graph on the non-isolated part and adding a universal vertex together with the appropriate isolated vertices.
  • The recursive upper bound is not tight once the non-isolated part of F becomes a clique on three or more vertices plus an isolate.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The equality appears to require that F contain at most two edges outside its isolated vertices.
  • The same case-analysis technique may apply to other F whose components are paths or cycles of bounded length plus isolates.
  • The explicit lists of extremal graphs supply concrete constructions that can be checked directly against the saturation definition.

Load-bearing premise

The graphs F under consideration have only a very small number of edges or a single clique plus isolates, so that every possible way an added edge could create a forbidden join can be enumerated by cases.

What would settle it

An n-vertex graph with strictly fewer than the claimed number of edges that contains no copy of K1 ∨ F yet becomes a copy of K1 ∨ F upon addition of any missing edge, for one of the families where equality is asserted.

Figures

Figures reproduced from arXiv: 2606.22011 by Xinying Hua, Yuejian Peng.

Figure 1
Figure 1. Figure 1: The local structure of G. If G contains K1 ∨2K2 as a subgraph, see [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The case of |V (T) ∩ V (T1)| = 1. Thus, |V (T1) ∩ V (T2)| = 2. Recall that |{v, u2, u3} ∩ V (T1)| = 1, then vu2 ∈/ E(T1). So, V (T1)∩V (T2) = {v, u1} or V (T1)∩V (T2) = {u1, u2}. Assume that V (T1)∩V (T2) = {v, u1}, as shown in [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Some 5-vertex graphs. Theorem 6.1. Let n ≥ 5. If n = 6 or 7, then sat(n, G5) = n. Otherwise, sat(n, G5) = n − 1. Proof. Let Tp(p ≥ 6) be the graph of order p formed by a triangle with each of its three vertices adjacent to one leaf, and the remaining p − 3 leaves attached to a single vertex of the triangle. Obviously, Tn(n ≥ 6) is G5-saturated. So, if n ≥ 6, then sat(n, G5) ≤ n. In particular, when n = 5, … view at source ↗
Figure 4
Figure 4. Figure 4: C4-saturated graphs with ⌊ 3n−5 2 ⌋ edges. (a): n even, (b) and (c): n odd. Theorem 6.3. Let n ≥ 5. Then sat(n, C+ 4 ) = ⌊ 3n−5 2 ⌋. Proof. It is clear that the graphs in [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗
read the original abstract

A graph $G$ is $H$-saturated if $G$ contains no $H$-copy as a subgraph, but adding any edge between two non-adjacent vertices in $G$ creates a copy of $H$. The saturation number $\mathrm{sat}(n,H)$ is the minimum number of edges in an $n$-vertex $H$-saturated graph. Saturation number for the join of a vertex and a graph $F$, denoted by $K_1\vee F$, has received considerable attention. Cameron and Puleo [Discrete Math. 345 (2022), 112867] showed that $\mathrm{sat}(n,K_1 \vee F)\le n-1+\mathrm{sat}(n-1, F)$ for all $n > |V(F)|$. A natural question is to ask when the above equality holds. Existing results for $\mathrm{sat}(n,K_1 \vee F)$ always constrain that a non-empty graph $F$ contains no isolated vertex. In this paper, we investigate the saturation number of $K_1\vee F$ when a non-empty graph $F$ contains an isolated vertex. We first determine the saturation number for $K_1\vee F$ when $F=K_{p-1}\cup K_1$. When $p=3$, we extend the result to any number of isolated vertices, and determine the saturation number for $K_1\vee F$ when $F=K_{2}\cup qK_1$, or $F=2K_{2}\cup qK_1$ for any $q\ge 1$. Moreover, all minimum saturated graphs are fully characterized. In our results, $\mathrm{sat}(n,K_1 \vee F)= n-1+\mathrm{sat}(n-1, F)$ holds when $F=K_2\cup qK_1$, or $F=2K_2\cup qK_1$ for any $q\ge 1$; but fails when $F=K_{p-1}\cup K_1$ for $p\ge 4$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper determines the saturation numbers sat(n, K_1 ∨ F) and fully characterizes the extremal graphs for three families of F containing isolated vertices: F = K_{p-1} ∪ K_1 (p fixed), F = K_2 ∪ q K_1 (any q ≥ 1), and F = 2K_2 ∪ q K_1 (any q ≥ 1). It proves that the recursive relation sat(n, K_1 ∨ F) = n-1 + sat(n-1, F) holds exactly for the latter two families and fails for the first family when p ≥ 4, extending prior work of Cameron and Puleo that assumed F has no isolated vertices.

Significance. If the determinations and characterizations hold, the results supply exact closed-form saturation numbers together with complete lists of minimum saturated graphs for joins involving graphs with isolates. This clarifies the boundary of the Cameron-Puleo inequality and demonstrates that exhaustive structural case analysis can succeed for these restricted families, advancing the theory of saturation numbers for non-complete forbidden subgraphs.

minor comments (2)
  1. The statement of the main theorems could explicitly reference the prior Cameron-Puleo bound in the introduction to make the improvement clearer.
  2. Notation for the join K_1 ∨ F is consistent, but a short reminder of the definition of saturation (no H-subgraph but every added edge creates one) would aid readers unfamiliar with the area.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and for recommending acceptance. We appreciate the recognition of how our results clarify the boundary of the Cameron-Puleo relation for graphs F containing isolated vertices.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper determines sat(n, K1 ∨ F) and characterizes extremal graphs for three explicit families of F (K_{p-1} ∪ K1, K2 ∪ qK1, 2K2 ∪ qK1) via exhaustive case analysis on the structure of minimum H-saturated graphs. It builds on the external inequality sat(n, K1 ∨ F) ≤ n-1 + sat(n-1, F) from Cameron-Puleo (different authors) and reports when equality holds or fails, without any self-definitional reductions, fitted parameters renamed as predictions, self-citation load-bearing steps, or imported uniqueness theorems. All claims rest on direct structural enumeration for the chosen F, making the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard definition of H-saturation and the join operation K1 ∨ F; no free parameters, invented entities, or non-standard axioms are indicated in the abstract.

axioms (1)
  • standard math Standard definitions of H-saturated graphs, saturation number sat(n,H), and the join operation K1 ∨ F from extremal graph theory.
    The entire investigation is built on these established notions.

pith-pipeline@v0.9.1-grok · 5935 in / 1341 out tokens · 20682 ms · 2026-06-26T11:47:39.024092+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references

  1. [1]

    Cameron and G.J

    A. Cameron and G.J. Puleo, A lower bound on the saturation number, and graphs for which it is sharp, Discrete Math. 345 (2022) 112867

    2022

  2. [2]

    S. Cao, H. Lei, X. Lian, S. Yao, and J. Zhang, Saturation number for tPk with k < 6, Discrete Appl. Math. 325 (2023) 108–119

    2023

  3. [3]

    Chen and X

    F. Chen and X. Yuan, Some results on the saturation number for unions of cliques, Discrete Math. 347 (2024) 113868

    2024

  4. [4]

    G. Chen, R. Faudree, and R. Gould, Saturation numbers of books, Electron. J. Combin. 15 (2008) #R118

    2008

  5. [5]

    Chen, Minimum C5-saturated graphs

    Y. Chen, Minimum C5-saturated graphs. J. Graph Theory 61(2) (2009) 111–126

    2009

  6. [6]

    Chen, All minimum C5-saturated graphs, J

    Y. Chen, All minimum C5-saturated graphs, J. Graph Theory 67(1) (2011) 9–26

    2011

  7. [7]

    Chen, Minimum K2,3-saturated graphs, J

    Y. Chen, Minimum K2,3-saturated graphs, J. Graph Theory 76(4)(2014) 309–322

    2014

  8. [8]

    Chen, J.R

    G. Chen, J.R. Faudree, R.J. Faudree, R.J. Gould, M.S. Jacobson, and C. Magnant, Results and problems on saturation numbers for linear forests, Bull. Inst. Combin. Appl. 75 (2015) 29–46

    2015

  9. [9]

    Currie, J.R

    B.L. Currie, J.R. Faudree, R.J. Faudree, and J.R. Schmitt, A survey of minimum saturated graphs, Electron. J. Comb. (2021) #DS19

    2021

  10. [10]

    Erdős, A

    P. Erdős, A. Hajnal, and J.W. Moon, A problem in graph theory, Amer. Math. Monthly 71 (1964) 1107–1110

    1964

  11. [11]

    Fan and C

    Q. Fan and C. Wang, Saturation numbers for linear forests P5 ∪ tP2, Graphs Combin. 31 (2015) 2193–2200

    2015

  12. [12]

    Faudree, R.J

    J. Faudree, R.J. Faudree, R.J. Gould, and M.S. Jacobson, Saturation numbers for trees, Electron. J. Comb. 16 (2009) #R91. 17

    2009

  13. [13]

    Faudree, R.J

    J.R. Faudree, R.J. Faudree, and J.R. Schmitt, A survey of minimum saturated graphs, Electron. J. Comb. 18 (2011) #DS19

    2011

  14. [14]

    Faudree, M

    R.J. Faudree, M. Ferrara, R.J. Gould, and M.S. Jacobson, tKp-saturated graphs of minimum size, Discrete Math. 309 (2009) 5870–5876

    2009

  15. [15]

    Faudree and R.J

    R.J. Faudree and R.J. Gould, Saturation numbers for nearly complete graphs, Graphs Comb. 29 (2013) 429–448

    2013

  16. [16]

    He and M

    Z. He and M. Lu, Saturation number of tKl,l,l in the complete tripartite graph, Electron. J. Comb. 28 (2021) #P4.20

    2021

  17. [17]

    Z. He, M. Lu, and Z. Lv, Minimum tP3-saturation graphs, Discrete Appl. Math. 327(2023) 148– 156

    2023

  18. [18]

    S. Hu, Z. Luo, and Y. Peng, Saturation numbers of joins of graphs, Discrete Appl. Math. 357 (2024) 300–309

    2024

  19. [19]

    J. Hu, S. Ji, and Q. Cui, (K1 ∨ Pt)-saturated graphs with minimum number of edges. J. Combin. Optim. 49 (2025) 23

    2025

  20. [20]

    Hua and Y

    X. Hua and Y. Peng, Minimum bull-saturated graphs, Discrete Math. 349 (2026) 114674

    2026

  21. [21]

    Hua and Y

    X. Hua and Y. Peng, Saturation numbers for joins of graphs, Manuscript

  22. [22]

    Huang, H

    S. Huang, H. Lei, Y. Shi, and J. Zhang, The saturation number of K3,3, Discrete Math. 347 (2024) 113794

    2024

  23. [23]

    Kászonyi and Z

    L. Kászonyi and Z. Tuza, Saturated graphs with minimal number of edges, J. Graph Theory, 10(2) (1986) 203–210

    1986

  24. [24]

    Y. Lan, Y. Shi, Y. Wang, and J. Zhang, The saturation number of C6, Discrete Math. 348 (2025)114504

    2025

  25. [25]

    Z. Lv, Z. He, and M. Lu, Saturation numbers for disjoint stars, J. Combin. Optim. 45 (2023) 11

    2023

  26. [26]

    Y. Ma, X. Hou, D. Hei, and J. Gao, Minimizing the number of edges in C≥r-saturated graphs, Discrete Math. 344 (2021) 112565

    2021

  27. [27]

    L.T. Ollmann, K2,2-saturated graphs with a minimal number of edges, Proceedings of the Third Southeastern Conference on Combinatorics, Graph Theory, and Computing, Florida Atlantic University, Boca Raton, FL, (1972) 367–392. 18

    1972

  28. [28]

    N. Song, J. Hu, S. Ji, and Q. Cui, The saturation number of W4, Discrete Math. 349 (2026) 115107

    2026

  29. [29]

    Tuza, C4-saturated graphs of minimum size, Acta

    Z. Tuza, C4-saturated graphs of minimum size, Acta. Univ. Carolin. Math. Phys. 30 (1989) 161–167

    1989

  30. [30]

    Y. Qiu, Z. He, M. Lu, and Y. Xu, The saturation number of wheels, Discrete Appl. Math. 379 (2026) 542–550

    2026

  31. [31]

    H. Zhu, R. Hao, and Z. He, Minimum saturated graphs for unions of cliques, Discrete Math. 348 (2025) 114530. 19

    2025