pith. sign in

arxiv: 2606.22006 · v2 · pith:7OPZZHVAnew · submitted 2026-06-20 · 🧮 math.CO

Saturation numbers of some joins of graphs

Xinying Hua , Yuejian Peng This is my paper

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

classification 🧮 math.CO
keywords saturation numbergraph joinK1 join Fsaturated graphsextremal graph theoryisolated verticesforbidden subgraphs
0
0 comments X

The pith

The saturation number sat(n, K1 ∨ F) equals n-1 + sat(n-1, F) when F is a near-triangle plus any number of isolates, but is strictly smaller when F is a near-clique on four or more vertices plus one isolate.

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

This paper calculates the exact minimum number of edges in an n-vertex graph that contains no copy of K1 joined to F, yet contains such a copy after any missing edge is added. It examines the case where F itself includes isolated vertices, a situation excluded from earlier work on the same join. When F consists of a triangle minus one edge union any number of isolated vertices, the minimum edge count is achieved exactly by the construction that adds one new vertex joined to all others in a minimum F-saturated graph on n-1 vertices. When F is instead a complete graph on p-1 vertices minus one edge union a single isolated vertex for p at least 5, the same construction does not minimize the edges, so the saturation number lies strictly below the bound. The results therefore separate the behavior of the join saturation number according to the non-isolated part of F.

Core claim

We determine the exact value of sat(n, K1 ∨ F) when F=K3^- ∪ sK1 (s≥1) or F=K_{p-1}^- ∪ K1 (p≥5). In our results, sat(n,K1 ∨ F)=n-1+sat(n-1,F) holds when F=K3^- ∪ sK1 for any s≥1, but fails when F=K_{p-1}^- ∪ K1 for p≥5.

What carries the argument

The comparison of sat(n, K1 ∨ F) to the quantity n-1 + sat(n-1, F), using constructions that add a vertex while exploiting isolated vertices in F to reach the minimum edge count that still forces a K1 ∨ F copy upon any added edge.

If this is right

  • The upper bound sat(n, K1 ∨ F) ≤ n-1 + sat(n-1, F) is achieved exactly for every F of the form K3^- ∪ sK1.
  • For every F of the form K_{p-1}^- ∪ K1 with p≥5 the saturation number is strictly smaller than n-1 + sat(n-1, F).
  • The exact saturation number can be computed from the saturation number of the smaller graph F precisely when the non-isolated component of F is a triangle minus an edge.
  • Isolated vertices in F change the saturation behavior of the join in a way that depends on the size of the non-isolated component.

Where Pith is reading between the lines

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

  • The pattern suggests that the equality holds exactly when the non-isolated part of F is small enough that its own saturation graphs can be extended without extra edges.
  • The same distinction between equality and strict inequality may appear for other near-complete graphs joined with varying numbers of isolates.
  • A complete classification of F for which the equality holds could be obtained by examining all small non-isolated components paired with isolates.
  • These results indicate that adding isolated vertices to F can sometimes reduce the relative cost of saturation for the join operation.

Load-bearing premise

The specific structures of these F graphs that contain isolated vertices permit constructions that achieve the claimed minimum edge count while keeping the graph saturated for the join.

What would settle it

Finding any graph on n vertices with fewer than the claimed number of edges that still contains no K1 ∨ F subgraph yet gains one upon addition of any missing edge would show the stated exact value is too high.

Figures

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

Figure 1
Figure 1. Figure 1: Two graphs occurred in the proof of Subcase 1.2. [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The local structure of G in Lemma 4.4. Lemma 4.5. Let G be a disconnected K+1 p− -saturated graph of order n ≥ p + 1. Then all but at most one component of G are Kp-copies. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The K− p -copy My in G + vy. Since dMy (y) = p − 1, yz ∈ E(G). Recall our assumption that dV1∪B(y) = dV1 (y) = p − 3. Together with {v1, v2, . . . , vp−3} ⊆ NV1 (y), this gives z ∈ A. Then by Claim 4.1, G[NG[z]] ∼= K− p , say M′ . As v1, v2 ∈ NG(z) and v1v2 ∈ E(G), v1v2 ∈ E(M′ ). Then either dM′(v1) = p − 1 or dM′(v2) = p − 1. Assume that dM′(v1) = p − 1. Then M′ is a K− p -copy in G[NG[v1]]. Since G is Kp… view at source ↗
read the original abstract

Let $H$ be a graph. A graph $G$ is $H$-saturated if $G$ is $H$-free, but adding any edge between two non-adjacent vertices of $G$ yields an $H$-copy as a subgraph. The saturation number $\mathrm{sat}(n, H)$ is the minimum number of edges in an $H$-saturated graph on $n$ vertices. The saturation number for the join of a vertex and a graph $F$, denoted by $K_1\vee F$, has attracted considerable attention. Cameron and Puleo [Discrete Math. 345 (2022), 112867] proved that $\mathrm{sat}(n,K_1 \vee F)\le n-1+\mathrm{sat}(n-1, F)$ for $n > |V(F)|$. A natural question is when the above equality holds. Most existing results impose conditions on $F$ and assume that $F$ has no isolated vertices. Let $K_p^-$ be the graph obtained by deleting one edge from the complete graph $K_p$. In this paper, we investigate the saturation number of $K_1\vee F$ when $F$ contains isolated vertices, and determine the exact value of $\mathrm{sat}(n, K_1\vee F)$ when $F=K^-_{3}\cup sK_1(s\ge 1)$ or $F=K^-_{p-1}\cup K_1(p\ge 5)$. In our results, $\mathrm{sat}(n,K_1 \vee F)= n-1+\mathrm{sat}(n-1, F)$ holds when $F=K^-_{3}\cup sK_1$ for any $s\ge 1$, but fails when $F=K^-_{p-1}\cup K_1$ for $p\ge 5$.

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 / 3 minor

Summary. The manuscript determines the exact saturation numbers sat(n, K_1 ∨ F) for two families of graphs F that contain isolated vertices: F = K_3^- ∪ s K_1 for s ≥ 1, and F = K_{p-1}^- ∪ K_1 for p ≥ 5. It proves that the Cameron-Puleo upper bound sat(n, K_1 ∨ F) ≤ n-1 + sat(n-1, F) is achieved with equality for the first family but is strict for the second, with the proofs relying on explicit constructions that exploit the presence of the isolated vertices in F.

Significance. If the determinations hold, the work extends saturation theory for joins by handling the previously excluded case of isolate-containing F, providing concrete exact values and identifying a structural distinction between the two families. The explicit constructions achieving the minimum edge counts while preserving the saturation property constitute a clear contribution, as does the demonstration that the Cameron-Puleo bound is not always tight once isolates are permitted.

minor comments (3)
  1. The abstract states the main results clearly but does not indicate the theorem numbers or the precise formulas obtained; adding these would improve readability for readers scanning the paper.
  2. Section 1 (Introduction): the notation K_p^- is used without an immediate definition; a one-sentence definition on first use would aid readers.
  3. The paper would benefit from a short table summarizing the exact sat(n, K_1 ∨ F) expressions for both families side-by-side with the Cameron-Puleo bound.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive evaluation of the manuscript, including the recognition of its contribution in determining exact saturation numbers for joins involving isolate-containing graphs F and in distinguishing the tightness of the Cameron-Puleo bound between the two families considered. The recommendation for minor revision is noted.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper determines exact values of sat(n, K1 ∨ F) for two families of F containing isolated vertices, showing that the Cameron-Puleo upper bound sat(n,K1 ∨ F) ≤ n-1 + sat(n-1, F) is tight for F = K3^- ∪ sK1 but not for F = K_{p-1}^- ∪ K1. These determinations rest on explicit constructions that use the isolates, which form the stated subject of the work. No step reduces by definition or by self-citation to the target result; the cited Cameron-Puleo bound is external and the new claims are independent extensions for the isolate case. The derivation is self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard graph-theoretic definitions and the cited Cameron-Puleo bound; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Standard definitions of H-saturation, graph join, and subgraph containment hold.
    The paper operates entirely within classical extremal graph theory.

pith-pipeline@v0.9.1-grok · 5881 in / 1321 out tokens · 46640 ms · 2026-06-26T11:50:29.191270+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

29 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. 24

    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

    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]

    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

  16. [16]

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

    2023

  17. [17]

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

    2024

  18. [18]

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

    2025

  19. [19]

    Hua and Y

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

  20. [20]

    Huang, H

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

    2024

  21. [21]

    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. 25

    1986

  22. [22]

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

    2025

  23. [23]

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

    2023

  24. [24]

    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

  25. [25]

    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

    1972

  26. [26]

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

    2026

  27. [27]

    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

  28. [28]

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

    2026

  29. [29]

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

    2025