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

Один вид, который может быть назван книгой четырёхугольников, состоит из p четырёхугольников, имеющих общее ребро (известное как «корешок» или «база» книги). То есть это прямое произведение звезды и отдельного ребра[1][2]. 7-Страничная книга этого типа даёт пример графа без гармоничной разметки[2].

Второй вид, который может быть назван книгой треугольников или треугольной книгой, является полным двудольным графом K_1,1,p. Это граф, состоящий из ${\displaystyle p}$ треугольников, имеющих общее ребро[3]. Книга этого типа является расщепляемым графом. Этот граф можно также назвать ${\displaystyle K_{e}(2,p)}$[4]. Книги треугольников образуют один из ключевых блоков рёберно совершенных графов[5].

Термин «граф-книга» использовался для других целей. Так, Бариоли[6] использовал его для графов, составленных из произвольных подграфов, имеющих две общие вершины. (Бариоли не использовал обозначение ${\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}}$[7].