ABCworld >> Book (graph theory)

Book (graph theory)

In graph theory, a book (usually written $B p$ ) is a graph consisting of $p$ triangles sharing a common edge (known as the "base" of the book). Given a graph $G$ , one often writes $b k (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.

Theorems on books

(here the Ramsey number between two books is denoted by $r (B p, B q)$ ).

If $1\leq p\leq q$ , then $r (B p, B q) = 2 q + 3$ (proved by Rousseau and Sheehan).
There exists a constant $c = o (1)$ such that $r (B p, B q) = 2 q + 3$ whenever $q\geq cp$ .
If $p\leq q/6+o(q)$ , and $q$ is large, the Ramsey number is given by $2 q + 3$ .

Let $C$ be a constant, and $k = C n$ . 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)