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

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 b k ( 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.)