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

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

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

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

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

Конструкции и примеры [ править ]

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

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

Клей и продукты [ править ]

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

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

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

Расширение [ править ]

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

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

Алгебраические конструкции [ править ]

Кнезер граф имеет вершины, представляющую -элементные подмножества элементного множества. Две вершины смежны, если соответствующие подмножества не пересекаются. Когда результирующий граф является локально линейным, потому что для каждых двух непересекающихся -элементных подмножеств существует ровно одно подмножество других -элементов (дополнение к их объединению), которое не пересекается с ними обоими. Полученный локально линейный граф имеет вершины и ребра. Например, для графа Кнезера локально линейный граф с 15 вершинами и 45 ребрами. ^[2]${\ 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}}$

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

Регулярные и сильно регулярные графы [ править ]

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

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

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

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

• график Браувер-Haemers (81,20,1,6), ^[9]
• Берлекемпа-ван Линт-Зейделя граф (243,22,1,2), ^[10]
• график Cossidente-Penttilä (378,52,1,8), ^[11] и
• график Игры (729,112,1,20). ^[12]

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

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

Плотность [ править ]

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

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

Ссылки [ править ]