Saturation numbers of books

Guantao Chen ; Ralph J. Faudree ; Ronald J. Gould

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

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) = {1\over2} \big( (p+1)(n-1) - \big\lceil {p\over2}\big\rceil \big\lfloor {p\over2} \big\rfloor + \theta(n,p)\big), $$ where $\theta(n, p) = \begin{cases} 1& \text{ if } p\equiv n -p/2 \equiv 0 \bmod 2 \\ 0& \text{ otherwise}\end{cases}$, provided $n \ge p^3 + p$. Moreover, we show that $$\eqalign{ sat(B_{b,p}, n) = \ & {1\over2} \big( (p+2b-3)(n-b+1) - \big\lceil {p\over2}\big\rceil \big\lfloor {p\over2} \big\rfloor\cr &+ \theta(n,p, b)+(b-1)(b-2) \big),\cr} $$ where $\theta(n, p, b) = \begin{cases} 1& \text{ if } p \equiv n -p/2 -b \equiv 0 \bmod 2 \\ 0 & \text{ otherwise} \end{cases}$, provided $n \ge 4(p+2b)^{b}$.

Détail

DOI : 10.37236/842

Classification : 05C35
Mots-clés : book, generalized book, triangles, saturated graph, saturation number