betaFeedback

WorksMathematics

Saturation and Semi-Saturation Numbers of Joins with Complete Graphs

Abstract

For a nonempty family F\mathcal F of graphs, a graph is F\mathcal F-semi-saturated if adding any missing edge creates a copy of some member of F\mathcal F containing the added edge, and is F\mathcal F-saturated if it is also F\mathcal F-free. The minimum numbers of edges in such graphs of order nn are denoted by ssat⁡(n,F)\operatorname{ssat}(n,\mathcal F) and sat⁡(n,F)\operatorname{sat}(n,\mathcal F), respectively. We study these parameters for families of graphs obtained by taking the join of a fixed complete graph with each member of a given graph family. Assume that every member of F\mathcal F has at least 88 vertices, minimum degree at least two, and no triangle containing two vertices of degree two. We give explicit sufficient conditions under which sat⁡(n,Kt∨F)=(t2)+t(n−t)+sat⁡(n−t,F),\operatorname{sat}(n,K_t\vee\mathcal F) =\binom{t}{2}+t(n-t)+\operatorname{sat}(n-t,\mathcal F), and characterize all extremal graphs. For the family C≥r={Cℓ:ℓ≥r}\mathcal C_{\ge r}=\{C_\ell:\ell\ge r\} of subdivisions of CrC_r, this identity holds for fixed t≥1t\ge1 and r≥4t2+8t+29r\ge4t^2+8t+29 and all sufficiently large nn. For Kt∨CkK_t\vee C_k with k≥2t2+3t+4k\ge2t^2+3t+4, we establish the corresponding identity for saturation when n≥2(k+t−2)3n\ge2(k+t-2)^3 and for semi-saturation when n≥56k3+t−1n\ge56k^3+t-1.

Paper details

vlnc:W_u4jfd89j
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC-BY-NC-SA-4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…