Book (graph theory)

A triangular book

In graph theory, a book graph (often written Bp ) may be any of several kinds of graph formed by multiple cycles sharing an edge.

## Contents

* 1 Variations
* 2 Within larger graphs
* 3 Theorems on books
* 4 References

## 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 K1,1,p. It is a graph consisting of p triangles sharing a common edge.[3] A book of this type is a split graph. This graph has also been called a Ke(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 Bp 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(Bp, Bq). This is the smallest number r such that for every r-vertex graph, either the graph itself contains Bp as a subgraph, or its complement graph contains Bq as a subgraph.

* If 1≤p≤q, then r(Bp, Bq)=2q+3.[8]
* There exists a constant c=o(1) such that r(Bp, Bq)=2q+3 whenever q≥cp.
* If p≤q/6+o(q), and q is large, the Ramsey number is given by 2q+3.
* Let C be a constant, and k=Cn. Then every graph on n vertices and m edges contains a (triangular) Bk.[9]

## References

1. ↑ Weisstein, Eric W.. "Book Graph". http://mathworld.wolfram.com/BookGraph.html.
2. ↑ 2.0 2.1 "A dynamic survey of graph labeling". Electronic Journal of Combinatorics 5: Dynamic Survey 6. 1998. http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.
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. doi:10.37236/6567. ; 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. doi:10.1090/proc/14608. ; Proudfoot, Nicholas; Ramos, Eric (2019). "Functorial invariants of trees and their cones". Selecta Mathematica. New Series 25 (4): Paper 62. doi:10.1007/s00029-019-0509-4.
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. .
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. ↑ "On Ramsey numbers for books". Journal of Graph Theory 2 (1): 77–87. 1978. doi:10.1002/jgt.3190020110.
9. ↑ Erdős, P. (1962). "On a theorem of Rademacher-Turán". Illinois Journal of Mathematics 6: 122–7. doi:10.1215/ijm/1255631811. http://projecteuclid.org/euclid.ijm/1255631811.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Book (graph theory). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Book_(graph_theory)&oldid=241885"