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.