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 pquadrilaterals 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 K1,1,p. It is a graph consisting of triangles sharing a common edge.[3] A book of this type is a split graph.
This graph has also been called a [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 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.
^Lingsheng Shi; Zhipeng Song (2007). "Upper bounds on the spectral radius of book-free and/or K2,l-free graphs". Linear Algebra and Its Applications. 420 (2–3): 526–9. doi:10.1016/j.laa.2006.08.007.
^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.
^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..
^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.