Book (often recorded ) 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 triangles with a common edge [3] . A book of this type is a split graph . This graph can also be called [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 for these graph-books.)
Inside large graphs
If the graph is given you can write for the largest book (of the type in question) contained in .
Book theorems
Denote the number of Ramsey two triangular books This is the smallest number such that for a fierce graph with vertices either the graph itself contains as a subgraph, or its addition contains as a subgraph.
- If a then (proved by Rousseau and Sheehan).
- There is a constant such that when .
- If a and large enough, the Ramsey number is given by .
- Let be - constant, and . Then any graph with tops and contains edges (the book of triangles) [7] .
Notes
- ↑ Weisstein, Eric W. Book Graph (English) on Wolfram MathWorld .
- ↑ 1 2 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 .