Book (graph theory)

Not to be confused with book embedding.

A triangular book

In graph theory, a book graph (often written ${\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 ${\displaystyle p}$ triangles sharing a common edge. ^[3] A book of this type is a split graph. This graph has also been called a ${\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 ${\displaystyle B_{p}}$ for his book-graph.)

Within larger graphs

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

Theorems on books

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

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

References

1. Weisstein, Eric W. "Book Graph". MathWorld .
2. Gallian, Joseph A. (1998). "A dynamic survey of graph labeling". Electronic Journal of Combinatorics . 5: Dynamic Survey 6. MR   1668059.
3. Lingsheng Shi; Zhipeng Song (2007). "Upper bounds on the spectral radius of book-free and/or K_2,l-free graphs". Linear Algebra and Its Applications. 420 (2–3): 526–9. doi: 10.1016/j.laa.2006.08.007 .
4. Erdős, Paul (1963). "On the structure of linear graphs". Israel Journal of Mathematics . 1 (3): 156–160. doi: 10.1007/BF02759702 .
5. Gedeon, Katie R. (2017). "Kazhdan-Lusztig polynomials of thagomizer matroids". Electronic Journal of Combinatorics. 24 (3). Paper 3.12. arXiv: 1610.05349 . doi:10.37236/6567. MR   3691529. S2CID   23424650.; Xie, Matthew H. Y.; Zhang, Philip B. (2019). "Equivariant Kazhdan-Lusztig polynomials of thagomizer matroids". Proceedings of the American Mathematical Society. 147 (11): 4687–4695. arXiv: 1902.01241 . doi: 10.1090/proc/14608 . MR   4011505.; Proudfoot, Nicholas; Ramos, Eric (2019). "Functorial invariants of trees and their cones". Selecta Mathematica. New Series. 25 (4). Paper 62. arXiv: 1903.10592 . doi:10.1007/s00029-019-0509-4. MR   4021848. S2CID   85517485.
6. Maffray, Frédéric (1992). "Kernels in perfect line-graphs". Journal of Combinatorial Theory . Series B. 55 (1): 1–8. doi: 10.1016/0095-8956(92)90028-V . MR   1159851..
7. Barioli, Francesco (1998). "Completely positive matrices with a book-graph". Linear Algebra and Its Applications. 277 (1–3): 11–31. doi: 10.1016/S0024-3795(97)10070-2 .
8. Rousseau, C. C.; Sheehan, J. (1978). "On Ramsey numbers for books". Journal of Graph Theory . 2 (1): 77–87. doi:10.1002/jgt.3190020110. MR   0486186.
9. Erdős, P. (1962). "On a theorem of Rademacher-Turán". Illinois Journal of Mathematics. 6: 122–7. doi: 10.1215/ijm/1255631811 .