PreprintarXiv licencearXiv
Saturation numbers of K3 ∨ Pk
Abstract
A graph G is said to be H-saturated if G contains no copy of H, but G+e contains a copy of H for any edge e of G̅. The saturation number of H, denoted by sat(n, H), is the minimum number of edges among all H-saturated graphs of order n. In this paper, we investigate the saturation number of K3 ∨ Pk for k ≥ 3 and show that sat(n, K3 ∨ Pk) = 3n − 6 + sat(n−3, Pk) holds for all n ≥ ak + 3 and k ≥ 3, which verifies the conjecture [Discrete Appl. Math, 394(2026) 62-80] on sat(n, Ks ∨ Pk) is true for the case s=3, where ak = k for 3 ≤ k ≤ 5, ak = 3 · 2t−1 − 2 for k = 2t ≥ 6, and ak = 2t+1 − 2 for k = 2t + 1 ≥ 7.
Related
- A linear upper bound for Berge saturation numbers
- Saturation numbers for joins with graphs containing isolated vertices
- Weak rainbow saturation numbers of paths, stars and cycles
- A note on power saturation in one-dimensional spaces
- Saturation in three-uniform Berge hypergraphs: the five-star spectrum and the K4 saturation number
BibTeX
@misc{li2026saturation,
title = {{Saturation numbers of $K_3 \vee P_k$}},
author = {Huaqin Li and Lihua You and Xiaoxue Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34990},
eprint = {2610.34990},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34990},
}
RIS
TY - UNPB
TI - Saturation numbers of K_3 ∨ P_k
AU - Huaqin Li
AU - Lihua You
AU - Xiaoxue Zhang
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.34990
UR - https://arxiv.org/abs/2610.34990
AB - A graph G is said to be H-saturated if G contains no copy of H, but G+e contains a copy of H for any edge e of G̅. The saturation number of H, denoted by sat(n, H), is the minimum number of edges among all H-saturated graphs of order n. In this paper, we investigate the saturation number of K_3 ∨ P_k for k ≥ 3 and show that sat(n, K_3 ∨ P_k) = 3n − 6 + sat(n−3, P_k) holds for all n ≥ a_k + 3 and k ≥ 3, which verifies the conjecture [Discrete Appl. Math, 394(2026) 62-80] on sat(n, K_s ∨ P_k) is true for the case s=3, where a_k = k for 3 ≤ k ≤ 5, a_k = 3 · 2^t−1 − 2 for k = 2t ≥ 6, and a_k = 2^t+1 − 2 for k = 2t + 1 ≥ 7.
ER -