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 \cite{Ca} 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)$.
From: Xinying Hua [view email]
[v1]
Sat, 20 Jun 2026 12:11:19 UTC (694 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。