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

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

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

Книга (часто записывается $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}$.