WikiDer > Локально линейный граф

Locally linear graph
Девять вершин Граф Пэли локально линейно. Один из его шести треугольников выделен зеленым.

В теория графов, а локально линейный граф является неориентированный граф в которой окрестности каждого вершина является индуцированное соответствие. То есть для каждой вершины , каждый сосед должен быть смежным ровно с одним другим соседом . Равно как и каждое ребро такого графа принадлежит единственному треугольнику .[1] Локально линейные графы также называются локально согласованными графами.[2]

Примеры локально линейных графов включают треугольные кактусы графики, то линейные графики из 3-х регулярных графы без треугольников, а Декартовы произведения меньших локально линейных графов. Определенный Графы Кнезера, и некоторые сильно регулярные графы, также локально линейны.

Некоторые локально линейные графы имеют число ребер, близкое к квадратичному. Вопрос о том, насколько плотными могут быть эти графы, является одной из формулировок Проблема Ружи – Семереди. Самый плотный планарные графы также известны локально линейные.

Конструкции и примеры

В кубооктаэдр, плоский локально линейный граф, который может быть сформирован как линейный граф куба или путем наклеивания антипризм на внутреннюю и внешнюю грани 4-цикла

Известно несколько конструкций локально линейных графов.

Клей и изделия

В графы дружбы, графы, образованные путем склеивания набора треугольников в одной общей вершине, являются локально линейными. Это единственные конечные графы, обладающие тем более сильным свойством, что каждая пара вершин (смежных или нет) имеет ровно одного общего соседа.[3] В целом каждый треугольный кактус граф, граф, в котором все простые циклы являются треугольниками, а все пары простых циклов имеют не более одной общей вершины, является локально линейным.

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

В Декартово произведение любых двух локально линейных графов остается локально линейным, потому что любые треугольники в произведении происходят из треугольников в одном или другом множителе. Например, девятивершинная Граф Пэли (график 3-3 дуопризма) - декартово произведение двух треугольников.[1]В Графы Хэмминга являются продуктами треугольников, и снова локально линейны.[5]

Расширение

Если это 3-регулярный граф без треугольников, то линейный график - граф, образованный расширением каждого ребра в новую вершину и сделав две вершины смежными в когда соответствующие ребра поделиться конечной точкой. Эти графы 4-регулярны и локально линейны. Таким образом можно построить любой 4-регулярный локально линейный граф.[6] Например, график кубооктаэдр может быть сформирован таким образом как линейный граф куба, а девятивершинный граф Пэли является линейным графом график полезности .Линейный график Граф Петерсена, другой граф этого типа, обладает свойством, аналогичным клетки в том, что это наименьший возможный граф, в котором наибольший клика имеет три вершины, каждая вершина входит ровно в две непересекающиеся по ребрам клики, а кратчайший цикл с ребрами из различных клик имеет длину пять.[7]

Более сложный процесс расширения применяется к планарные графы.Позволять - плоский граф, вложенный в плоскость таким образом, что каждая грань является четырехугольником, например график куба. Обязательно, если имеет вершины, он имеет лица. Склеивание квадратная антипризма на каждое лицо , а затем удалив исходные края , создает новый локально линейный планарный граф с вершины и края.[4] Например, кубооктаэдр снова может быть получен таким образом из двух граней (внутренней и внешней) четырехтактного цикла.

Алгебраические конструкции

А Граф Кнезера имеет вершины, представляющие -элементные подмножества -элементный набор. Две вершины смежны, если соответствующие подмножества не пересекаются. Когда полученный граф является локально линейным, потому что для каждых двух непересекающихся -элементные подмножества есть ровно один другой -элементное подмножество (дополнение их объединения), не пересекающееся с ними обоими. Полученный локально линейный граф имеет вершины и края. Например, для граф Кнезера локально линейна с 15 вершинами и 45 ребрами.[2]

Локально линейные графы также могут быть построены из наборов чисел без прогрессии. - простое число, и пусть быть подмножеством чисел по модулю так что никакие три члена для мужчины арифметическая прогрессия по модулю . (Это, это Набор Салема – Спенсера по модулю .) Тогда существует трехчастный граф, в котором каждая сторона трехчастного раздела имеет вершин, есть ребра, и каждое ребро принадлежит уникальному треугольнику. Чтобы построить этот граф, пронумеруйте вершины на каждой стороне тройного разбиения из к , и построим треугольники вида по модулю для каждого в диапазоне от к и каждый в . Граф, сформированный из объединения этих треугольников, обладает желаемым свойством, согласно которому каждое ребро принадлежит единственному треугольнику. В противном случае был бы треугольник где , , и все принадлежат , нарушая предположение об отсутствии арифметических прогрессий в .[8] Например, с и , результатом является граф Пэли с девятью вершинами.

Регулярные и сильно регулярные графы

Каждый локально линейный граф должен иметь четные степень в каждой вершине, потому что ребра в каждой вершине можно объединить в треугольники. Декартово произведение двух локально линейных регулярных графов снова является локально линейным и регулярным со степенью, равной сумме степеней факторов. Следовательно, существуют регулярные локально линейные графы любой четной степени.[1]В -регулярные локально линейные графы должны иметь не менее вершин, потому что среди любого треугольника и только его соседей столько вершин. (Никакие две вершины треугольника не могут иметь общего соседа без нарушения локальной линейности.) Регулярные графы с точно таким количеством вершин возможны только тогда, когда равно 1, 2, 3 или 5 и однозначно определены для каждого из этих четырех случаев. Четыре регулярных графа, удовлетворяющие этой границе по количеству вершин, являются 3-вершинным 2-правильным треугольником , 9-вершинный 4-регулярный граф Пэли, 15-вершинный 6-регулярный граф Кнезера , а 27-вершинная 10-регулярная дополнительный граф из Граф Шлефли. Последний 27-вершинный 10-регулярный граф также представляет собой граф пересечений из 27 строк на кубическая поверхность.[2]

А сильно регулярный граф можно охарактеризовать четырьмя параметрами где - количество вершин, - количество инцидентных ребер на вершину, - количество общих соседей для каждой смежной пары вершин, а - количество общих соседей для каждой несмежной пары вершин. Когда граф локально линейный. Уже упоминавшиеся выше локально линейные графы являются сильно регулярными графами и их параметры равны

  • треугольник (3,2,1,0),
  • граф Пэли с девятью вершинами (9,4,1,2),
  • граф Кнезера (15,6,1,3), и
  • дополнение к графу Шлефли (27,10,1,5).

Другие локально линейные сильно регулярные графы включают

Другие потенциально допустимые комбинации с включают (99,14,1,2) и (115,18,1,3), но неизвестно, существуют ли строго регулярные графы с этими параметрами.[13] Вопрос о существовании сильно регулярного графа с параметрами (99,14,1,2) известен как 99-графовая проблема Конвея, и Джон Хортон Конвей предложил приз в размере 1000 долларов за это решение.[14]

Конечное количество дистанционно регулярные графы степени 4 или 6, локально линейные. Помимо строго регулярных графов тех же степеней, они также включают линейный граф графа Петерсена, граф Хэмминга. , а вдвое Граф Фостера.[15]

Плотность

Максимально плотные локально линейные плоские графы формируются путем приклеивания антипризмы (красные вершины и черные ребра) к каждой четырехугольной грани плоского графа (синие вершины и желтые пунктирные ребра)

Одна формулировка Проблема Ружи – Семереди запрашивает максимальное количество ребер в -вершинный локально линейный граф. Так как Имре З. Ружа и Эндре Семереди доказано, это максимальное число но это для каждого . Построение локально линейных графов из множеств без прогрессии приводит к наиболее плотным из известных локально линейных графов с края.[8]

Среди планарные графы, максимальное количество ребер в локально линейном графе с вершины . График кубооктаэдр является первым в бесконечной последовательности многогранные графы с участием вершины и края, для , построенный расширением четырехугольных граней в антипризмы. Эти примеры показывают, что эта верхняя граница точна.[4]

использованная литература

  1. ^ а б c Фрончек, Далибор (1989), «Локально линейные графы», Mathematica Slovaca, 39 (1): 3–6, HDL:10338.dmlcz / 136481, Г-Н 1016323
  2. ^ а б c Ларрион, Ф .; Pizaña, M.A .; Вильярроэль-Флорес, Р. (2011), "Маленький локально нК2 графики " (PDF), Ars Combinatoria, 102: 385–391, Г-Н 2867738
  3. ^ Эрдеш, Пол; Реньи, Альфред; Сос, Вера Т. (1966), «К проблеме теории графов» (PDF), Studia Sci. Математика. Hungar., 1: 215–235
  4. ^ а б c Зелинка, Богдан (1988), "Политопические локально линейные графы", Mathematica Slovaca, 38 (2): 99–103, HDL:10338.dmlcz / 133017, Г-Н 0945363
  5. ^ Девиллерс, Алиса; Джин, Вэй; Ли, Цай Хэн; Прегер, Шерил Э. (2013), «Локальная 2-геодезическая транзитивность и кликовые графы», Журнал комбинаторной теории, Серия А, 120 (2): 500–508, Дои:10.1016 / j.jcta.2012.10.004, Г-Н 2995054. В обозначениях этой ссылки семейство -регулярные графы обозначаются как .
  6. ^ Мунаро, Андреа (2017), «О линейных графах субкубических графов без треугольников», Дискретная математика, 340 (6): 1210–1226, Дои:10.1016 / j.disc.2017.01.006, Г-Н 3624607
  7. ^ Фан, Конг (1996), "Обобщенные клетки", Журнал теории графов, 23 (1): 21–31, Дои:10.1002 / (SICI) 1097-0118 (199609) 23: 1 <21 :: AID-JGT2> 3.0.CO; 2-M, Г-Н 1402135
  8. ^ а б Ружа, И.З.; Семереди, Э. (1978), «Тройные системы без шести точек, несущие три треугольника», Комбинаторика (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Коллок. Математика. Soc. Янош Бойяи, 18, Амстердам и Нью-Йорк: Северная Голландия, стр. 939–945, Г-Н 0519318
  9. ^ Брауэр, А.Э.; Хемерс, В. Х. (1992), "Структура и единственность (81,20,1,6) сильно регулярного графа", Сборник статей в честь Джека ван Линта, Дискретная математика, 106/107: 77–82, Дои:10.1016 / 0012-365X (92) 90532-К, Г-Н 1181899
  10. ^ Берлекамп, Э.; ван Линт, Дж. Х.; Зайдель, Дж. Дж. (1973), «Сильно регулярный граф, полученный из совершенного тернарного кода Голея», Обзор комбинаторной теории (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971), Амстердам: Северная Голландия: 25–30, Дои:10.1016 / B978-0-7204-2262-7.50008-9, ISBN 9780720422627, Г-Н 0364015
  11. ^ Коссиденте, Антонио; Пенттила, Тим (2005), "Полусистемы на эрмитовой поверхности", Журнал Лондонского математического общества, Вторая серия, 72 (3): 731–741, Дои:10.1112 / S0024610705006964, Г-Н 2190334
  12. ^ Бондаренко, Андрей В .; Радченко, Данило В. (2013), "О семействе сильно регулярных графов с ", Журнал комбинаторной теории, Серия B, 103 (4): 521–531, arXiv:1201.0383, Дои:10.1016 / j.jctb.2013.05.005, Г-Н 3071380
  13. ^ Махнев, А. А. (1988), "Сильно регулярные графы с ", Академия Наук СССР, 44 (5): 667–672, 702, Дои:10.1007 / BF01158426, Г-Н 0980587, S2CID 120911900
  14. ^ Зехави, Саар; Давид де Оливера, Иво Фагундес (2017), Не проблема Конвея с 99-графами, arXiv:1707.08047
  15. ^ Хираки, Акира; Номура, Казумаса; Судзуки, Хироши (2000), "Дистанционно регулярные графы валентности 6 и ", Журнал алгебраической комбинаторики, 11 (2): 101–134, Дои:10.1023 / А: 1008776031839, Г-Н 1761910