WorksMathematics
Saturation and Semi-Saturation Numbers of Joins with Complete Graphs
Abstract
For a nonempty family of graphs, a graph is -semi-saturated if adding any missing edge creates a copy of some member of containing the added edge, and is -saturated if it is also -free. The minimum numbers of edges in such graphs of order are denoted by and , 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 has at least vertices, minimum degree at least two, and no triangle containing two vertices of degree two. We give explicit sufficient conditions under which and characterize all extremal graphs. For the family of subdivisions of , this identity holds for fixed and and all sufficiently large . For with , we establish the corresponding identity for saturation when and for semi-saturation when .