Локально линейный граф - Locally linear graph

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

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

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

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

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

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

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

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

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

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

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

Расширение

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

Более сложный процесс расширения применяется к планарные графы.Позволять ${ displaystyle G}$ - плоский граф, вложенный в плоскость таким образом, что каждая грань является четырехугольником, например график куба. Обязательно, если ${ displaystyle G}$ имеет ${ displaystyle n}$ вершины, он имеет ${ displaystyle n-2}$ лица. Склеивание квадратная антипризма на каждое лицо ${ displaystyle G}$, а затем удалив исходные края ${ displaystyle G}$, создает новый локально линейный планарный граф с ${ Displaystyle 5 (п-2) +2}$ вершины и ${ Displaystyle 12 (п-2)}$ края.^[4] Например, кубооктаэдр снова может быть получен таким образом из двух граней (внутренней и внешней) четырехтактного цикла.

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

А Граф Кнезера ${ displaystyle KG_ {a, b}}$ имеет ${ displaystyle { tbinom {a} {b}}}$ вершины, представляющие ${ displaystyle b}$-элементные подмножества ${ displaystyle a}$-элементный набор. Две вершины смежны, если соответствующие подмножества не пересекаются. Когда ${ displaystyle a = 3b}$ полученный граф является локально линейным, потому что для каждых двух непересекающихся ${ displaystyle b}$-элементные подмножества есть ровно один другой ${ displaystyle b}$-элементное подмножество (дополнение их объединения), не пересекающееся с ними обоими. Полученный локально линейный граф имеет ${ displaystyle { tbinom {3b} {b}}}$ вершины и ${ displaystyle { tfrac {1} {2}} { tbinom {3b} {b}} { tbinom {2b} {b}}}$ края. Например, для ${ displaystyle b = 2}$ граф Кнезера ${ displaystyle KG_ {6,2}}$ локально линейна с 15 вершинами и 45 ребрами.^[2]

Локально линейные графы также могут быть построены из наборов чисел без прогрессии. ${ displaystyle p}$ - простое число, и пусть ${ displaystyle A}$ быть подмножеством чисел по модулю ${ displaystyle p}$ так что никакие три члена ${ displaystyle A}$ для мужчины арифметическая прогрессия по модулю ${ displaystyle p}$. (Это, ${ displaystyle A}$ это Набор Салема – Спенсера по модулю ${ displaystyle p}$.) Тогда существует трехчастный граф, в котором каждая сторона трехчастного раздела имеет ${ displaystyle p}$ вершин, есть ${ displaystyle 3 | A | p}$ ребра, и каждое ребро принадлежит уникальному треугольнику. Чтобы построить этот граф, пронумеруйте вершины на каждой стороне тройного разбиения из ${ displaystyle 0}$ к ${ displaystyle p-1}$, и построим треугольники вида ${ Displaystyle (х, х + а, х + 2а)}$ по модулю ${ displaystyle p}$ для каждого ${ displaystyle x}$ в диапазоне от ${ displaystyle 0}$ к ${ displaystyle p-1}$ и каждый ${ displaystyle a}$ в ${ displaystyle A}$. Граф, сформированный из объединения этих треугольников, обладает желаемым свойством, согласно которому каждое ребро принадлежит единственному треугольнику. В противном случае был бы треугольник ${ Displaystyle (х, х + а, х + а + b)}$ где ${ displaystyle a}$, ${ displaystyle b}$, и ${ Displaystyle с = (а + Ь) / 2}$ все принадлежат ${ displaystyle A}$, нарушая предположение об отсутствии арифметических прогрессий ${ Displaystyle (а, с, Ь)}$ в ${ displaystyle A}$.^[8] Например, с ${ displaystyle p = 3}$ и ${ displaystyle A = { pm 1 }}$, результатом является граф Пэли с девятью вершинами.

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

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

А сильно регулярный граф можно охарактеризовать четырьмя параметрами ${ Displaystyle (п, к, лямбда, му)}$ где ${ displaystyle n}$ - количество вершин, ${ displaystyle k}$ - количество инцидентных ребер на вершину, ${ displaystyle lambda}$ - количество общих соседей для каждой смежной пары вершин, а ${ displaystyle mu}$ - количество общих соседей для каждой несмежной пары вершин. Когда ${ displaystyle lambda = 1}$ граф локально линейный. Уже упоминавшиеся выше локально линейные графы являются сильно регулярными графами и их параметры равны

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

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

• то График Брауэра – Хемерса (81,20,1,6),^[9]
• то Граф Берлекампа – ван Линта – Зейделя (243,22,1,2),^[10]
• то Граф Коссиденте – Пенттила (378,52,1,8),^[11] и
• то График игр (729,112,1,20).^[12]

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

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

Плотность

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

Одна формулировка Проблема Ружи – Семереди запрашивает максимальное количество ребер в ${ displaystyle n}$-вершинный локально линейный граф. Так как Имре З. Ружа и Эндре Семереди доказано, это максимальное число ${ Displaystyle о (п ^ {2})}$ но это ${ Displaystyle Omega (п ^ {2- varepsilon})}$ для каждого ${ displaystyle varepsilon> 0}$. Построение локально линейных графов из множеств без прогрессии приводит к наиболее плотным из известных локально линейных графов с ${ Displaystyle п ^ {2} / ехр О ({ sqrt { log n}})}$ края.^[8]

Среди планарные графы, максимальное количество ребер в локально линейном графе с ${ displaystyle n}$ вершины ${ Displaystyle { tfrac {12} {5}} (п-2)}$. График кубооктаэдр является первым в бесконечной последовательности многогранные графы с участием ${ displaystyle n = 5k + 2}$ вершины и ${ displaystyle { tfrac {12} {5}} (n-2) = 12k}$ края, для ${ Displaystyle к = 2,3, точки}$, построенный расширением четырехугольных граней ${ displaystyle K_ {2, k}}$ в антипризмы. Эти примеры показывают, что эта верхняя граница точна.^[4]

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