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

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

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

Вариации

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

Второй вид, который может быть назван книгой треугольников или треугольной книгой, является полным двудольным графом K1,1,p. Это граф, состоящий из треугольников, имеющих общее ребро[3]. Книга этого типа является расщепляемым графом. Этот граф можно также назвать [4]. Книги треугольников образуют один из ключевых блоков рёберно совершенных графов[5].

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

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

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

Теоремы о книгах

Обозначим число Рамсея двух треугольных книг Это наименьшее число , такое, что для лютого графа с вершинами либо сам граф содержит в качестве подграфа, либо его дополнение содержит в качестве подграфа.

  • Если , то (доказали Руссо и Шихан).
  • Существует константа , такая, что , когда .
  • Если и достаточно большое, число Рамсея задаётся формулой .
  • Пусть — константа, и . Тогда любой граф с вершинами и рёбрами содержит (книгу треугольников) [7].

Примечания

  1. Weisstein, Eric W. Book Graph (англ.) на сайте Wolfram MathWorld.
  2. Gallian, 1998, с. Dynamic Survey 6.
  3. Shi, Song, 2007, с. 526—529.
  4. Erdős, 1963, с. 156–160.
  5. Maffray, 1992, с. 1–8.
  6. Barioli, 1998, с. 11–31.
  7. Erdős, 1962, с. 122—127.

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.