In graph theory, a book graph (often written ) 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 K1,1,p. It is a graph consisting of triangles sharing a common edge. A book of this type is a split graph. This graph has also been called a 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.; ; 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 for his book-graph.)
Within larger graphs Given a graph , one may write for the largest book (of the kind being considered) contained within .
Theorems on books Denote the Ramsey number of two triangular books by This is the smallest number such that for every -vertex graph, either the graph itself contains as a subgraph, or its complement graph contains as a subgraph.
If , then . There exists a constant such that whenever . If , and is large, the Ramsey number is given by . Let be a constant, and . Then every graph on vertices and edges contains a (triangular) .
References