Skip to content
DraconiticResearch
Search Sources API
190,839 studies31 sourcesUpdated 40 min ago
PreprintarXiv licencearXiv

Saturation numbers for joins with graphs containing isolated vertices

  • Xinying Hua
  • Yuejian Peng
Open at sourcePDFDOICite

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 sat(n,H) is the minimum number of edges in an n-vertex H-saturated graph. Cameron and Puleo [Discrete Math. 345 (2022), 112867] showed that sat(n,K1∨ F)≤ n−1+sat(n−1,F) for all n>|V(F)|. It is natural to ask when the equality holds. Most known results on this bound consider non-empty graphs F without isolated vertices. We study families in which F contains isolated vertices. For F=Kp−1∪ qK1, where p≥4 and q≥ p−1, we prove that sat(n,K1∨ F)=(p−2)n−binomp−12 for n≥max{p+q,binom p2} and determine the unique extremal graph. We also give the exact result for q=1, where the extremal graph has a different structure. For F=pK2∪ qK1, in the natural range n≥2p+q+1, we prove that sat(n,K1∨ F)=n+3p−4 holds exactly when n≥3p−2, and the order condition is sharp. Furthermore, we characterize all extremal graphs.

Related

  1. Lattice coverings by parallelotopes containing cube vertices
    Dragomir Grozev, Nikolai Nikolov
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  2. On the sum of eccentric subgraph numbers of the vertices of a connected graph
    Akash De, Kamal Lochan Patra
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Rich-neighbor 5-edge-colorings of subcubic graphs whose 3-vertices induce a matching
    Jiangxu Kong, Zhuming Lin, Yan Wang
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. A linear upper bound for Berge saturation numbers
    Tianying Xie
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Saturation numbers of K3 ∨ Pk
    Huaqin Li, Lihua You, Xiaoxue Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{hua2026saturation,
  title = {{Saturation numbers for joins with graphs containing isolated vertices}},
  author = {Xinying Hua and Yuejian Peng},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2606.22011},
  eprint = {2606.22011},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.22011},
}
RIS
TY  - UNPB
TI  - Saturation numbers for joins with graphs containing isolated vertices
AU  - Xinying Hua
AU  - Yuejian Peng
PY  - 2026
DA  - 2026/10/11
PB  - arXiv
DO  - 10.48550/arxiv.2606.22011
UR  - https://arxiv.org/abs/2606.22011
AB  - 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 sat(n,H) is the minimum number of edges in an n-vertex H-saturated graph. Cameron and Puleo [Discrete Math. 345 (2022), 112867] showed that sat(n,K_1∨ F)≤ n−1+sat(n−1,F) for all n>|V(F)|. It is natural to ask when the equality holds. Most known results on this bound consider non-empty graphs F without isolated vertices. We study families in which F contains isolated vertices. For F=K_p−1∪ qK_1, where p≥4 and q≥ p−1, we prove that sat(n,K_1∨ F)=(p−2)n−binomp−12 for n≥max{p+q,binom p2} and determine the unique extremal graph. We also give the exact result for q=1, where the extremal graph has a different structure. For F=pK_2∪ qK_1, in the natural range n≥2p+q+1, we prove that sat(n,K_1∨ F)=n+3p−4 holds exactly when n≥3p−2, and the order condition is sharp. Furthermore, we characterize all extremal graphs.
ER  -