Misplaced Pages

Book (graph theory)

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Not to be confused with book embedding.
A triangular book

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. 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 p {\displaystyle p} triangles sharing a common edge. 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)} 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. 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. (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 ≤ p ≤ q {\displaystyle 1\leq p\leq q} , then r ( B p ,   B q ) = 2 q + 3 {\displaystyle r(B_{p},\ B_{q})=2q+3} .
  • 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}} .

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 K2,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.
Categories:
Book (graph theory) Add topic