Книга (теория графов)
В теории графов книжный граф (часто записываемый ) может быть любым из нескольких типов графа, образованного несколькими циклами, имеющими общее ребро.
Вариации
[ редактировать ]Один вид, который можно назвать четырехугольной книгой , состоит из p четырехугольников, имеющих общий край (известный как «позвоночник» или «основание» книги). есть это декартово произведение звезды То и одного ребра. [1] [2] 7-страничная книжная диаграмма этого типа представляет собой пример диаграммы без гармоничной разметки . [2]
Второй тип, который можно было бы назвать треугольной книгой , представляет собой полный трехдольный граф K 1,1, p . Это граф, состоящий из треугольники, имеющие общее ребро. [3] Книга такого типа представляет собой разделенный граф . Этот график еще называют [4] или граф тагомайзера (от тагомайзеров — шипастых хвостов динозавров -стегозавров из-за их заостренного вида на некоторых рисунках) и их графические матроиды были названы матроидами тагомайзера. [5] Треугольные книги образуют один из ключевых строительных блоков линейных совершенных графиков . [6]
Термин «книга-график» использовался и для других целей. Бариоли [7] использовал его для обозначения графа, состоящего из ряда произвольных подграфов, имеющих две общие вершины. (Бариоли не писал за свою книгу-графику.)
В рамках больших графиков
[ редактировать ]Учитывая график , можно написать за самую большую книгу (рассматриваемого типа), содержащуюся внутри .
Теоремы о книгах
[ редактировать ]Обозначим число Рамсея двух треугольных книг через Это наименьшее число такой, что для каждого -вершинный граф, либо сам граф содержит как подграф или его граф-дополнение содержит как подграф.
- Если , затем . [8]
- Существует константа такой, что в любое время .
- Если , и велико, число Рамсея определяется выражением .
- Позволять быть константой, и . Тогда каждый график на вершины и ребра содержат (треугольный) . [9]
Ссылки
[ редактировать ]- ^ Вайсштейн, Эрик В. «Книжный график» . Математический мир .
- ^ Jump up to: Перейти обратно: а б Галлиан, Джозеф А. (1998). «Динамический обзор разметки графов» . Электронный журнал комбинаторики . 5 : Динамическое обследование 6. MR 1668059 .
- ^ Линшэн Ши; Чжипен Сун (2007). «Верхние оценки спектрального радиуса графов без книг и/или K 2,l -свободных» . Линейная алгебра и ее приложения . 420 (2–3): 526–9. дои : 10.1016/j.laa.2006.08.007 .
- ^ Эрдеш, Пол (1963). «О структуре линейных графов» . Израильский математический журнал . 1 (3): 156–160. дои : 10.1007/BF02759702 .
- ^ Гедеон, Кэти Р. (2017). «Полиномы Каждана-Люстига матроидов тагомайзера». Электронный журнал комбинаторики . 24 (3). Статья 3.12. arXiv : 1610.05349 . дои : 10.37236/6567 . МР 3691529 . S2CID 23424650 . ; Се, Мэтью HY; Чжан, Филип Б. (2019). «Эквивариантные полиномы Каждана-Люстига матроидов тагомайзера» . Труды Американского математического общества . 147 (11): 4687–4695. arXiv : 1902.01241 . дои : 10.1090/proc/14608 . МР 4011505 . ; Праудфут, Николас; Рамос, Эрик (2019). «Функториальные инварианты деревьев и их конусов». Селекта Математика . Новая серия. 25 (4). Документ 62. arXiv : 1903.10592 . дои : 10.1007/s00029-019-0509-4 . МР 4021848 . S2CID 85517485 .
- ^ Маффрэ, Фредерик (1992). «Ядра в идеальных линейных графиках» . Журнал комбинаторной теории . Серия Б. 55 (1): 1–8. дои : 10.1016/0095-8956(92)90028-В . МР 1159851 . .
- ^ Бариоли, Франческо (1998). «Полностью положительные матрицы с книжным графом» . Линейная алгебра и ее приложения . 277 (1–3): 11–31. дои : 10.1016/S0024-3795(97)10070-2 .
- ^ Руссо, CC ; Шихан, Дж. (1978). «О числах Рамсея для книг». Журнал теории графов . 2 (1): 77–87. дои : 10.1002/jgt.3190020110 . МР 0486186 .
- ^ Эрдеш, П. (1962). «Об одной теореме Радемахера-Турана» . Иллинойский математический журнал . 6 : 122–7. дои : 10.1215/ijm/1255631811 .