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

Треугольная книга

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

Вариации

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

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

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

• Если , то . ^[8] ${\displaystyle 1\leq p\leq q}$ ${\displaystyle r(B_{p},\ B_{q})=2q+3}$
• Существует константа такая, что всякий раз, когда . ${\displaystyle c=o(1)}$ ${\displaystyle r(B_{p},\ B_{q})=2q+3}$ ${\displaystyle q\geq cp}$
• Если и велико, число Рамсея определяется выражением . ${\displaystyle p\leq q/6+o(q)}$ ${\displaystyle q}$ ${\displaystyle 2q+3}$
• Пусть будет константой, и . Тогда каждый граф на вершинах и ребрах содержит (треугольный) . ^[9] ${\displaystyle C}$ ${\displaystyle k=Cn}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle B_{k}}$

Ссылки

1. Вайсштейн, Эрик В. «Книжный граф». MathWorld .
2. Gallian, Joseph A. (1998). "Динамический обзор маркировки графов". Electronic Journal of Combinatorics . 5 : Dynamic Survey 6. MR  1668059.
3. Lingsheng Shi; Zhipeng Song (2007). «Верхние оценки спектрального радиуса графов без книг и/или K2,l-свободных». Линейная алгебра и ее приложения . 420 (2–3): 526–9. doi : 10.1016/j.laa.2006.08.007 .
4. Эрдёш, Пол (1963). «О структуре линейных графов». Israel Journal of Mathematics . 1 (3): 156–160. doi : 10.1007/BF02759702 .
5. Гедеон, Кэти Р. (2017). «Полиномы Каждана-Люстига матроидов Тагомайзера». Электронный журнал комбинаторики . 24 (3). Статья 3.12. arXiv : 1610.05349 . doi : 10.37236/6567. MR  3691529. S2CID  23424650.; Xie, Matthew HY; Zhang, Philip B. (2019). «Эквивариантные многочлены Каждана-Люстига матроидов Тагомайзера». Труды Американского математического общества . 147 (11): 4687–4695. arXiv : 1902.01241 . doi : 10.1090/proc/14608 . MR  4011505.; Праудфут, Николас; Рамос, Эрик (2019). «Функториальные инварианты деревьев и их конусов». Selecta Mathematica . Новая серия. 25 (4). Статья 62. arXiv : 1903.10592 . doi :10.1007/s00029-019-0509-4. MR  4021848. S2CID  85517485.
6. Маффрей, Фредерик (1992). «Ядра в совершенных линейных графах». Журнал комбинаторной теории . Серия B. 55 (1): 1–8. doi : 10.1016/0095-8956(92)90028-V . MR  1159851..
7. Бариоли, Франческо (1998). «Полностью положительные матрицы с книжным графом». Линейная алгебра и ее приложения . 277 (1–3): 11–31. doi : 10.1016/S0024-3795(97)10070-2 .
8. Руссо, CC ; Шихан, Дж. (1978). «О числах Рамсея для книг». Журнал теории графов . 2 (1): 77–87. doi :10.1002/jgt.3190020110. MR  0486186.
9. Эрдеш, П. (1962). «К теореме Радемахера-Турана». Иллинойский математический журнал . 6 : 122–7. дои : 10.1215/ijm/1255631811 .