Book (graph theory) explained

Book (graph theory) should not be confused with book embedding.

In graph theory, a book graph (often written

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] The 7-page book graph of this type provides an example of a graph with no harmonious labeling.^[1]

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.^[2] A book of this type is a split graph. This graph has also been called a K _{e(2,p)} ^[3] 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.^[4] Triangular books form one of the key building blocks of line perfect graphs.^[5]

The term "book-graph" has been employed for other uses. Barioli^[6] 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.)

Within larger graphs

Given a graph

G , one may write bk(G) for the largest book (of the kind being considered) contained within G .

Theorems on books

Denote the Ramsey number of two triangular books by

r(B _{p, B} _{q).} This is the smallest number r such that for every r -vertex graph, either the graph itself contains B _{p} as a subgraph, or its complement graph contains B _{q} as a subgraph.

• If

1 \leq p\leq q , then r(B _{p, B} _{q)=2q+3} .^[7]

• There exists a constant

c = o( 1 ) such that r(B _{p, B} _{q)=2q+3} whenever q\geq cp .

• If

p\leq q/ 6+ o(q) , and q is large, the Ramsey number is given by 2 q +3 .

• Let

C be a constant, and k = Cn . Then every graph on n vertices and m edges contains a (triangular) B _{k} .^[8]

Notes and References

1. Gallian . Joseph A. . Joseph Gallian . . 1668059 . Dynamic Survey 6 . A dynamic survey of graph labeling . 5 . 1998.
2. Lingsheng Shi . Zhipeng Song . Upper bounds on the spectral radius of book-free and/or K_2,l-free graphs . Linear Algebra and Its Applications . 420 . 2007 . 2–3 . 526–9 . 10.1016/j.laa.2006.08.007. free .
3. Erdős. Paul. 1963. On the structure of linear graphs. Israel Journal of Mathematics. 1. 3 . 156–160. Paul Erdős. 10.1007/BF02759702. free.
4. Gedeon. Katie R.. 3. Electronic Journal of Combinatorics. 3691529. Paper 3.12. Kazhdan-Lusztig polynomials of thagomizer matroids. 24. 2017. 10.37236/6567 . 23424650 . 1610.05349.

   Xie. Matthew H. Y.. Zhang. Philip B.. 10.1090/proc/14608. 11. Proceedings of the American Mathematical Society. 4011505. 4687–4695. Equivariant Kazhdan-Lusztig polynomials of thagomizer matroids. 147. 2019. free. 1902.01241. ; Proudfoot. Nicholas. Ramos. Eric. 10.1007/s00029-019-0509-4. 4. Selecta Mathematica. 4021848. Paper 62. New Series. Functorial invariants of trees and their cones. 25. 2019. 1903.10592. 85517485 .

5. Maffray . Frédéric . 10.1016/0095-8956(92)90028-V . 1 . . 1159851 . 1–8 . Series B . Kernels in perfect line-graphs . 55 . 1992. free . .
6. Francesco . Barioli . Completely positive matrices with a book-graph . Linear Algebra and Its Applications . 277 . 1998 . 1–3 . 11–31 . 10.1016/S0024-3795(97)10070-2. free .
7. Rousseau . C. C. . Cecil C. Rousseau . Sheehan . J. . 10.1002/jgt.3190020110 . 1 . . 486186 . 77–87 . On Ramsey numbers for books . 2 . 1978.
8. P. . Erdős . On a theorem of Rademacher-Turán . Illinois Journal of Mathematics . 6 . 1962 . 122–7 . 10.1215/ijm/1255631811. free .