Saturation numbers of books
Summary: A book \(B_p\) is a union of \(p\) triangles sharing one edge. This idea was extended to a generalized book \(B_{b,p}\), which is the union of \(p\) copies of a \(K_{b+1}\) sharing a common \(K_b\). A graph \(G\) is called an \(H\)-saturated graph if \(G\) does not contain \(H\) as a subgraph, but \(G\cup \{xy\}\) contains a copy of \(H\), for any two nonadjacent vertices \(x\) and \(y\). The saturation number of \(H\), denoted by sat\((H,n)\), is the minimum number of edges in \(G\) for all \(H\)-saturated graphs \(G\) of order \(n\). We show that \[ sat(B_p, n) = \frac{1}{2} \left((p+1)(n-1) - \left\lceil\frac{p}{2}\right\rceil \left\lfloor\frac{p}{2}\right\rfloor + \theta(n,p)\right), \] where \(\theta(n, p) = \begin{cases} 1\quad & \text{if }p\equiv n -p/2 \equiv 0\bmod 2 \\0 & \text{otherwise}\end{cases}, \text{provided } n \geq p^3 + p\). Moreover, we show that \[ sat(B_{b,p}, n) = \frac{1}{2} \left((p+2b-3)(n-b+1) - \left\lceil \frac{p}{2}\right\rceil \left\lfloor \frac{p}{2} \right\rfloor + \theta(n,p, b)+(b-1)(b-2)\right), \] where \(\theta(n, p,b) = \begin{cases} 1\quad & \text{if }p\equiv n -p/2 - b \equiv 0\bmod 2 \\ 0 & \text{otherwise}\end{cases}, \text{provided }n \geq 4(p + 2b)^b\).
scientific article; zbMATH DE number 5541023