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

Не следует путать с Книжным вложением.

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

Книга треугольников

ВариацииПравить

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

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

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

Внутри больших графовПравить

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

Теоремы о книгахПравить

Обозначим число Рамсея двух треугольных книг $r(B_p,B_q).$$r(B_{p},\ B_{q}).$  Это наименьшее число $r$$r$ , такое, что для лютого графа с $r$$r$  вершинами либо сам граф содержит $B_p$$B_{p}$  в качестве подграфа, либо его дополнение содержит $B_q$$B_{q}$  в качестве подграфа.

• Если $1⩽<!--\; ⩽\; -->p⩽<!--\; ⩽\; -->q$$1\leqslant p\leqslant q$ , то $r(B_p,B_q)=2q+3$$r(B_{p},\ B_{q})=2q+3$  (доказали Руссо и Шихан).
• Существует константа $c=o(1)$$c=o(1)$ , такая, что $r(B_p,B_q)=2q+3$$r(B_{p},\ B_{q})=2q+3$ , когда $q⩾<!--\; ⩾\; -->cp$$q\geqslant cp$ .
• Если $p⩽<!--\; ⩽\; -->q/6+o(q)$$p\leqslant q/6+o(q)$  и $q$$q$  достаточно большое, число Рамсея задаётся формулой $2q+3$$2q+3$ .
• Пусть $C$$C$  — константа, и $k=Cn$$k=Cn$ . Тогда любой граф с $n$$n$  вершинами и $m$$m$  рёбрами содержит (книгу треугольников) $B_k$$B_{k}$ .