THC Science

In graph theory, a book graph (often written $B_{p}$ ) may be any of several kinds of graph formed by multiple cycles sharing an edge.

Variations[edit]

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). That is, it is a Cartesian product of a star and a single edge.^[1]^[2] The 7-page book graph of this type provides an example of a graph with no harmonious labeling.^[2]

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.^[3] A book of this type is a split graph. This graph has also been called a $K_{e}(2,p)$ ^[4] or a thagomizer graph (after thagomizers, the spiked tails of stegosaurian dinosaurs, because of their pointy appearance in certain drawings) and their graphic matroids have been called thagomizer matroids.^[5] Triangular books form one of the key building blocks of line perfect graphs.^[6]

The term "book-graph" has been employed for other uses. Barioli^[7] 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.)

Within larger graphs[edit]

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

Theorems on books[edit]

Denote the Ramsey number of two triangular books by $r(B_{p},\ B_{q}).$ This is the smallest number $r$ such that for every $r$ -vertex graph, either the graph itself contains $B_{p}$ as a subgraph, or its complement graph contains $B_{q}$ as a subgraph.

If $1\leq p\leq q$ , then $r(B_{p},\ B_{q})=2q+3$ .^[8]
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}$ .^[9]