Книга (теорія графів)

Книга трикутників

Книга (часто записується ${\displaystyle B_{p}}$) — будь-який з графів, який утворений з циклів, що мають спільне ребро.

Варіації

Один вид, який можна назвати книгою чотирикутників, складається з p чотирикутників, що мають спільне ребро (відоме як «корінець» або «база» книги). Тобто це прямий добуток зірки і окремого ребра^[1]. 7-сторінкова книга цього типу є прикладом графу без гармонійної розмітки^[1].

Другий вид, який можна назвати книгою трикутників або трикутною книгою, є повним двочастковим графом K_1,1,p. Це граф, що складається з ${\displaystyle p}$ трикутників, що мають спільне ребро^[2]. Книга цього типу є розщеплюваним графом. Цей граф можна також назвати ${\displaystyle K_{e}(2,p)}$^[3]. Книги трикутників утворюють один з ключових блоків реберно-досконалих графів^[4].

Термін «граф-книга» використовувався для інших цілей. Так, Баріолі^[5] використовував його для графів, складених з довільних підграфів, що мають дві спільні вершини. (Баріолі для цих графів-книг не використовував позначення ${\displaystyle B_{p}}$.)

Всередині більших графів

Якщо дано граф ${\displaystyle G}$, можна записати ${\displaystyle bk(G)}$ для найбільшої книги (розглянутого типу), що міститься в ${\displaystyle G}$.

Теореми про книги

Позначивши число Рамсея двох трикутних книг ${\displaystyle r(B_{p},\ B_{q}).}$ Це найменше число ${\displaystyle r}$, таке, що для будь-якого графу з ${\displaystyle r}$ вершинами або сам граф містить ${\displaystyle B_{p}}$ як підграф, або його доповнення містить ${\displaystyle B_{q}}$ як підграф.

• Якщо ${\displaystyle 1\leqslant p\leqslant q}$, то ${\displaystyle r(B_{p},\ B_{q})=2q+3}$ (довели Руссо і Шихан).
• Існує стала ${\displaystyle c=o(1)}$, така, що ${\displaystyle r(B_{p},\ B_{q})=2q+3}$, коли ${\displaystyle q\geqslant cp}$.
• Якщо ${\displaystyle p\leqslant q/6+o(q)}$ і ${\displaystyle q}$ досить велике, число Рамсея задається формулою ${\displaystyle 2q+3}$.
• Нехай ${\displaystyle C}$ — стала, і ${\displaystyle k=Cn}$. Тоді будь-який граф з ${\displaystyle n}$ вершинами і ${\displaystyle m}$ ребрами містить книгу трикутників ${\displaystyle B_{k}}$^[6].

Примітка

1. Gallian, 1998, с. Dynamic Survey 6.
2. Shi, Song, 2007, с. 526—529.
3. Erdős, 1963, с. 156–160.
4. Maffray, 1992, с. 1–8.
5. Barioli, 1998, с. 11–31.
6. Erdős, 1962, с. 122—127.

Література

• Joseph Gallian. A dynamic survey of graph labeling // Electronic Journal of Combinatorics. — 1998. — Т. 5 (26 січня). Архівовано з джерела 8 листопада 2019. Процитовано 3 серпня 2021.
• 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. — Т. 420 (26 січня). — DOI:10.1016/j.laa.2006.08.007.
• Paul Erdős. On the structure of linear graphs // Israel Journal of Mathematics. — 1963. — Т. 1 (26 січня). — DOI:10.1007/BF02759702.
• Frédéric Maffray. Kernels in perfect line-graphs // Journal of Combinatorial Theory. — 1992. — Т. 55, вип. 1 (26 січня). — С. 1–8. — (Series B). — DOI:10.1016/0095-8956(92)90028-V.
• Francesco Barioli. Completely positive matrices with a book-graph // Linear Algebra and its Applications. — 1998. — Т. 277 (26 січня). — DOI:10.1016/S0024-3795(97)10070-2.
• Erdős P. On a theorem of Rademacher-Turán // Illinois Journal of Mathematics. — 1962. — Т. 6 (26 січня). Архівовано з джерела 26 липня 2020. Процитовано 3 серпня 2021.