Book (graph theory)

In graph theory, a book (usually written $B\_p$) is a split graph consisting of $p$ triangles sharing a common edge (known as the "base" of the book). Given a graph $G$, one often writes $bk(G)$ for the largest book contained within $G$.

Note: in the past, this has been referred to as a $K\_e(2,p)$ (see Erdos, P: On The Structure of Linear Graphs, Israel Journal of Mathematics, 1 (1963) pp156-160). Let $K(m,n)$ denote the complete bipartite graph with bipartitions of sizes $m$ and $n$. Then a $K\_e(m,n)$ is defined as a $K(m,n)$ with an extra edge in the first partition. It may also be viewed as a complete tripartite graph "K"_1,1,"p".

Theorems on books

(here the Ramsey number between two books is denoted by $r(B\_p,B\_q)$).
* If $1leq\; pleq\; q$, then $r(B\_p,B\_q)=2q+3$ (proved by Rousseau and Sheehan).
* There exists a constant $c=o(1)$ such that $r(B\_p,B\_q)=2q+3$ whenever $qgeq\; cp$.
* If $pleq\; q/6+o(q)$, and $q$ is large, the Ramsey number is given by $2q+3$.

* Let $C$ be a constant, and $k\; =\; Cn$. Then every graph on $n$ vertices and $m$ edges contains a $B\_k$. (see Erdos, P: On a Theorem of Rademacher-Turan, Illinois Journal of Mathematics 6 (1962) pp122-127)