Saturation numbers of books
type: Item
instance of: scholarly article
title: Saturation numbers of books
zbMATH Open document ID: 1158.05033
author: Guantao Chen
author: Ronald Gould
author: Ralph Faudree
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/129702
full work available at URL: v15i1r118.html
review text: 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\).
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5541023
zbMATH Keywords: book
zbMATH Keywords: generalized book
zbMATH Keywords: triangles
zbMATH Keywords: saturated graph
zbMATH Keywords: saturation number
MaRDI profile type: Publication
Recommended article: The Ramsey number of books
Recommended article: Ramsey numbers of large books
Recommended article: Ramsey Numbers Involving Large Books
Recommended article: Q3132256
Recommended article: Books in graphs
Recommended article: Ramsey numbers of fans and large books
description: scientific article; zbMATH DE number 5541023