Book (graph theory)


In graph theory, a book graph 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. 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 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.

Within larger graphs

Given a graph, one may write for the largest book 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 .