Book (graph theory)

In graph theory, a book graph (often written $B_p$ ) may be any of several kinds of graph.

One kind, which may be called a quadrilateral book, consists of p quadrilaterals sharing a common edge (known as the "spine" or "base" of the book). A book of this type is the Cartesian product of a star and K₂ .

A second type, which might be called a triangular book, is the complete tripartite graph K_1,1,p. It is a graph consisting of $p$ triangles sharing a common edge. A book of this type is a split graph. This graph has also been called a $K_e(2,p)$.

Given a graph $G$, one may write $bk(G)$ for the largest book (of the kind being considered) contained within $G$.

The term "book-graph" has been employed for other uses. Barioli used it to mean a graph composed of a number of arbitrary subgraphs having two vertices in common. (Barioli did not write $B_p$ for his book-graph.)

Theorems on books

Denote the Ramsey number of two (triangular) books by $r(B_p,\ B_q).$

• If $1\leq p\leq 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 $q\geq cp$.
• If $p\leq 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 (triangular) $B_k$.