pith. sign in

arxiv: 2605.07179 · v1 · submitted 2026-05-08 · 🧮 math.CO

The saturation number of K^s_t

Xinghui Zhao , Lihua You , Xiaoxue Zhang This is my paper

Pith reviewed 2026-05-11 01:16 UTC · model grok-4.3

classification 🧮 math.CO
keywords saturation numbervirus graphK^s_textremal graphssaturated graphsforbidden subgraphsgraph theory
0
0 comments X

The pith

Exact saturation numbers sat(n, K^3_3) and sat(n, K^2_t) for t at least 4 are determined, with the structures of all extremal graphs.

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

The paper computes the fewest edges an n-vertex graph can have while avoiding a copy of the virus graph K^3_3, yet forcing a copy whenever any missing edge is added. The same exact count and graph structures are found for the virus graphs K^2_t when t is at least four. A reader cares because these numbers identify the sparsest graphs that sit right at the boundary between avoiding and containing a given subgraph, which is a core question in extremal graph theory. The work completes the picture begun by earlier results on the simpler case K^2_3.

Core claim

For a given graph F, a graph G is said to be F-saturated if G contains no copy of F but for any edge uv not in E(G), G plus uv contains a copy of F. The saturation number sat(n,F) is the minimum number of edges among all n-vertex F-saturated graphs. The virus graph K^s_t, where s is at least 0 and t is at least the maximum of 3 and s, is formed by attaching s distinct leaves to s different vertices of a complete graph K_t. In this paper we determine sat(n,K^3_3) and sat(n,K^2_t) with t at least 4, together with the structural descriptions of the related extremal saturated graphs.

What carries the argument

The saturation number sat(n, K^s_t) for the virus graph K^s_t, realized by particular families of extremal saturated graphs.

If this is right

  • The value of sat(n, K^3_3) is known exactly for every n, along with every graph that achieves it.
  • The value of sat(n, K^2_t) is known exactly for every n when t is at least 4, along with every graph that achieves it.
  • The extremal graphs for both cases are completely characterized by explicit constructions.
  • These determinations extend the known case for K^2_3 to the next values of s and t in the virus graph family.

Where Pith is reading between the lines

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

  • The same style of construction may yield sat(n, K^s_t) for additional small values of s.
  • The structural families described may serve as candidates when studying saturation numbers for other graphs built from cliques plus leaves.
  • The results supply concrete lower bounds that can be tested against random or other sparse graphs in computational checks for moderate n.

Load-bearing premise

The extremal saturated graphs belong exactly to the families constructed in the paper and no other constructions use fewer edges for large n.

What would settle it

An n-vertex graph that avoids K^3_3, has fewer edges than the claimed sat(n, K^3_3), yet adding any missing edge creates a K^3_3 copy would falsify the result.

Figures

Figures reproduced from arXiv: 2605.07179 by Lihua You, Xiaoxue Zhang, Xinghui Zhao.

Figure 1
Figure 1. Figure 1: A graph in Mt n (K2). Our main results are as follows. Theorem 1.2 Let n ≥ 6, G = (Mq(K2)∪ n−q 5 K5)∪(Mq(K3)∪ n−q 5 K5)∪(Mp(K2 ∨(k − 2)K1) ∪ n−p 5 K5) with q ≤ n, 6 ≤ p ≤ n, 4 ≤ k ≤ p and Mq(H) ∪ H∗ = {H ∪ H∗ | H ∈ Mq(H)}. Then sat(n, K2 4 ) = 2n − 3 and SAT(n, K2 4 ) = G. Theorem 1.3 Let n, t, r be positive integers with n ≥ t + 2 ≥ 7 and 2 ≤ r ≤ t − 1. Then csat(n, K2 t ) =    tn 2 − t+2 2 , if n ≡ … view at source ↗
Figure 2
Figure 2. Figure 2: Graph G0. If b ≥ 3 and c = 2, then W2 = {w1, w2} with d(w1) = d(w2) = 3. Let Q9 be a copy of K3 3 in G + w2w1. Then w2, w1 ∈ V (CQ9), and thus w1w1 ∈ E(G) or w3w1 ∈ E(G) (if b = 3). Similarly, we have w1w2 ∈ E(G) or w3w2 ∈ E(G) (if b = 3) since G + w2w2 contains a copy of K3 3 . Furthermore, we have w1w1, w3w2 ∈ E(G) and thus b = 3 by d(w1) = 3, or w1w2, w3w1 ∈ E(G) and thus b = 3 since d(w1) = 3. We may a… view at source ↗
read the original abstract

For a given graph $F$, a graph $G$ is said to be $F$-saturated if $G$ contains no copy of $F$ but for any edge $uv\notin E(G)$, $G+uv$ contains a copy of $F$. The saturation number $sat(n,F)$ is defined as the minimum number of edges among all $n$-vertex $F$-saturated graphs. The virus graph $K^s_t$, where $s\geq0$ and $t\geq \max\{3,s\}$, is a graph of order $s+t$ constructed by attaching $s$ distinct leaves to $s$ different vertices of a complete graph $K_t$. Hua and Peng [Discrete Math. 349 (2026) 114674] determined $sat(n,K^2_3)$ and characterized its corresponding extremal graphs. In this paper, we determine $sat(n,K^3_3)$ and $sat(n,K^2_t)$ with $t\geq 4$, together with the structural descriptions of the related extremal saturated graphs.

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 paper determines the saturation numbers sat(n, K^3_3) and sat(n, K^2_t) for all t ≥ 4. It constructs explicit families of extremal K^s_t-saturated graphs on n vertices (unions of cliques with carefully placed pendant edges matching the virus-graph structure) and proves that these achieve the minimum edge count while satisfying the saturation condition; it also characterizes all extremal graphs via a finite case analysis on vertex neighborhoods in the core clique.

Significance. If the proofs hold, this extends the exact determination of sat(n, K^2_3) from Hua and Peng to two additional infinite families of virus graphs, supplying both the precise asymptotic and exact formulas for sat(n, F) together with structural descriptions of the extremal graphs. The constructions are parameter-free and the lower-bound argument reduces to exhaustive case division on neighborhoods, which is a strong feature for saturation problems where exact values are uncommon.

minor comments (3)
  1. The abstract and introduction state the main theorems but do not include a brief statement of the exact formulas for sat(n, K^3_3) and sat(n, K^2_t); adding these (even in asymptotic form) would improve readability.
  2. In the structural characterization, the description of the extremal graphs as 'unions of cliques with pendant edges' should be accompanied by a precise definition or diagram of the families (e.g., how many cliques, how the pendants are attached) to avoid ambiguity in the case analysis.
  3. The paper cites the prior result for K^2_3; a short comparison paragraph noting how the new case divisions differ from or generalize the earlier argument would help readers track the technical advance.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary and assessment of our manuscript. The referee's description of the main results on sat(n, K^3_3) and sat(n, K^2_t) for t ≥ 4, including the explicit constructions and structural characterizations, is accurate. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper determines sat(n, K^3_3) and sat(n, K^2_t) for t≥4 via explicit constructions of candidate extremal graphs (unions of cliques with pendant edges) together with a lower-bound argument that assumes an arbitrary F-saturated graph on n vertices, extracts structural constraints from the saturation condition, and partitions vertices by neighborhood type to show the edge count is at least that of the construction. This case analysis is finite and parameter-free; the cited result of Hua-Peng for the K^2_3 case is external prior work and is not invoked to justify the new families or the uniqueness of the extremal graphs. No equation reduces to a fitted input, no ansatz is smuggled via self-citation, and no uniqueness theorem is imported from the authors' own prior work. The central claims therefore rest on independent combinatorial reasoning rather than on re-labeling of inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper operates entirely within standard graph-theoretic definitions and prior saturation results; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Standard definitions of graphs, F-saturation, and the virus graph K^s_t as stated in the abstract.
    Relies on established concepts from extremal graph theory without additional assumptions.

pith-pipeline@v0.9.0 · 5487 in / 1283 out tokens · 30389 ms · 2026-05-11T01:16:19.121018+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Chen, All minimum C5-saturated graphs, J

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

    work page 2011

  2. [2]

    Chen, Minimum K2,3-saturated graphs, J

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

    work page 2014

  3. [3]

    Chen, X.Y

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

    work page 2024

  4. [4]

    Chen, R.J

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

    work page 2008

  5. [5]

    Erd˝ os, A

    P. Erd˝ os, A. Hajnal, J.W. Moon, A problem in graph theory, Am. Math. Mon, 71 (1964) 1107–1110

    work page 1964

  6. [6]

    Faudree, M

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

    work page 2009

  7. [7]

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

    work page 2025

  8. [8]

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

    work page 2024

  9. [9]

    Hua, Y.J

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

    work page 2026

  10. [10]

    Huang, H

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

    work page 2024

  11. [11]

    Lan, Y.T

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

    work page 2025

  12. [12]

    R.X. Li, R.X. Hao, Z. He, The saturation number for unions of four cliques, Discrete Math., 348 (2025) 114532

    work page 2025

  13. [13]

    Ollmann, K2,2-saturated graphs with a minimal number of edges, in: Proc

    L.T. Ollmann, K2,2-saturated graphs with a minimal number of edges, in: Proc. 3rd Southeastern Conference on Combinatorics, Graph Theory, and Computing, 1972, pp. 367–392. 28

    work page 1972

  14. [14]

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

    work page 2026

  15. [15]

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

    work page 2026

  16. [16]

    Tuza, C4-saturated graphs of minimum size, Acta Univ

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

    work page 1989

  17. [17]

    Zhang, L.H

    X.X. Zhang, L.H. You, X.H. Zhao, Saturation number of K2 ∨ Pk, ArXiv preprint, arXiv: 2511.20213, 2025

    work page arXiv 2025

  18. [18]

    Zhu, R.X

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

    work page 2025