Book (graph theory)

In graph theory, a book graph (often written B p {\displaystyle B_{p}}  ) 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.^[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 {\displaystyle 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 ) {\displaystyle 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 {\displaystyle B_{p}} for his book-graph.)

Within larger graphs

Given a graph G {\displaystyle G} , one may write b k ( G ) {\displaystyle bk(G)} for the largest book (of the kind being considered) contained within G {\displaystyle G} .

Theorems on books

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

• If 1 ≤ q {\displaystyle 1\leq q} , then r ( B 1 ,   B q ) = 2 q + 3 {\displaystyle r(B_{1},\ B_{q})=2q+3} .^[8]
• There exists a constant c = o ( 1 ) {\displaystyle c=o(1)} such that r ( B p ,   B q ) = 2 q + 3 {\displaystyle r(B_{p},\ B_{q})=2q+3} whenever q ≥ c p {\displaystyle q\geq cp} .
• If p ≤ q / 6 + o ( q ) {\displaystyle p\leq q/6+o(q)} , and q {\displaystyle q} is large, the Ramsey number is given by 2 q + 3 {\displaystyle 2q+3} .
• Let C {\displaystyle C} be a constant, and k = C n {\displaystyle k=Cn} . Then every graph on n {\displaystyle n} vertices and m {\displaystyle m} edges contains a (triangular) B k {\displaystyle B_{k}} .^[9]

References