Book (graph theory)
In graph theory, a book graph (often written formula_1 ) may be any of several kinds of graph formed by multiple cycles sharing an edge. Variations. 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". It is a graph consisting of formula_2 triangles sharing a common edge. A book of this type is a split graph. This graph has also been called a formula_3 or a thagomizer graph (after thagomizers, the pointy tails of Stegosaurus dinosaurs, because of their pointy appearance in certain drawings) and their graphic matroids have been called thagomizer matroids. Triangular books form one of the key building blocks of line perfect graphs. 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 formula_1 for his book-graph.) Within larger graphs. Given a graph formula_5, one may write formula_6 for the largest book (of the kind being considered) contained within formula_5. Theorems on books. Denote the Ramsey number of two triangular books by formula_8 This is the smallest number formula_9 such that for every formula_9-vertex graph, either the graph itself contains formula_1 as a subgraph, or its complement graph contains formula_12 as a subgraph.