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

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

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

Варіації

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

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

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

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

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

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

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

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

Література

• Joseph Gallian. A dynamic survey of graph labeling // Electronic Journal of Combinatorics. — 1998. — Т. 5 (21 квітня). Архівовано з джерела 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 (21 квітня). — DOI:10.1016/j.laa.2006.08.007.
• Paul Erdős. On the structure of linear graphs // Israel Journal of Mathematics. — 1963. — Т. 1 (21 квітня). — DOI:10.1007/BF02759702.
• Frédéric Maffray. Kernels in perfect line-graphs // Journal of Combinatorial Theory. — 1992. — Т. 55, вип. 1 (21 квітня). — С. 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 (21 квітня). — DOI:10.1016/S0024-3795(97)10070-2.
• Erdős P. On a theorem of Rademacher-Turán // Illinois Journal of Mathematics. — 1962. — Т. 6 (21 квітня). Архівовано з джерела 26 липня 2020. Процитовано 3 серпня 2021.