Book (graph theory)

Book of triangles

Book (often recorded $B_{p}$ ${\ displaystyle B_ {p}}$ ${\ displaystyle B_ {p}}$ ) can be any graph of some kind that is formed by cycles having a common edge.

Content

Variations

One view, which can be called a book of quadrangles , consists of p quadrilaterals with a common edge (known as the “root” or “base” of the book). That is, it is a direct product of a star and a separate edge ^[1] ^[2] . The 7-page book of this type gives an example of a graph without harmonious markup ^[2] .

The second kind, which may be called a triangle book or a triangular book , is a full bipartite graph K _{1,1, p} . This is a graph consisting of $p$ ${\ displaystyle p}$ triangles with a common edge ^[3] . A book of this type is a split graph . This graph can also be called $K_{e}(2,p)$ ${\ displaystyle K_ {e} (2, p)}$ ^[4] . The books of triangles form one of the key blocks of edge graphs ^[5] .

The term "graph-book" was used for other purposes. Thus, Barioli ^[6] used it for graphs composed of arbitrary subgraphs having two common vertices. (Barioli did not use the designation $B_{p}$ ${\ displaystyle B_ {p}}$ for these graph-books.)

Inside large graphs

If the graph is given $G$ ${\ displaystyle G}$ you can write $bk(G)$ ${\ displaystyle bk (G)}$ for the largest book (of the type in question) contained in $G$ ${\ displaystyle G}$ .

Book theorems

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

If a $1\leqslant p\leqslant q$ ${\ displaystyle 1 \ leqslant p \ leqslant q}$ then $r(B_{p},\ B_{q})=2q+3$ ${\ displaystyle r (B_ {p}, \ B_ {q}) = 2q + 3}$ (proved by Rousseau and Sheehan).
There is a constant $c=o(1)$ ${\ displaystyle c = o (1)}$ such that $r(B_{p},\ B_{q})=2q+3$ ${\ displaystyle r (B_ {p}, \ B_ {q}) = 2q + 3}$ when $q\geqslant cp$ ${\ displaystyle q \ geqslant cp}$ .
If a $p\leqslant q/6+o(q)$ ${\ displaystyle p \ leqslant q / 6 + o (q)}$ and $q$ ${\ displaystyle q}$ large enough, the Ramsey number is given by $2q+3$ ${\ displaystyle 2q + 3}$ .
Let be $C$ ${\ displaystyle C}$ - constant, and $k=Cn$ ${\ displaystyle k = Cn}$ . Then any graph with $n$ ${\ displaystyle n}$ tops and $m$ ${\ displaystyle m}$ contains edges (the book of triangles) $B_{k}$ ${\ displaystyle B_ {k}}$ ^[7] .

Notes

↑ Weisstein, Eric W. Book Graph (English) on Wolfram MathWorld .
↑ ¹ ² Gallian, 1998 , p. Dynamic Survey 6.
↑ Lingsheng, Zhipeng, 2007 , p. 526–9.
↑ Erdős, 1963 , p. 156–160.
↑ Maffray, 1992 , p. 1–8.
↑ Barioli, 1998 , p. 11–31.
↑ Erdős, 1962 , p. 122–7.

Literature

Joseph Gallian. A dynamic survey of graph labeling // Electronic Journal of Combinatorics . - 1998. - V. 5 .
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. - 2007. - T. 420 . - DOI : 10.1016 / j.laa.2006.08.007 .
Paul Erdős . On the structure of linear graphs // Israel Journal of Mathematics. - 1963. - T. 1 . - DOI : 10.1007 / BF02759702 .
Frédéric Maffray. Kernels in perfect line graphs // Journal of Combinatorial Theory . - 1992. - T. 55 , no. 1 . - P. 1–8 . - DOI : 10.1016 / 0095-8956 (92) 90028-V .
Francesco Barioli. Completely positive matrices with a book-graph // Linear Algebra and its Applications. - 1998. - T. 277 . - DOI : 10.1016 / S0024-3795 (97) 10070-2 .
Erdős P. On a theorem of Rademacher-Turán // Illinois Journal of Mathematics. - 1962. - Vol . 6 .

[1] Weisstein, Eric W. Book Graph (English) on Wolfram MathWorld .

[_16ef50c8c310546b-2] ¹ ² Gallian, 1998 , p. Dynamic Survey 6.

[_33e9302f6ab1ce2d-3] Lingsheng, Zhipeng, 2007 , p. 526–9.

[_5e1f539eb66c9b0a-4] Erdős, 1963 , p. 156–160.

[_24a4906f0daf4c44-5] Maffray, 1992 , p. 1–8.

[_37c2bad698605477-6] Barioli, 1998 , p. 11–31.

[_4372b2c89837586c-7] Erdős, 1962 , p. 122–7.